第七章-图的基本概念答案

第七章 图的基本概念

一、 单项选择题

1. 设V ＝{a,b,c,d},与V 能构成强连通图的边集E ＝(A ) (A) {,,,,} (B) {,,,,}

(C) {,,,,} (D) {,,,,} 2. n 阶无向完全图K n 中的边数为（ A ）

(A)

2)1(-n n (B) 2

)

1(+n n (C) n (D)n(n+1) 3. 给定无向图G 图5－1所示，下面给出的顶点集子集中，不是点割集的为（A ） (A) {b,d} (B) {d} (C) {a,c} (D) {g,e} 4. 下列数组中，不能构成无向图的度数列的数组是( B ) (A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3)

5. 图 中 从v 1到v 3长度为3 的通路有（

4）条。

A ． 0；

B ． 1；

C ． 2；

D ． 3。

v 1到v 3长度为3 的通路: V 1V 3V 1V 3 ; V 1V 1V 1V 3 ; V 1V 4V 1V 3 ; V 1V 1V 4V 3 ; 6．给定无向图>=

A 、},,,{4341><>

B 、},,,{6451><>

C 、

},,,{8474><>

},,,{3221><>

。

7.有向图D=

，则41v v 到长度为2的通路有（ B ）条。

A 、0；

B 、1；

C 、2；

D 、3 。

二、 填空题

1.设有向图D ＝的邻接矩阵为A(D)=⎥⎥⎥⎥⎦

⎤⎢⎢⎢

⎢⎣⎡11

00

10000100

0120

，那么∣E ∣

b f

c e

2. 有16条边，每个顶点都是2度顶点的无向图有 16 个顶点．

3.图G 有21条边,3个4度结点,其余均为3度结点,则G 有__13____个结点. 三、解答题

1. 指出有向图D(如图5－5)中各图是强连通，单侧连通还是弱连通？

强连通图为 (1),(4),(5)；单侧连通图为 (1),(2),(4),(5)

弱连通图为： (1)～(5)

2. 设简单连通无向图G 有12条边，G 中有2个1度结点，2个2度结点，3个4度结点，

3.无向图G 有12条边,G 中有6个3度结点,其余结点度数均小于3,问G 中至少有多少个结点?为什么?

解 设图G 有x 个结点．除6个3度结点外，其余都小于3度，则小于或等于2度，由握手定理，有2×12≤3×6+2×(x －6)，解得x ≥9．故图G 至少有9个结点． 4．若有n 个人，每个人都恰有三个朋友，则n 必为偶数。

证明：将每个人用结点表示，当两个人是朋友时，则对应两结点连一条边，则得一无向图

>=

∈∀=，由任意图

奇数度结点一定是偶数个，可知，此图结点数一定是偶数。

5.有n 个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少

种药品？

解：用n 个结点表示n 个药箱，当两种药箱放一种相同药时，则对应的两点连一条边，则得

第八章 几种特殊图

一、单项选择题

1. 无向完全图K 4是（ B ）

（A ）欧拉图 （B ）哈密顿图 （C ）树 （D ）非平面图 2. 以下各图中存在哈密顿回路的图是 ( C )

(1) (2) (3) (4) (5)

3. 设G 是连通平面图，有v 个结点，e 条边，r 个面，则r= ( A )．

(A) e －v ＋2 (B)v ＋e －2 (C)e －v －2 (D) e ＋v ＋2 4. 无向图G 是欧拉图，当且仅当( C )

(A) G 中所有结点的度数全为偶数 (B) G 中所有结点的度数全为奇数

(C) G 连通且所有结点的度数全为偶数 (D) G 连通且所有结点的度数全为奇数 5、下图中既不是Eular 图，也不是Hamilton 图的图是（ B ）

6.在Peterson 图中，至少填加（ D ）条边才

能构成Euler 图。

A 、1；

B 、2；

C 、4；

D 、5 。

7.下列图中是欧拉图的有( A )。

K n 是欧拉图．K n 存在欧拉

3. 无向连通图G

4.在平面图>=

∑=r

i i

r 1

)deg(,r)是图G 的面．

5. 设图>=

图 的对偶图为 。

7.

三、计算题

1. 在有6个结点，12条边的简单平面连通图中，每个面有几条边围成？为什么？ 6个 解答：图G 中有5个有限面，一个无限面，共6个面．

2. 在图6－4所示的两个图中各有几个面，写出每个面的边界和次数．

解图(a)有5个面：r 0，r 1，r 2，r 3，r 3．r 0的边界：acbda ；r 1的边界：abca ；r 2的边界：bdeb ；r 3的边界：aeda ；r 4的边界：abca ．面次数：)deg(0r ＝4，)deg(1r ＝3，)deg(2r ＝3，)deg(3r ＝3，)deg(4r ＝3．

图(b)有2个面：r 0，r 1．r 0的边界：abcdefcba ；r 1的边界：cdefgfc ．面次数：)deg(0r ＝8，

)deg(1r ＝6．

3 试判断图6－6所示的四个图是否为可平面图．

解在图(a)中，只要改动三条边，就可以得到平面图，如6－7(a)所示．

在图(b)中，只要改动三条边，就可以得到平面图，如6－7(b)所示． 在图(c)中，只要改动三条边，就可以得到平面图，如6－7(c)所示．

故图6－5中(a),(b),(c)都是可平面图．图6－5(d)是无向完全图K 5，它是非平面图．

4．给定三个图如图6－7所示，试判断它们是否 为欧拉图、哈密顿图、或平面图？并说明理由．

d

g

(a ) (c ) 图6－6

c d d (a ) (b ) (d ) 图6－7