离散数学(第五版)清华大学出版社第7章习题解答

发布时间：2024-11-17

离散数学（第五版）清华大学出版社第7章习题解答

7.1 (1),(2),(3),(5)都能构成无向图的度数列,其中除(5)外又都能构成无向简单图的度数列.

分析1°非负整数列d,d ,L,d 能构成无向图的度数列当且仅当n di为

1 2n∑

i=1偶数,即d1,d2,L,dn中的奇数为偶数个.（1）,(2),(3),(5)中分别有4个,0个,4个,4 个奇数,所以,它们都能构成无向图的度数列,当然,所对应的无向图很可能是非简单图.而(4)中有 3 个奇数,因而它不能构成无向图度数列.否则就违背了握手定理的推论.

2°(5) 虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3 为度数列,不妨设G 中顶点为v1,v2,v3,v4,且d(vi)=1,于是d(v2)=d(v3)=d(v4)=3.而v1只能与v2,v3,v4之一相邻,设v1与v2相邻,这样一来,除v2能达到3度外, v3,v4都达不到3度,这是矛盾的.

在图7.5所示的4个图中,(1) 以1为度数列,(2)以2为度数列,(3)以3为度数列,(4)以4为度数列(非简单图).

7.2 设有几简单图D以2,2,3,3为度数列,对应的顶点分别为v1,v2,v3,v4,由于d(v)=d+(v)+d_(v),所示,d+(v)−d−(v)=2−0=2,d+(v )=d(v )−d−(v )

11222=2−0=2,d+(v)=d(v)−d−(v)=3−2=1,d+(v)=d(v)−d−(v)=3−3=0

333444

由此可知,D 的出度列为2,2,1,0,且满足d+(v)= d−(v).请读者画出

∑i∑i

一个有向图.以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列.

7.3 D 的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2(因为d(v)=d+(v)+d−(v)),)此时,入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知,1,1,1,1也不能为D的出席列.

7.4 不能. N阶无向简单图的最大度Δ≤n−1.而这里的n个正整数彼此不同,因而这n个数不能构成无向简单图的度数列,否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾.

7.5 (1) 16个顶点. 图中边数m=16,设图中的顶点数为n.根据握手定理可知2m=32= n d(v)=2n

∑i

i=1

所以,n=16.

(2) 13个顶点.图中边数m=21,设3度顶点个数为x,由握手定理有

2m=42=3×4+3x

由此方程解出x=10.于是图中顶点数n=3+10=13.

(3) 由握手定理及各顶点度数均相同,寻找方程

2×24=nk

的非负整数解,这里不会出现n,k均为奇数的情况. 其中n为阶级,即顶点数,k为度数共可得到下面10种情况.

①个顶点,度数为48.此图一定是由一个顶点的24个环构成,当然为非简单图.

②2个顶点,每个顶点的度数均为24.这样的图有多种非同构的情况,一定为非简单图.

③3个顶点,每个顶点的度数均为16.所地应的图也都是非简单图.

④4个顶点,每个顶点的度数均为12. 所对应的图也都是非简单图.

⑤6个顶点，每个顶点的度数均为8，所对应的图也都是非简单图.

⑥个顶点,每个顶点的度数均为 6.所对应的非同构的图中有简单图,也有非简单图.

⑦12 个顶点,每个顶点的度数均为 4. 所对应的非同构的图中有简单图,也有非简单图.

⑧16个顶点,每个顶点的度数均为3,所对应的非同构的图中有简单图,也有非简单图.

⑨24个顶点,每个顶点的度数均为2.所对应的非同构的图中有简单图,也有非简单图.

⑩48个顶点,每个顶点的度数均为1,所对应的图是唯一的,即由24个K2构成的简单图.

分析由于n阶无向简单图G中,ΔG( )≤n−1,的以①-⑤所对应的图不可能有简单图.⑥-⑨既有简单图,也有非简单图,读者可以画出若干个非同构的图,而⑩只能为简单图.

