离散数学（第五版）清华大学出版社第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=033344481由此可知,D 的出度列为2,2,1,0,且满足d+(v)= d-(v).请读者画出∑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=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,∑　1i=1所以,?70?n≤=23.?3????70?这里, ?x?为不大于x的最大整数,例如?2?=2,?2.5?=2,=23 .?3???可是由于G 为7.7 由于δ(G)=n-1,说明G 中任何顶点v的度数d(v)≥δ(G)=n-1,简单图,因而Δ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-1Gn83其中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阶有向完全图共有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为蓝色的.867.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 中,另一个187在G 中,则E''?E',易知p(G-E'')=2,这与E'为边割集矛盾,所以,2p(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 0A=??A =???0 0 0 0??0 0 0 1??????1 1 1 1??1 2 1 2?3 1 1 0 14 1 1 1 1A =??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°回路仍然看成是通路的特殊情况.88读者可利用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∑ikki=1?Nk=n(k+1)-2n .7.20 答案A:②; B:③.分析在图7.12中,图(1)与它的补同构,再没有与图(1)非同构的自补图了,所以非同构的无向的4阶自补图只有1个.图(2)与它的补同构,图(3)与它的补也同构,而图(2)与图(3)不同构,再没有与(2),(3)非同构的自补图了,所以,非同械的5阶自补图有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)既不是强连通的,也不是连通的,它只是弱连通图.而b到a有唯一的通路ba,所以d<b,a>=1. 在(3)中,从a到b无通路,所以d,<a,b>=∞，7.22 答案A:①; B:⑥㈩C:②; D:④.89分析用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 gk0 7 1∞∞∞∞1 4 ∞ 5 4∞1/b2 12 5 4∞4/c3 12 5 4/c114 12 5/c74 01 95 4 77.23 答案A:⑧; B:⑩C:③; D:③和④.分析按求最早、最晚完成时间的公式，先求各顶点的最早完成时间，再求最晚完成时间，最后求缓冲时间。