6.1 图的基本概念·习题

教材导航 · 返回本节知识

复习入口

6.1 图的基本概念 · 6.1.1 图的定义与基本术语

本节共20题:选择题19题,综合应用题1题。每题答案紧接题目折叠显示。

文字转录进度:20/20题。已转录题目的题干、选项和解析可编辑;示意图按需保留。

单项选择题

单项选择题 01

原书题目P201 · 解析P203 · 目视转录

图中有关路径的定义是( )。

A. 由顶点和相邻顶点序偶构成的边所形成的序列

B. 由不同顶点所形成的序列

C. 由不同边所形成的序列

D. 上述定义都不是

查看答案与解析

答案:A。

本题是北京交通大学考研真题,不同教材对路径的定义可能略有不同,顶点之间关联的边也可理解为路径的构成要素。对于选项 B,路径的定义中并没有要求是不同顶点,比如简单回路的第一个顶点和最后一个顶点是可以相同的,此外选项 B 也没有说明这些顶点之间有边相联。

单项选择题 02

原书题目P202 · 解析P203 · 目视转录

一个有 n 个顶点和 n 条边的无向图一定是( )。

A. 连通的

B. 不连通的

C. 无环的

D. 有环的

查看答案与解析

答案:D。

若一个无向图有 n 个顶点和 n-1 条边,可以使它连通但没有环(生成树),但若再加一条边,在不考虑重边的情形下,则必然会构成环。

单项选择题 03

原书题目P202 · 解析P203 · 目视转录

若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是( )。

A. 强连通图

B. 连通图

C. 有回路

D. 一棵树

查看答案与解析

答案:B。

强连通图是有向图,与题意矛盾,选项 A 错误;对无向连通图做一次深度优先搜索,可以访问到该连通图的所有顶点,选项 B 正确;有回路的无向图不一定是连通图,因为回路不一定包含图的所有结点,选项 C 错误;连通图可能是树,也可能存在环,选项 D 错误。

单项选择题 04

原书题目P202 · 解析P204 · 目视转录

以下关于图的叙述中,正确的是( )。

A. 图与树的区别在于图的边数大于或等于顶点数

B. 假设有图 G={V,{E}}G=\{V,\{E\}\},顶点集 V′⊆VV'\subseteq V,E′⊆EE'\subseteq E,则 V′V' 和 {E′}\{E'\} 构成 G 的子图

C. 无向图的连通分量是指无向图中的极大连通子图

D. 图的遍历就是从图中某一顶点出发访遍图中其余顶点

查看答案与解析

答案:C。

图与树的区别是逻辑上的区别,而不是边数的区别,图的边数也可能小于树的边数,选项 A 错误;若 E′ 中的边对应的顶点不是 V′ 的元素,V′ 和 {E′} 无法构成图,选项 B 错误;无向图的极大连通子图称为连通分量,选项 C 正确;图的遍历要求每个结点只能被访问一次,且若图非连通,则从某一顶点出发无法访问到其他全部顶点,选项 D 的说法不准确。

单项选择题 05

原书题目P202 · 解析P204 · 目视转录

以下关于图的叙述中,正确的是( )。

A. 强连通有向图的任何顶点到其他所有顶点都有弧

B. 图的任意顶点的入度等于出度

C. 有向完全图一定是强连通有向图

D. 有向图的边集的子集和顶点集的子集都构成原有向图的子图

查看答案与解析

答案:C。

强连通有向图的任何顶点到其他所有顶点都有路径,但未必有弧;无向图任意顶点的入度等于出度,但有向图未必满足;若边集中的某条边对应的某个顶点不在对应的顶点集中,则有向图的边集的子集和顶点集的子集无法构成子图。

转录核对:无向图通常只定义“度”,不区分入度和出度;原解析关于无向图“入度等于出度”的说法并非本书有向图入度、出度定义的适用对象。

单项选择题 06

原书题目P202 · 解析P204 · 目视转录

一个有 28 条边的非连通无向图至少有( )个顶点。

A. 7

B. 8

C. 9

D. 10

查看答案与解析

答案:C。

考查至少有多少个顶点的情形,我们考虑该非连通图最极端的情况,即它由一个完全图加一个独立的顶点构成,此时若再加一条边,则必然使图变成连通图。在 28=n(n−1)/2=8×7/228=n(n-1)/2=8\times7/2 条边的完全无向图中,总共有 8 个顶点,再加上 1 个不连通的顶点,共为 9 个顶点。

单项选择题 07

原书题目P202 · 解析P204 · 目视转录

对于一个有 n 个顶点的图:若是连通无向图,其边的个数至少为( );若是强连通有向图,则其边的个数至少为( )。

A. n-1,n

B. n-1,n(n-1)

C. n,n

D. n,n(n-1)

查看答案与解析

答案:A。

对于连通无向图,边最少时构成一棵树的情形;对于强连通有向图,边最少时构成一个有向环的情形。

单项选择题 08

原书题目P202 · 解析P204 · 目视转录