7.6 设G为n阶图,由握手定理可知

70=2×35= n d(v)≥3n,

∑ 1

i=1

所以,

⎢70⎥

n≤=23.

⎢3⎥

⎣⎦

⎢70⎥

这里, ⎣x⎦为不大于x的最大整数,例如⎣2⎦=2,⎣2.5⎦=2,=23 .

⎢3⎥

⎣⎦

7.7 由于δ(G)=n−1,说明G 中任何顶点v的度数d(v)≥δ(G)=n−1,可是由于G 为简单图,因而ΔG( )≤n−1,这又使得d(v)≤n−1,于是d(v)=n−1,也就是说,G中每个顶点的度数都是n−1,因而应有ΔG( )≤n−1.于是G为(n−1)阶正则图,即G为n阶完全图Kn.

7.8 由G的补图G的定义可知,GUG为Kn,由于n为奇数,所以, Kn中各项顶点的度数n−1为偶数.对于任意的v∈V(G),应有v∈V(G),且

dG(v)_d (v)=dK (v)=n−1

其中dG(v)表示v在G中的度数, d (v)表示v在G中的度数.由于n−1为偶

数,所以, dG(v)与d (v)同为奇数或同为偶数,因而若G有r个奇度顶点,则G也

有r个奇度顶点.

7.9 由于D'⊆D,所以,m'≤m.而n阶有向简单图中,边数m≤n(n−1),所以,应有

n(n−1)=m'≤m≤n(n−1)

这就导致m=n(n−1),这说明D为n阶完全图,且D'=D.

7.10 图7.6给出了K4的18个非同构的子图,其中有11个生成子图(8-18),其中连通的有6个11,12,13,14,16,17).图7.6中,n,m分别为顶点数和边数.

7.11 K4有11个生成子图,在图7.6中,它们分别如图8-18所示.要判断它们之中哪些是自补图,首先要知道同构图的性质,设G1与G2的顶点数和边数.若G1≅G2,则n1=n2且m1=m2.

(8)的补图为(14)=K4,它们的边数不同,所以,不可能同构.因而(8)与(14)

均不是自补图类似地,(9)的补图为(13),它们也非同构,因而它们也都不是自补图.(10)与(12)互为补图,它们非同构,因而它们都不是自补图.(15)与(17)互为补图,它们非同构,所以,它们都不是自补图.类似地,(16)与(18)互为补图且非同构,所以,它们也都不是自补图.

而(11)与自己的补图同构,所以,(11)是自补图.

7.12 3阶有向完全图共有20个非同构的子图,见图7.7所示,其中(5)-(20)为生成子图,生成子图中(8),(13),(16),(19)均为自补图.

分析在图7.7所示的生成子图中, (5)与(11)互为补图,(6)与(10)互为补图,(7)与(9)互为补图,(12)与(14)互为补图,(15)与(17)互为补图,(18)与(20)互为补图,以上互为补图的两个图边数均不相同,所以,它们都不是自补图.而(8),(13),(16),(19)4个图都与自己的补图同构,所以,它们都是自补图.

7.13 不能.

分析在同构的意义下,G1,G2,G3都中K4的子图,而且都是成子图.而K4的两条边的生成子图中,只有两个是非同构的,见图7.6 中(10)与(15)所示.由鸽巢原理可知, G1,G2,G3中至少有两个是同构的,因而它们不可能彼此都非同构.

鸽巢原理m只鸽飞进n个鸽巢,其中m≥n,则至少存在一巢飞入至少[m]只

n鸽子.这里⎡x⎤表示不小于x的最小整数.例如, ⎡2⎤=2,⎡2.5⎤=3.

7.14 G是唯一的,即使G是简单图也不唯一.

分析由握手定理可知2m=3n,又由给的条件得联立议程组

⎧2m=3n

⎨2n−3=m.

⎩

