网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。
参考答案
更多 “若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。” 相关考题
考题
设G是n个顶点的无向简单图,则下列说法不正确的是()
A、若G是树，则其边数等于n-1B、若G是欧拉图，则G中必有割边C、若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点D、若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路
考题
阅读下列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)；}
考题
对于含有n个顶点的带权连通图，它的最小生成树是指()。A.图中任意一个由n-l条权值最小的边构成的子图
B.图中任意一个由n-1条权值之和最小的边构成的子图
C.图中任意一个由n-1条权值之和最小的边构成的连通子图
D.图中任意一个由n个顶点构成的边的权值之和最小的连通子图
考题
平面上有五个点A（5，3），B（3，5），C（2，1），D（3，3），E（5，1）。以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。以下哪条边不是图G的最小生成树中的边（）。A、ADB、BDC、CDD、DEE、EA
考题
填空题若一个连通图中每个边上的权值均不同，则得到的最小生成树是（）（唯一/不唯一）的。
热门标签
最新试卷
