第7章 习题解答
7.1 (1),(2),(3),(5)都能构成无向图的度数列,其中除(5)外又都能构成无向简单图的度数列.
分析 1° 非负整数列d1,d2,?,dn能构成无向图的度数列当且仅当?di为
i?1n偶数,即d1,d2,?,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?(v1)?d?(v1)?2?0?2,d?(v2)?d(v2)?d?(v2)
?2?0?2,d?(v3)?d(v3)?d?(v3)?3?2?1,d?(v4)?d(v4)?d?(v4)?3?3?0
1 / 11
由此可知,D的出度列为2,2,1,0,且满足?d?(vi)??d?(vi).请读者画出一个有向图.以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??d(vi)?2n
i?1n所以,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.所对应的非同构的图中有简单图,也有非简单图.
2 / 11
⑦12个顶点,每个顶点的度数均为4. 所对应的非同构的图中有简单图,也有非简单图.
⑧16个顶点,每个顶点的度数均为3,所对应的非同构的图中有简单图,也有非简单图.
⑨24个顶点,每个顶点的度数均为2.所对应的非同构的图中有简单图,也有非简单图.
⑩48个顶点,每个顶点的度数均为1,所对应的图是唯一的,即由24个K2构成的简单图.
分析 由于n阶无向简单图G中,?(G)?n?1,的以①-⑤所对应的图不可能有简单图.⑥-⑨既有简单图,也有非简单图,读者可以画出若干个非同构的图,而⑩只能为简单图.
7.6 设G为n阶图,由握手定理可知
70?2?35??d(v1)?3n,
i?1n所以,
?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的定义可知,G?G为Kn,由于n为奇数,所以, Kn中各项顶点的度数n?1为偶数.对于任意的v?V(G),应有v?V(G),且
dG(v)_dG(v)?dKn(v)?n?1
3 / 11
离散数学7习题解答
