设G = ＜V, E＞中无孤立点。M为G的最大匹配, 对于G中每个未覆盖顶点v, 选取与v关联的边组成集合N,则MÈN是G的最小边覆盖。
设G = ＜V, E＞中无孤立点。M为G的最大匹配, 对于G中每个未覆盖顶点v, 选取与v关联的边组成集合N,则MÈN是G的最小边覆盖。
参考答案和解析
错误
相关考题：
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。[说明]Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图，令T是由G的顶点构成的于图，Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树：初始时，T中的点互相不连通；考察G的边集E中的每条边，若它的两个顶点在T中不连通，则将此边添加到T中，同时合并其两顶点所在的连通分量，如此下去，当添加了n-1条边时，T的连通分量个数为1，T便是G的一棵最小生成树。下面的函数void Kruskal(EdgeType edges[],int n)利用Kruskal算法，构造了有n个顶点的图 edges的最小生成树。其中数组father[]用于记录T中顶点的连通性质：其初值为father[i]=-1 (i=0,1,…,n-1)，表示各个顶点在不同的连通分量上；若有father[i]=j，j＞-1，则顶点i，j连通；函数int Find(int father[],int v)用于返回顶点v所在树形连通分支的根结点。[函数]define MAXEDGE 1000typedef struct{ int v1;int v2;}EdgeType;void Kruskal(EdgeType edges[],int n){ int father[MAXEDGE];int i,j,vf1,vt2;for(i=0;i＜n;i+ +) father[i]=-1;i=0;j=0;while(i＜MAXEDGE j＜(1)){ vf1=Find(father,edges[i].v1);vf2=Find(father,edges[i].v2);if((2)){(3)=vf1;(4);printf("%3d%3d\n",edges[i].v1,edges[i].v2);}(5);}}int Find(int father[],int v){ int t;t=v;while(father[t]＞=0) t=father[t];return(t);}
阅读下列C程序和程序说明，将应填入(n)处的字句写在答题纸的对应栏内。【说明】用克鲁斯卡尔算法求解给定图的最小生成树。include ＜stdio. h＞include ＜stdlib. h＞define MAXN 30typedef struct{ int v1,v2; /*一条边依附的两个顶点*/int weight; /*边上的权值*/}EDGE;typedef struct{ int Vnum; /*图中的顶点数目*/EDGE e[MAXN*(MAXN-1)/2]; /*图中的边*/}Graph;typedef struct node{ /*用链表存储同一个连通分量的顶点*/int v;struct node *next;}Alist;void heapadjust(EDGE data[], int s, int m){ /*将元素序列data[s..m]调整为小顶堆, 堆顶元素(最小元素)为data[s]*/int j;EDGE t;t=data[s]; /*备份元素data[s], 为其找到适当位置后再插入*/for(j=2*s+1; j＜=m; j=j*2+1){/*沿值较小的子结点向下筛选*/if(j＜m (1)) ++j;if(!(t. weight＞data[j]. weight)) break;data[s]=data[j];s=j; /*用s记录待插入元素的位置(下标)*/}/*for*/data[s]=t; /*将备份元素插入由s所指出的插入位置*/}/*heapadjust*/int creat_graph(Graph *p) /*输入图中的顶点及边, 返回图中边的数目*/{ int k=0; /*记录图中边的数目*/int n;int v1,v2;int w;printf("vertex number of the graph:");scanf("%d", n); /*输入图中的顶点数目*/if(n＜1) return 0;p-＞Vnum=n;do{ printf("edge(vertex1,vertex2,weight):");scanf("%d %d %d", V1, v2, w);if(v1＞=0 v1＜n v2＞=0 v2＜n){p-＞e[k]. v1=v1; p-＞e[k]. v2=v2; p-＞e[k]. weight=w;k++;}/*if*/}while(!( (2) ));return k; /*返回图中边的数目*/}/*creat_graph*/int kruskal(Graph G, int enumber, int tree[][3]){ /*用kruskal算法求无向连通图G的最小生成树, 图中边所得数目为enumber, *//*数组tree[][3]中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/int i, k, m, c=0;int v1, v2;Alist *p, *q, *a[MAXN];for(i=0; i＜G．Vnum; ++i){ /*将每个连通分量中的顶点存放在一个单链表中*/a[i]=(Alist*)malloc(sizeof(Alist));if(!a[i]) {printf("\n mernory allocation error!");exit(0);}/*if*/a[i]-＞v=i; a[i]-＞next=NULL;}/*for*/for(i=enumber-1; i＞=0; --i)/*按照边上的权值建立小顶堆*/heapadjust( (3) );k=G. Vnum; /*k用于计算图中的连通分量数目*/m=enumber-1;i=0;do{v1=G. e[0]. v1; v2=G. e[0]. v2;p=a[v1];while(p p-＞v!=v2){ /*判断当前选择的边的顶点是否在一个连通分量中*/q=p; p=p-＞next;}if(!p){ /*当前边的顶点不在一个连通分量中*/p=q;p-＞next=a[G. e[0]. v2];&nb
设G是n个顶点的无向简单图,则下列说法不正确的是() A、若G是树，则其边数等于n-1B、若G是欧拉图，则G中必有割边C、若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点D、若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路
分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: ① 增加一个新顶点v,InsertVex(G, v); ② 删除顶点v及其相关的边,DeleteVex(G, v); ③ 增加一条边,InsertArc(G, v, w); ④ 删除一条边,DeleteArc(G, v, w)。
● McCabe度量法是通过定义环路复杂度，建立程序复杂性的度量，它基于一个程序模块的程序图中环路的个数。计算有向图 G 的环路复杂性的公式为：V(G)=m-n+2，其中 V(G)是有向图 G 中的环路个数，m是 G 中的有向弧数，n 是 G 中的节点数。下图所示程序图的程序复杂度是 （32） 。（32）A. 2B. 3C. 4D. 5
设|V|=n(n>1),当且仅当______,G=是强连通图。A.G中至少有一条路B.G中至少有一条回路C.G中有 设|V|=n(n＞1)，当且仅当______，G=＜V，E＞是强连通图。A．G中至少有一条路B．G中至少有一条回路C．G中有通过每个节点至少一次的路D．G中有通过每个节点至少一次的回路A．B．C．D．
设有一个无向图G=(V，E)和G′=(V′,E′)，如果G′为G的生成树，则下面不正确的说法是(40)。A．G′为G的子图B．G′为G的极小连通子图且V′=VC．G′为G的一个无环子图D．G′为G的边通分量
设无向图G=(V，E)和G′=(V′，E′)，如果G′是G的生成树，则下面的说法中错误的是()。A.G′为G的极小连通子图且V=V′B.G′是G的一个无环子图C.G′为G的子图D.G′为G的连通分量
设无向图G=（V，E）和G’=（V’，E’），如果G’是G的生成树，则下面的说法中错误的是（）。A、G’为G的子图B、G’为G的连通分量C、G’为G的极小连通子图且V=V’D、G’是G的一个无环子图
单选题设无向图G=（V，E）和G’=（V’，E’），如果G’是G的生成树，则下面的说法中错误的是（）。AG’为G的子图BG’为G的连通分量CG’为G的极小连通子图且V=V’DG’是G的一个无环子图
单选题设无向图G有n个顶点m条边，则其邻接表中表结点数是（）AnB2nCmD2m