无向图 G 有 23 条边,度为 4 的顶点有 5 个,度为 3 的顶点有 4 个,其余都是度为 2 的顶点,则图 G 有( )个顶点。

A. 11

B. 12

C. 15

D. 16

查看答案与解析

答案:D。

因为在具有 n 个顶点、e 条边的无向图中,有 ∑i=1nTD⁡(vi)=2e\sum_{i=1}^{n}\operatorname{TD}(v_i)=2e,所以求得度为 2 的顶点数为 7,从而共有 16 个顶点。

单项选择题 09

原书题目P202 · 解析P204 · 目视转录

在有 n 个顶点的有向图中,顶点的度最大可达( )。

A. n

B. n-1

C. 2n

D. 2n-2

查看答案与解析

答案:D。

在有向图中,顶点的度等于入度与出度之和。n 个顶点的有向图中,任意一个顶点最多还可以与其他 n-1 个顶点有一对指向相反的边相连。注意,数据结构中仅讨论简单图。

单项选择题 10

原书题目P202 · 解析P204 · 目视转录

具有 6 个顶点的无向图,当有( )条边时能确保是一个连通图。

A. 8

B. 9

C. 10

D. 11

查看答案与解析

答案:D。

5 个顶点构成一个完全无向图,需要 n(n−1)/2=10n(n-1)/2=10 条边,再加上 1 条边后,能保证第 6 个顶点必然与此完全无向图构成一个连通图,所以共需 11 条边。

单项选择题 11

原书题目P202 · 解析P204 · 目视转录

设有无向图 G=(V,E)G=(V,E) 和 G′=(V′,E′)G'=(V',E'),若 G′ 是 G 的生成树,则下列不正确的是( )。

Ⅰ. G′ 为 G 的连通分量

Ⅱ. G′ 为 G 的无环子图

Ⅲ. G′ 为 G 的极小连通子图且 V′=V

A. Ⅰ、Ⅱ

B. 只有Ⅲ

C. Ⅱ、Ⅲ

D. 只有Ⅰ

查看答案与解析

答案:D。

一个连通图的生成树是一个极小连通子图,显然它是无环的,因此选项Ⅱ、Ⅲ正确。极大连通子图称为连通分量,G′ 连通但非连通分量。这里再补充一下“极大连通子图”:若图本来就是连通的,且每个子部分包含其本身的所有顶点和边,则它就是极大连通子图。

单项选择题 12

原书题目P202 · 解析P204 · 目视转录

具有 51 个顶点和 21 条边的无向图的连通分量最多为( )。

A. 33

B. 34

C. 45

D. 32

查看答案与解析

答案:C。

初始考虑只有 51 个顶点的无向图 G,此时 G 中每个顶点都是连通分量,问题转化为向 G 中添加 21 条边,如何添加这 21 条边使得连通分量数目最多。若向两个不同的连通分量之间添加边,则连通分量数目会减 1,所以应尽可能地将这 21 条边加入同一个连通分量且让其接近完全图。含有 7 个顶点的完全图有 21 条边,所以用 7 个顶点构成一个含有 21 条边的连通分量,剩下 51-7=44 个顶点对应 44 个连通分量,共有 45 个连通分量。

单项选择题 13

原书题目P202 · 解析P204 · 目视转录

在如下图所示的有向图中,共有( )个强连通分量。

有向图与强连通分量题图

A. 1

B. 2

C. 3

D. 4

查看答案与解析

答案:B。

强连通分量是极大强连通子图,任意两个顶点之间有方向相反的两条路径。由定义不难得出,若一个顶点只有出边或入边,则该顶点必定单独构成一个连通分量。

图中,顶点 B 只有出边,其他所有顶点都不可能有到顶点 B 的路径,所以顶点 B 单独构成一个强连通分量。在顶点 A、C、D、E 中,任意两个顶点之间都有方向相反的两条路径,所以可构成一个强连通分量。

单项选择题 14

原书题目P203 · 解析P204 · 目视转录

若具有 n 个顶点的图是一个环,则它有( )棵生成树。

A. n2n^2

B. n

C. n-1

D. 1

查看答案与解析

答案:B。

n 个顶点的生成树是具有 n-1 条边的极小连通子图,因为 n 个顶点构成的环共有 n 条边,去掉任意一条边就是一棵生成树,所以共有 n 种情况,所以可以有 n 棵不同的生成树。

单项选择题 15

原书题目P203 · 解析P205 · 目视转录

若一个具有 n 个顶点、e 条边的无向图是一个森林,则该森林中必有( )棵树。

A. n

B. e

C. n-e

D. 1

查看答案与解析

答案:C。

n 个结点的树有 n-1 条边,假设森林中有 x 棵树,将每棵树的根连到一个添加的结点,则成为一棵树,结点数是 n+1,边数是 e+x,从而可知 x=n-e。

【另解】设森林中有 x 棵树,则再用 x-1 条边就可将所有的树连接成一棵树,此时边数+1=顶点数,即 e+(x-1)+1=n,所以 x=n-e。