解出n=6,m=9.6个顶点,9条边,每个顶点的度数都是3的图有多种非同构的情况,其中有多个非简单图(带平行边或环),有两个非同构的简单图,在图7.8中(1),(2)给出了这两个非同构的简单图.

满足条件的非同构的简单图只有图7.8

中,(1),(2)所示的图,(1)与(2)所示的图,(1)

与(2)是非同构的.

注意在(1)中不存在3个彼此相邻的顶点,

而在(2)中存在3个彼此相邻的顶点,因而(1)

图与(2)图非同构.下面分析满足条件的简单

图只有两个是非同构的.首先注意到(1)中与

(2)中图都是K6的生成子图,并且还有这样

的事实,设G1,G2都是n 阶简单图,则G1≅G2当且仅当G1≅G2,其中G1,G2分别为G1与G2的补图.满足要求的简单图都是6阶9条边的3正则图,因而它们的补图都为6阶6条边的2正则图(即每个顶点度数都是2).而K6的所有生成子图中,6条边2正则的非同构的图只有两个,见图7.8中(3),(4)所示的图,其中(3)为(1)的补图,(4)为(2)的补图,满足要求的非同构的简单图只有两个.

但满足要求的非同简单图有多个非同构的,读者可自己画出多个来.

7.15 将K6的顶点标定顺序,讨论v1所关联的边.由鸽巢原理(见7.13 题),与v1关联的5条边中至少有3条边颜色相同,不妨设存在3条红色边,见图7.9中(1)所示(用实线表示红色的边)并设它们关联另外3个顶点分别为v2,v4,v6.若v2,v4,v6构成的K3中还有红色边,比如边(v2,v4)为红色,则v1,v2,v4构成的K3为红色K3,见图7.9中(2)所示.若v2,v4,v6构成的K3各边都是蓝色(用虚线表示),则v2,v4,v6构成的K3为蓝色的.

7.16 在图7.10 所示的3个图中,(1)为强连通图,(2)为单向连通图,但不是强连通

的,(3)是弱连通的,不是单向连通的,更不是强连通的.

分析在(1)中任何两个顶点之间都有通路,即任何两个顶点都是相互可达的,因而它是强连能的.(2)中c不可达任何顶点,因而它不是强连通的,但任两个顶点存在一个顶点可达另外一个顶点,所以,它是单向可达的.(3)中a,c互相均不可达,因而它不是单向连通的,更不是强连通的.

判断有向图的连通性有下面的两个判别法.

1°有向图D是强连通的当且仅当D中存在经过每个顶点至少一次的回路.

2°有向图D是单向连通的当且仅当D中存在经过每个顶点至少一次的通路. (1) 中abcda为经过每个顶点一次的回路,所以,它是强连能的.(2)中abdc为经过每个顶点的通路,所以,它是单向连通的,但没有经过每个顶点的回路,所以,它不是强连通的.(3)中无经过每个顶点的回路,也无经过每个顶点的通路,所以,它只能是弱连通的.

7.17 G−E的连通分支一定为2,而G−V''的连通分支数是不确定的.

