图的基本概念试题解析

一、单项选择题
01．图中有关路径的定义是( A )。
A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形成的序列
C.由不同边所形成的序列 D.上述定义都不是

02．一个有n个顶点和n条边的无向图一定是（ D )。
A．连通的 B．不连通的 C.无环的 D.有环的
解析：若一个无向图有n个顶点和n-1条边，可以使它连通但没有环，但若再加一条边，在不考虑重边的情形下，则必然会构成环

03．若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( B )。
A.强连通图 B.连通图 C.有回路 D.一棵树
解析：强连通图必定是有向图，A错误，对无向连通图做一次深度优先搜索可以访问到该连通图的所有顶点，B正确，有回路的无向图不一定是连通图，因为回路不一定包含图的所有结点，C错误；连通图可能是树，也可能存在环，D错

04.以下关于图的叙述中，正确的是（C )。
A.图与树的区别在于图的边数大于或等于顶点数
B.假设有图G={V,{E}}，顶点集 $V'\subseteq V,E'\subseteq E$ ，则V'和{E'}构成G的子图
C.无向图的连通分量是指无向图中的极大连通子图
D.图的遍历就是从图中某一顶点出发访遍图中其余顶点
解析：A图与树的区别是逻辑上的区别，而不是边数的区别，图的边数也可能小于树的边数，B中若E'中的边对应的顶点不是V'的元素，V'和{E'}无法构成图；无向图的极大连通子图称为连通分量，C正确;图的遍历要求每个结点只能被访问依次，若图非连通，则从某个顶点出发无法访问到其他全部顶点,D错。

05.以下关于图的叙述中，正确的是（C )。
A.强连通有向图的任何顶点到其他所有顶点都有弧
B.图的任意顶点的入度等于出度
C.有向完全图一定是强连通有向图
D.有向图的边集的子集和顶点集的子集都构成原有向图的子图
解析：强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧；无向图的任意顶点的入度等于出度，但有向图未必满足；若边集中的某条边对应的某个顶点不在对应的顶点集中，则有向图的边集的子集和顶点集的子集无法构成子图。

06.一个有28条边的非连通无向图至少有（C)个顶点。
A.7 B.8 C.9 D.10
解析：至少有多少个结点的情形，考虑非连通图最极端的情况，由一个完全图加一个独立的顶点构成，此时再加一条边，必然使图变成连通图，在28=n(n-1)/2=8*7/2条边的完全无向图中，总共有8个顶点，再加上1个不连通的顶点，共9个顶点。

07.对于一个有n个顶点的图:若是连通无向图，其边的个数至少为()，若是强连通有向图，则其边的个数至少为(A).
A. n-1,n B. n-1, n(n-1) C. n, n D.n, n(n-1)

08．无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G有（D )个顶点。
A.11 B. 12 C. 15 D.16
解析：无向图的全部顶点的度的和等于边数的2倍，23*2=4*5+3*4+2*i,度为2的顶点7，所以共5+4+7=16个顶点

09．在有n个顶点的有向图中，顶点的度最大可达(D) 。
A. n B. n-1 C. 2n D. 2n-2
解析：有向图中，顶点的度等于出度和入度之和，n个顶点的有向图中，任意一个顶点最多可以与其他n-1个顶点有一对指向相反的边相连，所以顶点的度最大可达2(n-1)

10．具有6个顶点的无向图，当有(D)条边时能确保是一个连通图。
A.8 B.9 C. 10 D.11
解析：5个顶点构成一个完全无向图需要n(n-1)/2=10条边，再加上1条边后能保证第六个顶点必然与此完全无向图构成一个连通图，所以共需11条边

11.设有无向图G=(V,E)和G'=(V,E')，若G是G的生成树，则下列不正确的是(D)。
Ⅰ.G'为G的连通分量
Ⅱ.G'为G的无环子图
Ⅲ.G'为G的极小连通子图且V'=V
A.I、Ⅱ B.只有Ⅲ C.Ⅱ、Ⅲ D.只有Ⅰ
解析：一个连通图的生成树是一个极小连通子图，显然它是无环的，所以选项Ⅱ、IⅢ正确。极大连通子图称为连通分量，G'连通但非连通分量。
若图本来就不是连通的，且每个子部分包含其本身的所有顶点和边，则它就是极大连通子图。

12．具有51个顶点和21条边的无向图的连通分量最多为( C )。
A. 33 B.34 C. 45 D.32

13.在如下图所示的有向图中，共有(B）个强连通分量。

A. 1 B.2 C.3 D.4

14.若具有n个顶点的图是一个环，则它有（B）棵生成树。
A. n^2 B.n C. n-1 D.1
解析：n个顶点的生成树具有n-1条边的极小连通子图，因为n个顶点构成的环共有n条边，去掉任意一条边就是一棵生成树，所以共有n种情况

15.若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有( C )棵树。
A. n B. e C. n-e D.1
解析：n个结点的树有n-1条边，假设森林有x棵树，将每棵树的根连到一个添加的结点，则称为一棵树，结点数是n+1,边数是e+x,x=n-e

16.【2009统考真题】下列关于无向连通图特性的叙述中，正确的是(A)。
Ⅰ所有顶点的度之和为偶数
Ⅱ.边数大于顶点个数减1
Ⅲ.至少有一个顶点的度为1
A.只有Ⅰ B.只有Ⅱ C.I和Ⅱ D.Ⅰ和Ⅲ
解析：每条边都连接了两个顶点，在计算顶点的度之和时每条边都被计算了两次，所以所有顶点的度之和为偶数，无向连通图对应生成的树也是连通图，但此时的边数等于顶点数减1，Ⅱ错，考虑2个或以上的顶点恰好构成一个环的情况，此时每个顶点的度都是2，Ⅲ错

17.【2010统考真题】若无向图G=(V, E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是（C)。
A. 6 B.15 C.16 D.21
6个顶点构成的完全图再加一条边，则可保证是连通的，6*5/2=15条边 ,所以至少要15+1=16条边

18.【2017统考真题】已知无向图G含有 16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是( B )。
A.10 B.11 C.13 D.15
解析:2*16=4*3+3*4+2*n ,n=4，至少3+4+4=11个顶点

19.【2022统考真题】对于无向图G=(V,E)，下列选项中，正确的是（ D).
A.当|V|>|E|时，G一定是连通的
B.当|V|<|E|时，G一定是连通的
C.当|V|=|E|-1时，G一定是不连通的
D.当|V|>|E|+1时，G一定是不连通的