单项选择题 16

原书题目P203 · 解析P205 · 目视转录

【2009 统考真题】下列关于无向连通图特性的叙述中,正确的是( )。

Ⅰ. 所有顶点的度之和为偶数

Ⅱ. 边数大于顶点个数减 1

Ⅲ. 至少有一个顶点的度为 1

A. 只有Ⅰ

B. 只有Ⅱ

C. Ⅰ和Ⅱ

D. Ⅰ和Ⅲ

查看答案与解析

答案:A。

每条边都连接了两个顶点,在计算顶点的度之和时每条边都被计算了两次,所以所有顶点的度之和为偶数。无向连通图对应的生成树也是无向连通图,但此时边数等于顶点数减 1,选项Ⅱ错误。考虑顶点恰好构成一个环的情况,此时每个顶点的度都是 2,选项Ⅲ错误。

单项选择题 17

原书题目P203 · 解析P205 · 目视转录

【2010 统考真题】若无向图 G=(V,E)G=(V,E) 中含有 7 个顶点,要保证图 G 在任何情况下都是连通的,则需要的边数最少是( )。

A. 6

B. 15

C. 16

D. 21

查看答案与解析

答案:C。

题干要求无论如何分配边,都能使 7 个顶点连通,这不同于只要 6 条边两两相连就能构成一个连通图的情形。考虑最极端的情形,即图 G 的其中 6 个顶点构成一个完全无向图,此时若再添加一条边,则都将连通第 7 个顶点,使该图变成一个连通图。所以最少边数=6×5/2+1=16。若边数 n 小于或等于 15,可以使这 n 条边仅连接图 G 中的某 6 个顶点,从而导致第 7 个顶点无法与 6 个顶点构成连通图(不满足“在任何情况下”)。

为简单起见,以 5 个顶点为例,4 个顶点和 4×3/2=6 条边构成一个完全图,此时若再增加一条连接第 5 个顶点的边,则能保证这 5 个顶点在任何情况下都是连通的;若边数小于 7,则不能保证 5 个顶点在任何情况下都是连通的。

单项选择题 18

原书题目P203 · 解析P205 · 目视转录

【2017 统考真题】已知无向图 G 含有 16 条边,其中度为 4 的顶点个数为 3,度为 3 的顶点个数为 4,其他顶点的度均小于 3。图 G 所含的顶点个数至少是( )。

A. 10

B. 11

C. 13

D. 15

查看答案与解析

答案:B。

无向图边数的 2 倍等于各顶点度数的总和。要求至少的顶点数,应使每个顶点的度取最大,而其他顶点的度均小于 3,因此可以设它们的度都为 2,并设它们的数量是 x,列出方程 4×3+3×4+2x=16×24\times3+3\times4+2x=16\times2,解得 x=4。因此至少包含 4+4+3=11 个顶点。

单项选择题 19

原书题目P203 · 解析P205 · 目视转录

【2022 统考真题】对于无向图 G=(V,E)G=(V,E),下列选项中,正确的是( )。

A. 当 ∣V∣>∣E∣|V|>|E| 时,G 一定是连通的

B. 当 ∣V∣<∣E∣|V|<|E| 时,G 一定是连通的

C. 当 ∣V∣=∣E∣−1|V|=|E|-1 时,G 一定是不连通的

D. 当 ∣V∣>∣E∣+1|V|>|E|+1 时,G 一定是不连通的

查看答案与解析

答案:D。

对于此类分析图的边数、顶点数与连通性问题,思路是寻找临界情况,在临界情况下任意增加或减少一条边,都会改变图的连通性。

第一种临界情况:若减少任意一条边,则图就由连通变为不连通,即无向图连通的最小边数是 ∣V∣−1|V|-1,因此,当 ∣E∣<∣V∣−1|E|<|V|-1 时,一定不连通,选项 C 错误,选项 D 正确。

第二种临界情况:若增加任意一条边,则图就由不连通变为连通,即无向图不连通的最大边数是 (∣V∣−1)(∣V∣−2)/2(|V|-1)(|V|-2)/2(此时 ∣V∣−1|V|-1 个顶点构成一个完全图),因此,仅当 ∣E∣≥(∣V∣−1)(∣V∣−2)/2+1|E|\ge(|V|-1)(|V|-2)/2+1 时才能保证无向图一定连通,选项 A、B 错误。

综合应用题

综合应用题 01

原书题目P203 · 解析P205 · 目视转录

图 G 是一个非连通无向图,共有 28 条边,该图至少有多少个顶点?

查看答案与解析

图 G 是一个非连通无向图,当边数固定时,顶点数最少的情况是该图由两个连通子图构成,且其中之一只含一个顶点,另一个为完全图。其中只含一个顶点的子图没有边,另一个完全图的边数为 n(n−1)/2=28n(n-1)/2=28,得 n=8。所以该图至少有 1+8=9 个顶点。