分析设E为连通图G的边割集,则G−E的连通分支数p(G−E)=2,不可'''

能大于2.否则,比如p(G−E)=3,则G−E由3个小图G,G'',G 组成,且E中边'

1 2 3

的两个端点分属于两个不同的小图.设E''中的边的两个端点一个在G 中,另一个1

在G 中,则E''⊂E',易知p(G−E'')=2,这与E'为边割集矛盾,所以,

p(G−E'')=2.

但p(G−V')不是定数,当然它大于等于2,在图7.11中,V'={u,v}为(1)的点割集, p(G−V)=2,其中'G 为(1)中图. V''={v}为(2)中图的点割集,且v为割点, p(G'−V'')=4,其中G为(2)中图.'

7.18 解此题,只要求出D的邻接矩阵的前4次幂即可.

⎡0 1 1 0⎤⎡1 1 0 1⎤

1 0 0 020 1 1 0

A=⎢⎥A =⎢⎥

⎢0 1 0 1⎥⎢1 0 0 1⎥

⎢0 0 0 0⎥⎢0 0 0 1⎥

⎣⎦⎣⎦

⎡1 1 1 1⎤⎡1 2 1 2⎤

3 1 1 0 1

4 1 1 1 1

A =⎢⎥A =⎢⎥

⎢0 1 1 1⎥⎢1 1 0 1⎥

⎢0 0 0 1⎥⎢0 0 0 1⎥

⎣⎦⎣⎦

D中长度为4的通路数为A4中元素之和,等于15,其中对角线上元素之和为3,即D中长度为3的回路数为3.v 到v 的长度为4的通路数等于a(4)=2.

3434

分析用邻接矩阵的幂求有向图D中的通路数和回路数应该注意以下几点:

1°这里所谈通路或回路是定义意义下的,不是同构意义下的.比如,不同始点(终点)的回路

2°这里的通路或回路不但有初级的、简单的，还有复杂的.例如,v1,v2,v1,v2,v1是一条长为4的复杂回路.

3°回路仍然看成是通路的特殊情况.

读者可利用A2,A3,求D中长度为2和3的通路和回路数.

7.19 答案A:④.

分析G中有Nk个k度顶点,有(n−Nk)个(k+1)度顶点,由握手定理可知

n d(v)=k⋅N +(k+1)(n−N )=2m

∑ikk

i=1

⇒Nk=n(k+1)−2n .

7.20 答案A:②; B:③.

分析在图7.12中,图(1)与它的补同构,再没有与图(1)非同构的自补图了,所以非同构的无向的4阶自补图只有1个.图(2)与它的补同构,图(3)与它的补也同构,而图(2)与图(3)不同构,再没有与(2),(3)非同构的自补图了,所以,非同械的5阶自补图有

2个.

7.21 答案A:④; B:③; C:④; D:①.

分析(1)中存在经过每个顶点的回路,如adcba.(2)中存在经过每个顶点.

的通路,但无回路.(3)中无经过每个顶点至少一次的通路,其实,b,d两个顶点互不可达.(4)中有经过每个顶点至少一次的通路,但无回路,aedcbd为经过每个顶点的通路.(5)中存在经过每个顶点至少一次的回路,如aedbcdba(6)中也存在经.

过每个顶点的回路,如baebdcb.由7.16 题可知,(1),(5),(6)是强连通的,(1),(2),(4),(5),(6)是单向连能的,(2),(4)是非强连通的单向连通图.注意,强连通图必为单向连通图.6 个图中,只有(3)既不是强连通的,也不是连通的,它只是弱连通图.

在(3)中,从a到b无通路,所以d,<a,b>=∞,而b到a有唯一的通路ba,所以d<b,a>=1.

7.22 答案A:①; B:⑥㈩C:②; D:④.

分析用Dijkstra标号法,将计算机结果列在表7.1中.表中第x列最后标定y/Z表示b到x的最短路径的权为y,且在b到x的最短路径上,Z邻接到x, 即x的前驱元为Z.由表7.1可知,a的前驱元为c(即a邻接到c),c的前驱元为b,所以,b到a的最短路径为bca,其权为4.类似地计论可知,b到c的最短路径为bc,其权为1.b到d 的最短路径为bcegd,其权为9.b到e 的最短路径为bce,其权为7.

表7.1

顶点a b c d e f g

0 7 1∞ ∞ ∞ ∞

1 4 ∞ 5 4∞

1/b

2 12 5 4∞

4/c

3 12 5 4/c11

4 12 5/c7

5 97/e

69/g

4 01 9

5 4 7

7.23 答案A:⑧; B:⑩C:③; D:③和④.

分析按求最早、最晚完成时间的公式，先求各顶点的最早完成时间，再求最晚完成时间，最后求缓冲时间。

（1）最早完成时间：

TE(v1)=0

Γ−(v )={v,v}, TE(v )=max{0+3}=3

21 22

Γ−(v )={v,v}, TE(v )=max{0+2,3+0}=3

31 33

Γ−(v )={v,v}, TE(v )=max{0+4,3+2}=5

41 34

Γ−(v )={v ,v}, TE(v )=max{3+4,3+4}=7

52 35

Γ−(v )={v ,v}, TE(v )=max{3+4,7+0}=7

63 66

Γ−(v )={v ,v}, TE(v)=max{5+5,10+0}=10

74 57

Γ−(v )={v,v}, TE(v)=max{7+3,10+1}=11

86 78

Γ−(v )={v ,v}, TE(v )=max{7+6,11+1}=13

95 89

（2）最晚完成时间：

TL(v9)=13

Γ+(v )={v}, TL(v )=min{13−1}=12;

898

Γ+(v )={v}, TL(v )=min{12−3}=9;

686

Γ+(v )={v}, TL(v )=min{12−1}=11;

787

Γ+(v )={v ,v},TL(v )=min{9−0,13−6}=7;

56 95

Γ+(v )={v},TL(v )=min{11−5=6;

474

Γ+(v )={v ,v ,v}, TL(v )=min{6−2.7−4.9−4=5;

34 5 63

Γ+(v )={v,v}, TL(v )=min{3−0.7−4}=3;

23 52

Γ+(v)={v ,v ,v}, TL(v)=min{3−3.3−2,6−4}=0;

12 3 41

（3）缓冲时间：

TS(v1)=TS(v2)=TS(v3)=TS(v5)=TS(v9)=0

TS(v4)=1,TS(v6)=2,TS(v7)=TS(v8)=1.

（4）关键路径有两条：v1,v2,v5,v9和v1,v2,v3,v5,v9.

第8 章习题解答

8.1 图8.6 中,(1)所示的图为K1,3,(2) 所示的图为K2,3,(3)所示的图为K2,2,它们分别各有不同的同构形式.

8.2 若G为零图,用一种颜色就够了,若G是非零图的二部图,用两种颜色就够了. 分析根据二部图的定义可知,n 阶零图(无边的图)是三部图(含平凡图),对n阶零图的每个顶点都用同一种颜色染色,因为无边,所以,不会出现相邻顶点染同色,因而一种颜色就够用了.

8.3 完全二部图Kr,s,中的边数m−rs.

分析设完全二部图Kr,s的顶点集为V, 则V=V1UV2,V1IV2=∅,且|V1|=r,|V2|=s, Kr,s是简单图,且V1中每个顶点与V2中所有顶点相邻,而且V1中任何两个不同顶点关联的边互不相同,所以,边数m−rs.

8.4 完全二部图Kr,s中匹配数β1=min{r,s},即β1等于r,s中的小者.

分析不妨设r≤s,且二部图Kr,s中,|V1|=r,|V2|=s,由Hall定理可知,图中存在V1到的完备匹配,设M 为一个完备匹配,则V1中顶点全为M 饱和点,所以,β1=r.

8.5 能安排多种方案,使每个工人去完成一项他们各自能胜任的任务.

分析设V1={甲,乙,丙},则V1为工人集合, V2={a,b,c},则V2为任务集合.

令V=V1UV2,E={(x,y)|x能胜任y},得无向图G=<V,E>,则G 为二部图,见图8.7 所示.本题是求图中完美匹配问题. 给图中一个完美匹配就

对应一个分配方案.图8.7 满足Hall定理中的相异性条件,所以,

存在完备匹配,又因为|V1|=V2| |=3,所以,完备匹配也为完美匹配.

其实,从图上,可以找到多个完美匹配. 取

M1={(甲,a),(乙,b),(丙,c)}

此匹配对应的方案为甲完成a,乙完成b, 丙完成c,见图中粗边所示的匹配.

M ={(甲,b),(乙,a),(丙,c)}

M2对应的分配方案为甲完成b,乙完成a,丙完成c.

请读者再找出其余的分配方案.

8.6 本题的答案太多,如果不限定画出的图为简单图,非常容易地给出 4 族图分别满足要求.

(1) n (n 为偶数,且n≥2)阶圈都是偶数个顶点,偶数条边的欧拉图.

(2) n (n 为奇数,且n≥1)阶圈都是奇数个顶点,奇数条边的欧拉图.

(3) 在(1) 中的圈上任选一个顶点,在此顶点处加一个环,所务图为奇数个顶点,偶数条边的欧拉图.

分析上面给出的4族图都是连通的,并且所有顶点的度数都是偶数,所以,都是欧拉图.并且(1),(2) 中的图都是简单图.而(3),(4)中的图都带环,因而都是非简单图. 于是,如果要求所给出的图必须是简单图,则(3),(4)中的图不满足要求.

其实,欧拉图是若干个边不重的图的并,由这种性质,同样可以得到满足(3),(4)中要求的简单欧拉图.设G1,G2,L,Gk是长度大于等于3的k个奇圈(长度为奇数的圈称为奇圈),其中k为偶数,将G1中某个顶点与G2中的某顶点重合,但边不重合, G2中某顶点与G3中某顶点重合,但边不重合,继续地,最后将Gk−1中某顶点与Gk中某顶点重合,边不重合,设最后得连通图为G,则G中有奇数个顶点,偶数条边,且所

有顶点度数均为偶数,所以,这样的一族图满足(4)的要求,其中一

个特例为图8.8中(1)所示.在以上各图中,若G1,G2,L,Gk中有一个偶圈,其他条件不变,构造方法同上,则所得图G 为偶数个顶点,奇数条边的简单欧拉图,满足(3)的要求,图8.8中(2)所示为一个特殊的情况.

8.7 本题的讨论类似于8.6 题,只是将所有无向圈全变成有向圈即可,请读者自己画出满足要求的一些特殊有向欧拉图.

8.8 本题的答案也是很多的,这里给出满足要求的最简单一些图案,而且全为简单图.

(1) n(n≥3)阶圈,它们都是欧拉图,又都是哈密尔顿图.

(2) 给定k(k≥2)个长度大于等于3的初级回路,即圈G1,G2,L,Gk,用8.6题方法构造的图G均为欧拉图,但都不是哈密尔顿图,图8.8给出的两个图是这里的特例.

(3)n(n≥4)阶圈中,找两个不相邻的顶点,在它们之间加一条边,所得图均为哈密尔顿图,但都不是欧拉图.

(4) 在(2)中的图中,设存在长度大于等于4的圈,比如说G1,在G1中找两个不相邻的相邻顶点,在它们之间加一条新边,然

后用8.6题方法构造图G,则G既不是欧拉图,

也不是哈密尔顿图,见图8.9所示的图.

分析(1) 中图满足要求是显然的.(2)

中构造的图G 是连通的,并且各顶点度数均为偶数,所以,都是欧拉图,但因为G 中存在割点,将割点从G中删除,所得图至少有两个连通分支,这破坏了哈密尔顿图的必要条件,所以,G 不是哈密尔顿图.(3) 中构造的图中,所有顶点都排在一个圈上,所以,图中存在哈密尔顿回路,因而为哈密尔顿图,但因图中有奇度顶点(度数为奇数的顶点),所以,不是欧拉图. 由以上讨论可知,(4) 中图既不是欧拉

图,也不是哈密尔顿图.

其实,读者可以找许多族图,分别满足题中的要求.

8.9 请读者自己讨论.

8.10 其逆命题不真.

分析若D是强连通的有向图,则D中任何两个顶点都是相互可达的,但并没有要求D中每个顶点的入度都等于出度. 在图8.2 所示的3个强连通的有向衅都不是欧拉图.

8.11 除K2不是哈密尔顿图之外, Kn(n≥3)全是哈密尔顿图. Kn(n 为奇数)为欧拉图. 规定K1(平凡图)既是欧拉图,又是哈密尔顿图.

分析从哈密尔顿图的定义不难看出,n阶图G是否为哈密尔顿图,就看是否能将G中的所有顶点排在G中的一个长为n的初级回路,即圈上. Kn(n≥3)中存在多个这样的生成圈(含所有顶点的图), 所以Kn(n≥3)都是哈密尔顿图.

在完全图Kn中,各顶点的度数均为n-1,若Kn为欧拉图,则必有n−1为偶数,即n 为奇数,于是,当n为奇数时, Kn连通且无度顶点,所以, Kn(n为奇数) 都是欧拉图.当n为偶数时,各顶点的度数均为奇数,当然不是欧拉图.

8.12 有割点的图也可以为欧拉图.

分析无向图G为欧拉图当且仅当G连通且没有奇度顶点.只要G连通且无奇度顶点(割点的度数也为偶数),G就是欧拉图.图8.8所示的两个图都有割点,但它们都是欧拉图.

8.13 将7个人排座在圆桌周围,其排法为abdfgeca .

分析做无向图G=<V,E>,其中,

V={a,b,c,d,e,f,g}

E={(u,v)|u,v∈V且u与v有共同语言}

图G为图8.10所示.图G是连通图,于是,能否将这7个人排座在圆桌周围,使得每个人能与两边的人交谈,就转化成了图G 中是否存在哈密尔顿回路(也就是G是否为哈密尔顿图).通过观察发现G中存在哈密尔顿回路, abdfgeca就是其

中的一条哈密尔顿回路.

8.14 用vi表示颜色i,i=1,2,L,6.做无向图G=<V,E>,其中

V={v1,v2,v3,v4,v5,v6},

E={(u,v)|u,v∈V且u≠v,并且u与v能搭配}.

对于任意的v∈V,d(v)表示顶点v与别的能搭配的颜色个数,易知G是简单图,且对于任意的u,v∈V,均有d(u)+d(v)≥3+3=6,由定理8.9可知,G为哈密尔顿图,因而G

中存在哈密尔顿回路,不妨设vi vivivivivivi 为其中的一条,在这种回

1 2 3 4 5 6 1

路上,每个顶点工表的颜色都能与它相邻顶点代表的颜色相.于是,让vi与vi ,vi 12 3与vi ,vi与vi所代表的颜色相搭配就能织出3种双色布,包含了6种颜色.

4 56

8.15

deg(R)=4,deg(R )=1,deg(R )=3,而deg(R )=12.3 deg(R)=20=2×10,本图边

1230∑i

i=0

数m=10.

分析平面图(平面嵌入)的面Ri的次数等于包围它的边界的回路的长度,这里所说回路,可能是初级的,可能是简单的,也可能是复杂的,还可能由若干个回路组成.图8.1所示图中,R1,R2,R3的边界都是初级回路,而R0的边界为复杂回路(有的边在回路中重复出现),即e1e2e3e4e5e6e7e8e9e10e1e2e3e4,长度为12,其中边e5,e6在其中各出现两次.

8.16 图8.11中,实线边所示的图为图8.1中图G,虚线边,实心点图为它的

对偶图的顶点数n*,边数m*,面数r*分别为4,10和8,于是有

分析从图8.11还可以发现,G的每个顶点位于的一个面中,且的每个面只含G的一个顶点,所以,这是连通平面图G是具有k个连通分支的平面图k≥2,则应有r*=n−k+1.读者自己给出一个非连通的平面图,求出它的对偶图来验证这个结论.另外,用图8.1还可以验证,对于任意的v*(G*中的顶点),若它处于G的面R中,则应有d(v)=deg(R).*

8.17 不能与G同构.

分析任意平面图的对偶图都是连通的,因而与都是连通图,而G 是具有3个连通分支的非连通图,连通图与非连通图显然是不能同构的.

图8.12 中, 这线边图为图8.2中的图G,虚线边图为G的对偶图,带小杠的

***~

边组成的图是G 的对偶图,显然G ≠G.

8.18 因为彼得森图中有长度为奇数的圈,根据定理8.1可知它不是二部图.图中每个顶点的度数均为3,由定8.5 可知它不是欧拉图.又因为它可以收缩成K5,由库拉图期基定理可知它也不是平面图.

其实,彼得森图也不是哈密尔顿图图,这里就不给出证明了.

8.19 将图8.4重画在图8.13中,并且将顶点标定.图中afbdcea为图中哈密尔顿回路,见图中粗边所示,所以,该图为哈密尔顿图.

将图中边(d,e),(e,f),(f,d)三条去掉,所得图为原来图的子图,它为K3,3,可取V1={a,b,c} V2={d,e,f},由库拉图期基定理可知,该图不是平面图.

8.20 图8.14 所示图为图8.5所示图的平面嵌入.

分析该图为极大平面图.此图G中,顶点数n=9,边数m=12若G是不是极.

大平面图,则应该存在不相邻的顶点u,v,在它们之间再加一条边所得G'还应该是简单平面图, G'的顶点数n'=n=6,m'=n+1=13,于是会有

m'=13>3n−6=12. '

这与定理8.16矛盾,所以,G为极大平面图.

其实,n( n≥3)阶简单平面图G为极大平面图当且仅当G的每个面的次数均为3.由图8.14可知,G的每个面的次数均为3,所以,G为极大平面图.

8.12 答案A,B,C,D全为②

分析(1) 只有n为奇数时命题为真,见8.11的解答与分析.

(2) n≠2时,命题为真,见8.11的解答与分析.

(3) 只有n,m都是偶数时,Kn,m中才无奇度数顶点,因而Kn,m为欧拉图,其他情况下,即n,m中至少有一个是奇数,这时Kn,m中必有奇度顶点,因而不是欧拉图. (4) 只有n=m时, Kn,m中存在哈密尔顿回路,因而为哈密尔顿图.

当n≠m时,不妨设n<m ,并且在二部图Kn,m中,|V1|=n,|V2|=m ,则p(G−V1)=m>|V1|=n,这与定理8.8矛盾. 所以, n≠m时, Kn,m不是哈密尔顿

图.

8.22 答案A:②;B②;C②.

分析

图8.15中,两个实边图是同构的,但它们的对偶力(虚边图)是不同构的.

(2) 任何平面图的对偶图都是连通图.设G 是非连通的平面图,显然有~ **

G≠G .

(3) 当G是非连通的平面图时,r*=n−k+1,其中k为G的连通分支数.

8.23 答案A:④;B②;C②.

分析根据库期基定理可知,所求的图必含有K5或K3,3同胚子图,或含可收缩成K5或K3,3的子图.由于顶点数和边数均已限定,因而由K3,3加2 条边的图可满足要求,由K5增加一个顶点,一条边的图可满足要求,将所有的非同构的简单图画出来,共有4个,其中由K3,3产生的有2个,由K5产生的有2个.见图8.16所示.

第9章习题解答

9.1 有5片树叶.

分析设T有x个1度顶点(即树叶).则T的顶点数n=3+2+x=5+x,T的边数m=n−1=4+x.由握手定理得方程.

2m=2(4+x)= n d(v)=3×3+2×2+1⋅x=13+x.

∑ i

i=1

由方程解出x=5.

所求无向树T的度数列为1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图9.6给出的4棵都具有上述度数列,且它们是非同构的.

9.2 T中有5个3度顶点.

分析设T中有x个3度顶点,则T中的顶点数n=7+x,边数m=n−1=6+x,由握手定理得方程.

2m=12+2x= n d(v)=3x+7

∑i