网友您好, 请在下方输入框内输入要搜索的题目:

题目内容 (请给出正确答案)
判断题
若图G的最小生成树不唯一,则G的边数一定多于n-1,并且权值最小的边有多条(其中n为G的顶点数)。
A

B


参考答案

参考解析
解析: 暂无解析
更多 “判断题若图G的最小生成树不唯一,则G的边数一定多于n-1,并且权值最小的边有多条(其中n为G的顶点数)。A 对B 错” 相关考题
考题 如果网络中有多条边的权相同,则其最小生成树就不会是唯一的。() 此题为判断题(对,错)。

考题 ● 若无向连通图 G 具有 n个顶点,则以下关于图 G的叙述中,错误的是(43)。(43)A.G 的边数一定多于顶点数B.G 的生成树中一定包含 n个顶点C.从 G 中任意顶点出发一定能遍历图中所有顶点D.G 的邻接矩阵一定是n阶对称矩阵

考题 设连通图G的顶点数和边数与一立方体相同,即有8个顶点和12条边。任意一棵G的生成树的总边数为A.7B.8C.9D.10

考题 设G是n个顶点的无向简单图,则下列说法不正确的是() A、若G是树,则其边数等于n-1B、若G是欧拉图,则G中必有割边C、若G中有欧拉路,则G是连通图,且有零个或两个奇度数顶点D、若G中任意一对顶点的度数之和大于等于n-1,则G中有汉密尔顿路

考题 连通图的各边权值均不相同,则该图的最小生成树是唯一的。()

考题 图的生成树是不唯一的,一个连通图的生成树是一个最小连通子图,n个顶点的生成树有n-1条边,最小代价生成树是唯一的。( ) 此题为判断题(对,错)。

考题 设无向图G中顶点数为n,图G最多( )有条边。 A: nB: n-1C: n*(n-1)/2D: n*(n-1)

考题 连通图G有n个点,其部分树为T,则有()。 A、T有n个点n条边B、T的长度等于G的每条边的长度之和C、T有n个点n+1条边D、T有n-1个点n条边

考题 若无向连通图G具有n个顶点,则以下关于图G的叙述中,错误的是( )。A.c的边数一定多于顶点数B.G的生成树中一定包含n个顶点C.从c中任意顶点出发一定能遍历图中所有顶点D.G的邻接矩阵一定是n阶对称矩阵

考题 阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】 应用Prim算法求解连通网络的最小生成树问题。请阅读程序后填空。const int MaxInt=INT MAX; //INT MAX的值在<limits.h>中const int n=6; //图的顶点数,应由用户定义typedef int AdjMatrix[n][n]; //用二维数组作为邻接矩阵表示typedef struct{ //生成树的边结点int fromVex,to Vex; //边的起点与终点int weight; //边上的权值}TreeEdSenode;typedef TreeEdgeNode MST[n-1]; //最小生成树定义void PrimMST (AdjMatrix G,MST T,int rt){//从顶点rt出发构造图G的最小生成树T,rt成为树的根结点TreeEdgeNode e; int i,k=0,min,minpos,v;for(i=0;i<n;i++) //初始化最小生成树Tif(i!=rt){T[k].fromVex=rt;(1);T[k++].weight=G[rt][i];}for(k=0;k<n-1;k++){ //依次求MST的候选边(2);for(i=k;i<n-1;i++) 八遍历当前候选边集合if(T[i].weight<min) //选具有最小权值的候选边{min=T[i].weight;(3);}if(min==MaxInt) //图不连通,出错处理{cerr<<“Graph is disconnected!”<<endl; exit(1);}e=T[minpos];T[minpos]=T[k];(4);v=T[k].to Vex;for(i=k+1;i<n-1;i++) //修改候选边集合if(G[v][T[i].to Vex]<T[i].weight){T[i].weight=G[v][T[i].toVex];(5);}}}

