违法和不良信息举报 联系客服
免费注册 登录

若一个具有n个节点、k条边的非连通无向图是一个森林(n>k),则该森林中必有(19)棵树。A.kB.nC.n－kD.n

题目

若一个具有n个节点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(19)棵树。

A．k

B．n

C．n-k

D．n+k

如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

若一森林有n个顶点、k个分支（n＞k)，该森林必有（）棵树。

A．k

B．n

C．n-k

D．1


N-K

第2题：

若一个具有N个顶点，K条边的无向图是一个森林（N＞K且2K＞=N），则该森林有多少棵树？ There is an undirected graph. It has N nodes and K edges. （N＞K and 2K＞=N). If it is a forest, then how many trees will it has？


N-K

第3题：

若一个具有n个结点k条边的无向图是一个森林（n＞k），则该森林必有（）棵树。

A．k

B．n

C．n-k

D．n+k


n-k

第4题：

10、若一个具有N个顶点，K条边的无向图是一个森林（N＞K且2K＞=N），则该森林有多少棵树？ There is an undirected graph. It has N nodes and K edges. （N＞K and 2K＞=N). If it is a forest, then how many trees will it has？


N-K

第5题：

若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有()棵树。

A.k
B.n
C.n-k
D.n+k

答案：C
解析：
一个具有n个结点的树有n-l条边，结点数比边数多1，则若一个森林中有m棵树，其结点数比边数多m。反过来，森林中树的个数等于结点数减去边数。

第6题：

若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(34)棵树。

A．k

B．n

C．n-k

D．n+k


正确答案：C
解析：根据抽屉原理，至少有n-k-1个结点无边可连，因此至少有n-k棵树。

第7题：

若一个具有n个结点、k条边的非连通无向图是一个森林(n，k)，则该森林中必有(58)棵树。

A．k

B．n

C．n-k

D．n+k


正确答案：C
解析：假设该森林中有s棵树：T1，T2...，TS，且每个Ti有ni个结点，ki条边(i=1,2,...，S)，由树的等价条件可知：ki=ni-1，则k＝k1+k2+...+ks：(n1-1)+(n2-1)+...+(ns-1)=n-s，故s=n-k，所以该森林中必有n-k棵树。友情提示：该题如果清楚树的等价条件，可以很容易的解出。若不清楚，则无法下手。不过考生也可以画出一个具体的非连通无向图的森林，如：5个结点3条边2棵树的森林，也可帮助判断。抽象问题具体化是作选择题的一个重要方法。

第8题：

若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有( )。棵树。

A．k

B．n

C．n-k

D．n+k


正确答案：C
解析：假设有x棵树，任一棵树的结点数ni与边数ki都满足ni=ki+1，所以对x棵树有 n=k+x，则x=n-k。

第9题：

下列叙述中正确的是（ ）。A．连通分量是无向图中的极小连通子图 B．生成树是连通图的一个极大连通子图 C．若一个含有n个顶点的有向图是强连通图，则该图中至少有n条弧 D．若一个含有n个顶点的无向图是连通图，则该图中至少有n条边


正确答案：C
有向图是一个二元组，其中 　　1.V是非空集合，称为顶点集。 　　2.E是V×V的子集，称为边集。 　　直观来说，若图中的每条边都是有方向的，则称为有向图。有向图中的边是由两个顶点组成的有序对，有序对通常用尖括号表示，如表示一条有向边，其中vi是边的始点，vj是边的终点。和代表两条不同的有向边。如果在有向图中任意两个顶点都是连通的，则称图为连通图。因此如果有向图是连通图，则该图中至少有n条弧。 一个无向图(undirected graph)是一个二元组，其中： 　　1.E是非空集合，称为顶点集。 　　2.V是E中元素构成的无序二元组的集合，称为边集。 　　直观来说，若一个图中每条边都是无方向的，则称为无向图。

相关内容