离散数学（第五版）清华大学出版社第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

81

由此可知,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.所对应的非同构的图中有简单图,也有非简单图.

82

⑦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

Gn

83

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

G

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

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)

84

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

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

7.12 3阶有向完 …… 此处隐藏：10281字，全部文档内容请下载后查看。喜欢就下载吧 ……