考题 ●试题四阅读下列算法说明和算法,将应填入(n)的字句写在答题纸的对应栏内。【说明】下列最短路径算法的具体流程如下:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去,直至该森林变成一棵树为止,这棵树便是连通网的最小生成树。该算法的基本思想是:为使生成树上总的权值之和达到最小,则应使每一条边上的权值尽可能地小,自然应从权值最小的边选起,直至选出n-1条互不构成回路的权值最小边为止。图5算法流程图【算法】/*对图定义一种新的表示方法,以一维数组存放图中所有边,并在构建图的存储结构时将它构造为一个"有序表"。以顺序表MSTree返回生成树上各条边。*/typedef struct{VertexType vex1;VertexType vex2;VRType weight;}EdgeType;typedef ElemType EdgeType;typedef struct{//有向网的定义VertexType vexs[MAX_VERTEX_NUM];//顶点信息EdgeType edge[MAX_EDGE_NUM];//边的信息int vexnum,arcnum;//图中顶点的数目和边的数目}ELGraph;void MiniSpanTree_Kruskal(ELGraph G,SqList MSTree){//G.edge 中依权值从小到大存放有向网中各边//生成树的边存放在顺序表MSTree中MFSetF;InitSet(F,G.vexnum);//将森林F初始化为n棵树的集合InitList(MSTree,G.vexnum);//初始化生成树为空树i=0;k=1;while(k (1) ){e=G.edge[i];//取第i条权值最小的边/*函数fix_mfset返回边的顶点所在树的树根代号,如果边的两个顶点所在树的树根相同,则说明它们已落在同一棵树上。*/rl=fix_mfset(F,LocateVex(e.vex1));r2= (2) //返回两个顶点所在树的树根if(r1 (3) r2){//选定生成树上第k条边if(ListInsert(MSTree,k,e){ (4) ;//插入生成树mix_mfset(E,rl,r2);//将两棵树归并为一棵树}(5) ;//继续考察下一条权值最小边}DestroySet(F);}

考题 在图G点最小生成树G1中,可能会有某条边的权值超过未选边的权值。()

考题 对于含有n个顶点的带权连通图,它的最小生成树是指()。A.图中任意一个由n-l条权值最小的边构成的子图 B.图中任意一个由n-1条权值之和最小的边构成的子图 C.图中任意一个由n-1条权值之和最小的边构成的连通子图 D.图中任意一个由n个顶点构成的边的权值之和最小的连通子图

考题 连通图G有n个点,其部分树是T,则有()A、T有n个点n条边B、T的长度等于G的每条边的长度之和C、T有n个点n-1条边D、T有n-1个点n条边

考题 关于图的生成树,下列说法不正确的是()。A、它又称为图的支撑树。B、图有生成树的充要条件是该图为连通图。C、图的生成树是唯一的。D、顶点数为n的图的生成树有n-1条边。

考题 平面上有五个点A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图G的顶点,每两点之间的直线距离是图G中对应边的权值。以下哪条边不是图G的最小生成树中的边()。A、ADB、BDC、CDD、DEE、EA

考题 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。

考题 若图G的最小生成树不唯一,则G的边数一定多于n-1,并且权值最小的边有多条(其中n为G的顶点数)。

考题 最小生成树指的是()。A、由连通网所得到的边数最少的生成树B、由连通网所得到的顶点数相对较少的生成树C、连通网中所有生成树中权值之和为最小的生成树D、连通网的极小连通子图

考题 若连通网络上各边的权值均不相同,则该图的最小生成树有()棵。

考题 设无向图G中顶点数为n,则图G至少有()条边,至多有()条边;若G为有向图,则至少有()条边,至多有()条边。

考题 设无向图G的顶点数为n,图G最少有()边。

考题 单选题最小生成树指的是()。A 由连通网所得到的边数最少的生成树B 由连通网所得到的顶点数相对较少的生成树C 连通网中所有生成树中权值之和为最小的生成树D 连通网的极小连通子图

考题 判断题连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。A 对B 错

考题 填空题设无向图G中顶点数为n,则图G至少有()条边,至多有()条边;若G为有向图,则至少有()条边,至多有()条边。

考题 填空题若连通网络上各边的权值均不相同,则该图的最小生成树有()棵。

考题 单选题关于图的生成树,下列说法不正确的是()。A 它又称为图的支撑树。B 图有生成树的充要条件是该图为连通图。C 图的生成树是唯一的。D 顶点数为n的图的生成树有n-1条边。