一棵无向树T有5片树叶、3个2度分支点,其余的分支点都是3度顶点,则T有几个顶点?
一棵无向树T有5片树叶、3个2度分支点,其余的分支点都是3度顶点,则T有几个顶点?
参考答案和解析
假设 T 有 n 个结点,根据握手定理,有 得 n =11 。
相关考题:
阅读下列函数说明和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);}
● 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程,若在有向图中从顶点vi到vj有一条路径,则在该线性序列中,顶点 vi 必然在顶点 vj之前。因此,若不能得到全部顶点的拓扑排序序列,则说明该有向图一定 (57)(57)A. 包含回路B. 是强连通图C. 是完全图D. 是有向树
● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构 (矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧),则该矩阵的元素数目为 (60) ,其中非零元素数目为 (61) 。
如果一个有向图(25),则是一棵有向树。A.恰有一个顶点的人度为0,其余顶点的人度为1B.恰有一个顶点的人度为1,其余顶点的人度为0C.恰有一个顶点的人度为1,其余顶点的人度为2D.恰有一个顶点的人度为1,其余顶点的度大于1
填空题如果无向图G有n个顶点,那么G的一棵生成树有且仅有()条边。