离散数学习题解答

离散数学~习题1.11.下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。

⑴中国有四大发明。

⑵计算机有空吗?⑶不存在最大素数。

⑷21+3＜5。

⑸老王是山东人或河北人。

⑹2与3都是偶数。

⑺小李在宿舍里。

⑻这朵玫瑰花多美丽呀!⑼请勿随地吐痰!⑽圆的面积等于半径的平方乘以 。

⑾只有6是偶数，3才能是2的倍数。

⑿雪是黑色的当且仅当太阳从东方升起。

⒀如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。

2. 将下列复合命题分成若干原子命题。

⑴李辛与李末是兄弟。

⑵因为天气冷，所以我穿了羽绒服。

⑶天正在下雨或湿度很高。

⑷刘英与李进上山。

⑸王强与刘威都学过法语。

⑹如果你不看电影，那么我也不看电影。

⑺我既不看电视也不外出，我在睡觉。

⑻除非天下大雨，否则他不乘班车上班。

解：⑴本命题为原子命题；⑵p：天气冷；q：我穿羽绒服；⑶p：天在下雨；q：湿度很高；⑷p：刘英上山；q：李进上山；⑸p：王强学过法语；q：刘威学过法语；⑹p：你看电影；q：我看电影；⑺p：我看电视；q：我外出；r：我睡觉；⑻p：天下大雨；q：他乘班车上班。

3. 将下列命题符号化。

⑴他一面吃饭，一面听音乐。

⑵3是素数或2是素数。

⑶若地球上没有树木，则人类不能生存。

⑷8是偶数的充分必要条件是8能被3整除。

⑸停机的原因在于语法错误或程序错误。

⑹四边形ABCD是平行四边形当且仅当它的对边平行。

⑺如果a和b是偶数，则a+b是偶数。

解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q⑵p：3是素数；q：2是素数；原命题符号化为：p∨q⑶p：地球上有树木；q：人类能生存；原命题符号化为：⌝p→⌝q⑷p：8是偶数；q：8能被3整除；原命题符号化为：p↔q⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：p↔q。

1.1 命题及其表示法1.下列陈述句中，（）不是命题。

A.2013年国庆节是星期天。

B.火星上有生物。

C.月球距离地球近。

D.上海是大城市。

2.下列命题中，（）是复合命题。

A.江山代有人才出。

B.我花开时百花杀。

C.春江水暖鸭先知。

D.万紫千红总是春。

3.下列命题中，（）是原子命题。

A.燕子飞回南方，春天来了。

B.天才是炼成的，而不是天生的。

C.暮春三月，江南草长。

D.哥白尼指出地球绕太阳转。

4.下列命题中，（）是原子命题。

A.王芳与王菲是姐妹。

B.王芳与王菲是三好学生。

C.王芳与王菲持有驾照。

D.王芳与王菲喜欢早睡早起。

5.下列命题中，（）是原子命题。

A.数学是科学的皇后，而数论是数学的皇后。

B.数学使人精细，逻辑使人善辩。

C.较大的偶数都可表示为两个素数的和。

D.数学是一种语言，也是一种工具。

6.判断一个语句是否为命题，首先看它是否为陈述句，然后再看它是否具有唯一的真值。

1.C2.B3.D4.A5.C6.陈述句，真值1.2 命题联结词1.命题“如果我休假，我将去美丽的黄山旅游。

”的否定可表示为2.命题“每个学生都要考试。

”的否定可表示为3.命题“1既不是素数也不是合数。

”的否定可表示为4.命题“如果我是你，那么太阳从西边出。

”的真值为5.命题“如果时间倒流，那么我们将长生不老。

”的真值为6.命题“2是偶数或3是奇数。

”的否定可表示为（）。

A.2不是偶数或3不是奇数。

B.2不是偶数且3不是奇数。

C.2不是偶数或3是奇数。

D.2不是偶数且3是奇数。

7.设P:中国地处亚洲。

Q:大熊猫产在中国。

R:太阳从西边升起。

求下列复合命题的真值。

（1）(P↔Q)→R（2）（R→(P∧Q))↔┐P（3）┐R→(┐P∨┐Q∨R)（4）(┐P↑Q)↓(Q↑┐R)8.命题“我善良、正直、勤奋、感恩、有责任、有尊严，所以我幸福。

”的否定可表述。

1.我休假且我不将去美丽的黄山旅游。

2.有的学生不要考试。

3.1是素数或合数。

第7章习题解答7.1 (1),(2),(3),(5) 都能构成无向图的度数列,其中除⑸ 外又都能构成无向简单图的度数列.n 分析1 °非负整数列d!,d2,…，d n能构成无向图的度数列当且仅当di为i 4偶数,即d!,d2,…，d n中的奇数为偶数个.(1),(2),(3),(5) 中分别有4个,0个,4 个,4个奇数，所以，它们都能构成无向图的度数列，当然，所对应的无向图很可能是非简单图.而⑷中有3个奇数，因而它不能构成无向图度数列.否则就违背了握手定理的推论.2° (5)虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3 为度数列,不妨设G中顶点为v! ,v2, v3,v4,且d(V i) =1,于是d(V2)=d(V3)=d(V4)=3.而V!只能与v?""之一相邻,设w 与v?相邻，这样一来，除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 (vj - d -(y) = 2 - 0 = 2,d(V2) = d(V2)-d “2)= 2—0 =2,d (vj =d(V s) _d—(V3) =3_2 =1,d (V4) = d(V q) _ d^v。

)= 3 _ 3 = 0由此可知，D 的出度列为2,2,1,0,且满足a dd -(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.根据握手定理可n知 2m =32 二' d(vj=2 ni 4所以，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个环构成，当然为非简单⑥ 个顶点，每个顶点的度数均为6.所对应的非同构的图中有简单图，也有非 简单图.② 2个顶点,每个顶点的度数均为 非简单图.③ 3个顶点,每个顶点的度数均为 ④ 4个顶点,每个顶点的度数均为⑤ 6个顶点，每个顶点的度数均为 24.这样的图有多种非同构的情况，一定为 16.所地应的图也都是非简单图. 12.所对应的图也都是非简单图.8,所对应的图也都是非简单图.⑦ 12个顶点，每个顶点的度数均为4.所对应的非同构的图中有简单图，也 有非简单图•⑧ 16个顶点,每个顶点的度数均为3,所对应的非同构的图中有简单图，也有 非简单图•⑨ 24个顶点,每个顶点的度数均为2.所对应的非同构的图中有简单图，也有 非简单图•⑩ 48个顶点,每个顶点的度数均为1,所对应的图是唯一的,即由24个K 2构 成的简单图•分析 由于n 阶无向简单图G 中,：(G)< n —1,的以①-⑤所对应的图不可能 有简单图•⑥-⑨既有简单图，也有非简单图，读者可以画出若干个非同构的图，而 ⑩只能为简单图•7.6 设G 为n 阶图，由握手定理可知n70 =2 35 八 d(vj _3n ,i吕所以，这里，乂为不大于x 的最大整数，例如.2」=2,25」=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 阶完全图K n .7.8由G 的补图G 的定义可知，G G 为K n ,由于n 为奇数，所以，K n 中各 项顶点的度数n -1为偶数.对于任意的V(G),应有v V(G),且d G (v)_d G (v)二 dg(v)二 n -1其中d G (v)表示v 在G 中的度数，d G(v)表示v 在G 中的度数.由于n_1为偶 数,所|70= 23.以,d G(v)与d G(v)同为奇数或同为偶数,因而若G有r个奇度顶点,则G也有r个奇度顶点.7.9由于D' D,所以，m'空m.而n阶有向简单图中，边数m乞n(n 一1),所以, 应有n(n _1) = m\ m 乞n(n -d)这就导致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三G?,贝U门丄=门2「且m<i = m?.国(8)的补图为(14) -K4 ,它们的边数不同,所以，不可能同构.因而(8)与(14) 均不是自补图类似地，(9)的补图为(13),它们也非同构,因而它们也都不是自补图.(10)与(12)互为补图,它们非同构,因而它们都不是自补图.(15)与(17)互为补图,它们非同构，所以,它们都不是自补图•类似地,(16)与(18)互为补图且非同构，所以，它们也都不是自补图•而(11)与自己的补图同构，所以,(11)是自补图•7.12 3阶有向完全图共有20个非同构的子图，见图7.7所示，其中⑸-(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 不能.分析在同构的意义下，G,G2,G3都中K4的子图，而且都是成子图.而K4的两条边的生成子图中，只有两个是非同构的，见图7.6中(10)与(15)所示.由鸽巢原理可知，G,G2,G3中至少有两个是同构的，因而它们不可能彼此都非同构.鸽巢原理m只鸽飞进n个鸽巢,其中m 一n ,则至少存在一巢飞入至少［凹］只n鸽子.这里x表示不小于x的最小整数.例如，|2 = 2, |2.5 =3.7.14 G是唯一的，即使G是简单图也不唯一.分析由握手定理可知2m = 3n,又由给的条件得联立议程组'2m =3 n 、2n —3 = m.解出n = 6,m二9.6个顶点,9条边，每个顶点的度数都是3的图有多种非同构的情况,其中有多个非简单图(带平行边或环),有两个非同构的简单图，在图7.8 中(1),(2)给出了这两个非同构的简单图.满足条件的非同构的简单图只有图7.8中,(1),(2)所示的图,(1)与⑵所示的图,(1) 与(2)是非同构的.注意在⑴中不存在3个彼此相邻的顶点而在⑵ 中存在3个彼此相邻的顶点，因而⑴图与(2)图非同构.下面分析满足条件的简单图只有两个是非同构的.首先注意到(1)中与(2)中图都是K6的生成子图，并且还有这样的事实，设G,G2都是n阶简单图，则G^G2当且仅当G^e G2 ,其中G,G2分别为G与G2的补图.满足要求的简单图都是6阶9条边的3正则图，因而它们的补图都为6阶6条边的2正则图(即每个顶点度数都是2).而K6的所有生成子图中,6条边2正则的非同构的图只有两个，见图7.8中(3),(4)所示的图，其中(3) 为(1)的补图,(4)为(2)的补图，满足要求的非同构的简单图只有两个.但满足要求的非同简单图有多个非同构的，读者可自己画出多个来.7.15将K6的顶点标定顺序，讨论X所关联的边.由鸽巢原理(见7.13题),与V1关联的5条边中至少有3条边颜色相同，不妨设存在3条红色边,见图7.9 中⑴ 所示(用实线表示红色的边)并设它们关联另外3个顶点分别为V2,v4,V6.若V2,V4, V6构成的K g中还有红色边，比如边(V2M)为红色，则Vj^M构成的K g为红色K3,见图7.9中⑵ 所示.若V2,V4,V6构成的K3各边都是蓝色(用虚线表示), 则V2,V4,V6构成的K a为蓝色的.珂7.16在图7.10所示的3个图中，(1)为强连通图，(2)为单向连通图，但不是强连通的,(3)是弱连通的，不是单向连通的，更不是强连通的.图7. 10分析在⑴中任何两个顶点之间都有通路，即任何两个顶点都是相互可达的,因而它是强连能的.(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「G2，G3组成，且E'中边的两个端点分属于两个不同的小图.设E"中的边的两个端点一个在G中,另一个在G 2中,则E " E ',易知p(G 一 E") =2 ,这与E '为边割集矛盾,所以, p(G 一 E") =2.但p(G-V ')不是定数,当然它大于等于2,在图7.11中,V 二｛u,v ｝为⑴的点 割集,p(G-V)=2，其中G 为(1)中图.V =｛v ｝为⑵ 中图的点割集，且v 为割tin i点,p(G -V ) =4,其中G 为⑵中图.屛1;■<]>£ 7.11(2)7.18解此题，只要求出D 的邻接矩阵的前4次幕即可.D 中长度为4的通路数为A 4中元素之和，等于15,其中对角线上元素之和为 3,即D 中长度为3的回路数为3. V 3到V 4的长度为4的通路数等于a 34)= 2.分析 用邻接矩阵的幕求有向图D 中的通路数和回路数应该注意以下几点： 1 °这里所谈通路或回路是定义意义下的，不是同构意义下的.比如,不同始 点(终点)的回路2 ° 这里的通路或回路不但有初级的、简单的，还有复杂的.例 如，V 1,V 2,w,V 2,V 1是一条长为4的复杂回路.3°回路仍然看成是通路的特殊情况.读者可利用A 2, A 3,求D 中长度为2和3的通路和回路数. 7.19 答案A:④.分析G 中有N k 个k 度顶点，有(n — NQ 个(k 1)度顶点，由握手定理可知0 11010 0 0 A = 0 10 1 .0 0 0 0一A 2A 3A 4~1 1 0 11 1 0 0 0 1 0 0 1211n、d(V j) =k N k(k 1)(n - N k) =2mi 4=N k=n (k 1)-2 n.7.20答案A:②；B:③.分析在图7.12中，图(1)与它的补同构，再没有与图(1)非同构的自补图了所以非同构的无向的4阶自补图只有1个.图⑵与它的补同构，图⑶与它的补也同构，而图⑵ 与图⑶ 不同构，再没有与(2),(3)非同构的自补图了，所以，非同械的5阶自补图有2个.<1)(Z) ⑶圉7.127.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)既不是强连通的，也不是连通的，它只是弱连通图.在⑶中，从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的最短路径为be,其权为1.b到d的最短路径为bcegd ,其权为9.b到e的最短路径为bee,其权为7.7.23 答案A:⑧；B:⑩ C:③；D:③和④.分析按求最早、最晚完成时间的公式，先求各顶点的最早完成时间，再求最晚完成时间，最后求缓冲时间（1）最早完成时间：TE（vJ =0-_(V2)二{vM, TE(v2) =max{0 3} =3-_(V3)二{vz}, TE(v3) =max{0 2,3 C} -3厂(vj 二{WM},TE(vJ =max{0 4,3 2} = 5-(V5)二M M},TE(V5)= max{34,3 4} - 711 /11TL(V 9)=13 -(V 8)二{V 9},TL(v 8) =mi n{13_1} =12; -(V 6) ={V 8},TL(v 6) = mi n{12 -3 = 9; -(V 7)二 g},TL(v 7) =mi n{12 —1} =11; -(V 5) ={V 6,V 9}, TL(v 5) =min{9-0,13 -6} = 7; ：(V 4)*7}, TL (V4)= min {11-5=6; -(V 3)二{V 4,V 5,V 6},TL(v 3) =min{6-2.7-4.9-4二 5; (v 2 ) = {v 3, V 5}, TL(v 2) =mi n{3-0.7-4} =3; ；(vj ={V 2,V 3,V 4},TL(vJ = mi n{ 3 —3.3 —2,6 —'4} = 0;(3)缓冲时间： TS(V i )二TS(V 2)=TS(V 3)=TS(V 5)=TS(V 9)=0 TS(V 4)=1,TS (V 6)=2,TS (V 7)=TS (V 8)=1.(4)关键路径有两条： V 1,V 2,V 5,V 9 和 V 1,V 2,V 3,V 5,V 9.-一山)={V 4,V 5},TE(v 7) = max{5 5,10 0} =10 (V 8 ) = { V 6, V 7 }, TE(v 8) = max{7 3,10 1} =11-讥)二{V 5,V 8},TE(v 9) =max{7 6,11 1} =13 -_(V 6)二“他},TE(v 6) =max{3 4,7 0} = 7 (2)最晚完成时间:。

离散数学8习题解答第8 章习题解答8.1 图8.6 中,(1)所⽰的图为,3,1K (2) 所⽰的图为,3,2K (3)所⽰的图为,2,2K 它们分别各有不同的同构形式.8.2 若G 为零图,⽤⼀种颜⾊就够了,若G 是⾮零图的⼆部图,⽤两种颜⾊就够了.分析根据⼆部图的定义可知,n 阶零图(⽆边的图)是三部图(含平凡图),对n 阶零图的每个顶点都⽤同⼀种颜⾊染⾊,因为⽆边,所以,不会出现相邻顶点染同⾊,因⽽⼀种颜⾊就够⽤了.8.3 完全⼆部图,,s r K 中的边数rs m -.分析设完全⼆部图s r K ,的顶点集为V, 则?==2121,V V V V V ,且,||,||21s V r V ==s r K ,是简单图,且1V 中每个顶点与2V 中所有顶点相邻,⽽且1V 中任何两个不同顶点关联的边互不相同,所以,边数rs m -.8.4 完全⼆部图s r K ,中匹配数},min{1s r =β,即1β等于s r ,中的⼩者. 分析不妨设,s r ≤且⼆部图s r K ,中,,||,||21s V r V ==由Hall 定理可知,图中存在1V 到的完备匹配,设M 为⼀个完备匹配,则1V 中顶点全为M 饱和点,所以,.1r =β8.5 能安排多种⽅案,使每个⼯⼈去完成⼀项他们各⾃能胜任的任务.分析设},,{1丙⼄甲=V ,则1V 为⼯⼈集合, },,{2c b a V =,则2V 为任务集合.令}|),{(,21y x y x E V V V 能胜任== ,得⽆向图>=8.7 所⽰.本题是求图中完美匹配问题. 给图中⼀个完美匹配就对应⼀个分配⽅案.图8.7 满⾜Hall 定理中的相异性条件,所以,存在完备匹配,⼜因为,3||||21==V V 所以,完备匹配也为完美匹配.其实,从图上,可以找到多个完美匹配. 取)},(),,(),,{(1c b a M 丙⼄甲=此匹配对应的⽅案为甲完成a,⼄完成b, 丙完成c,见图中粗边所⽰的匹配. )},(),,(),,{(c a b M 丙⼄甲=2M 对应的分配⽅案为甲完成b,⼄完成a,丙完成c.请读者再找出其余的分配⽅案.8.6 本题的答案太多,如果不限定画出的图为简单图,⾮常容易地给出4族图分别满⾜要求.(1) n (n 为偶数,且2≥n )阶圈都是偶数个顶点,偶数条边的欧拉图.(2) n (n 为奇数,且1≥n )阶圈都是奇数个顶点,奇数条边的欧拉图.(3) 在(1) 中的圈上任选⼀个顶点,在此顶点处加⼀个环,所务图为奇数个顶点,偶数条边的欧拉图.分析上⾯给出的4族图都是连通的,并且所有顶点的度数都是偶数,所以,都是欧拉图.并且(1),(2) 中的图都是简单图.⽽(3),(4)中的图都带环,因⽽都是⾮简单图. 于是,如果要求所给出的图必须是简单图,则(3),(4)中的图不满⾜要求.其实,欧拉图是若⼲个边不重的图的并,由这种性质,同样可以得到满⾜(3),(4)中要求的简单欧拉图.设k G G G ,,,21 是长度⼤于等于3的k 个奇圈(长度为奇数的圈称为奇圈),其中k 为偶数,将1G 中某个顶点与2G 中的某顶点重合,但边不重合, 2G 中某顶点与3G 中某顶点重合,但边不重合,继续地,最后将1-k G 中某顶点与k G 中某顶点重合,边不重合,设最后得连通图为G,则G 中有奇数个顶点,偶数条边,且所有顶点度数均为偶数,所以,这样的⼀族图满⾜(4)的要求,其中⼀个特例为图8.8中(1)所⽰.在以上各图中,若k G G G ,,,21 中有⼀个偶圈,其他条件不变,构造⽅法同上,则所得图G 为偶数个顶点,奇数条边的简单欧拉图,满⾜(3)的要求,图8.8中(2)所⽰为⼀个特殊的情况.8.7 本题的讨论类似于8.6题,只是将所有⽆向圈全变成有向圈即可,请读者⾃⼰画出满⾜要求的⼀些特殊有向欧拉图.8.8 本题的答案也是很多的,这⾥给出满⾜要求的最简单⼀些图案,⽽且全为简单图.(1) n (3≥n )阶圈,它们都是欧拉图,⼜都是哈密尔顿图.(2) 给定k (2≥k )个长度⼤于等于3的初级回路,即圈k G G G ,,,21 ,⽤8.6题⽅法构造的图G 均为欧拉图,但都不是哈密尔顿图,图8.8给出的两个图是这⾥的特例.(3)n (4≥n )阶圈中,找两个不相邻的顶点,在它们之间加⼀条边,所得图均为哈密尔顿图,但都不是欧拉图.(4) 在(2)中的图中,设存在长度⼤于等于4的圈,⽐如说1G ,在1G 中找两个不相邻的相邻顶点,在它们之间加⼀条新边,然后⽤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 除2K 不是哈密尔顿图之外, n K (3≥n )全是哈密尔顿图. n K (n 为奇数)为欧拉图. 规定1K (平凡图)既是欧拉图,⼜是哈密尔顿图.分析从哈密尔顿图的定义不难看出,n 阶图G 是否为哈密尔顿图,就看是否能将G 中的所有顶点排在G 中的⼀个长为n 的初级回路,即圈上. n K (3≥n )中存在多个这样的⽣成圈(含所有顶点的图), 所以n K (3≥n )都是哈密尔顿图.在完全图n K 中,各顶点的度数均为n-1,若n K 为欧拉图,则必有1-n 为偶数,即n 为奇数,于是,当n 为奇数时, n K 连通且⽆度顶点,所以, n K (n 为奇数) 都是欧拉图.当n 为偶数时,各顶点的度数均为奇数,当然不是欧拉图.8.12 有割点的图也可以为欧拉图.分析⽆向图G 为欧拉图当且仅当G 连通且没有奇度顶点.只要G 连通且⽆奇度顶点(割点的度数也为偶数),G 就是欧拉图.图8.8所⽰的两个图都有割点,但它们都是欧拉图.8.13 将7个⼈排座在圆桌周围,其排法为.abdfgeca分析做⽆向图>=},,,,,,{g f e d c b a V =},|),{(有共同语⾔与且v u V v u v u E ∈=图G 为图8.10所⽰.图G 是连通图,于是,能否将这7个⼈排座在圆桌周围,使得每个⼈能与两边的⼈交谈,就转化成了图G 中是否存在哈密尔顿回路(也就是G 是否为哈密尔顿图).通过观察发现G 中存在哈密尔顿回路, abdfgeca 就是其8.14 ⽤i v 表⽰颜⾊.6,,2,1, =i i 做⽆向图>=},,,,,,{654321v v v v v v V =}.,,|),{(能搭配与并且且v u v u V v u v u E ≠∈=对于任意的)(,v d V v ∈表⽰顶点v 与别的能搭配的颜⾊个数,易知G 是简单图,且对于任意的V v u ∈,,均有633)()(=+≥+v d u d ,由定理8.9可知,G 为哈密尔顿图,因⽽G 中存在哈密尔顿回路,不妨设1654321i i i i i i i v v v v v v v 为其中的⼀条,在这种回路上,每个顶点⼯表的颜⾊都能与它相邻顶点代表的颜⾊相.于是,让1i v 与2i v ,3i v 与4i v ,5i v 与6i v 所代表的颜⾊相搭配就能织出3种双⾊布,包含了6种颜⾊.8.15∑=?======300321,10220)deg(.12)deg(,3)deg(,1)deg(,4)deg(i i R R R R R ⽽本图边数m=10.分析平⾯图(平⾯嵌⼊)的⾯i R 的次数等于包围它的边界的回路的长度,这⾥所说回路,可能是初级的,可能是简单的,也可能是复杂的,还可能由若⼲个回路组成.图8.1所⽰图中,321,,R R R 的边界都是初级回路,⽽0R 的边界为复杂回路(有的边在回路中重复出现),即432110987654321e e e e e e e e e e e e e e ,长度为12,其中边65,e e 在其中各出现两次.8.16 图8.11中,实线边所⽰的图为图8.1中图G,虚线边,实⼼点图为它的对偶图的顶点数*n ,边数*m ,⾯数*r 分别为4,10和8,于是有分析从图8.11还可以发现,G 的每个顶点位于的⼀个⾯中,且的每个⾯只含G 的⼀个顶点,所以,这是连通平⾯图G 是具有k 个连通分⽀的平⾯图2≥k ,则应有1*+-=k n r .读者⾃⼰给出⼀个⾮连通的平⾯图,求出它的对偶图来验证这个结论.另外,⽤图8.1还可以验证,对于任意的*v (*G 中的顶点),若它处于G 的⾯i R 中,则应有)deg()(*i R v d =.8.17 不能与G 同构.分析任意平⾯图的对偶图都是连通的,因⽽与都是连通图,⽽G 是具有3个连通分⽀的⾮连通图,连通图与⾮连通图显然是不能同构的.图 8.12 中, 这线边图为图8.2中的图G,虚线边图为G 的对偶图,带⼩杠的边组成的图是*G 的对偶图,显然.~**G G ≠8.18 因为彼得森图中有长度为奇数的圈,根据定理8.1可知它不是⼆部图.图中每个顶点的度数均为3,由定8.5可知它不是欧拉图.⼜因为它可以收缩成5K ,由库拉图期基定理可知它也不是平⾯图.其实,彼得森图也不是哈密尔顿图图,这⾥就不给出证明了.8.19 将图8.4重画在图8.13中,并且将顶点标定.图中afbdcea 为图中哈密尔顿回路,见图中粗边所⽰,所以,该图为哈密尔顿图.将图中边),(),,(),,(d f f e e d 三条去掉,所得图为原来图的⼦图,它为3,3K ,可取},,{1c b a V =},,{2f e d V =,由库拉图期基定理可知,该图不是平⾯图.8.20 图8.14 所⽰图为图8.5所⽰图的平⾯嵌⼊.分析该图为极⼤平⾯图.此图G 中,顶点数9=n ,边数.12=m 若G 是不是极⼤平⾯图,则应该存在不相邻的顶点,,v u 在它们之间再加⼀条边所得'G 还应该是简单平⾯图, 'G 的顶点数131,6''=+===n m n n ,于是会有.126313''=->=n m这与定理8.16⽭盾,所以,G 为极⼤平⾯图.其实,n ( 3≥n )阶简单平⾯图G 为极⼤平⾯图当且仅当G 的每个⾯的次数均为3.由图8.14可知,G 的每个⾯的次数均为3,所以,G 为极⼤平⾯图.8.12 答案 A,B,C,D 全为②分析 (1) 只有n 为奇数时命题为真,见8.11的解答与分析.(2) 2≠n 时,命题为真,见8.11的解答与分析.(3) 只有m n ,都是偶数时,m n K ,中才⽆奇度数顶点,因⽽m n K ,为欧拉图,其他情况下,即m n ,中⾄少有⼀个是奇数,这时m n K ,中必有奇度顶点,因⽽不是欧拉图.(4) 只有m n =时, m n K ,中存在哈密尔顿回路,因⽽为哈密尔顿图. 当m n ≠时,不妨设m n <,并且在⼆部图m n K ,中,m V n V==||,||21,则n V m V G p =>=-||)(11,这与定理8.8⽭盾. 所以, m n ≠时, m n K ,不是哈密尔顿图.8.22 答案 A:②;B ②;C ②.分析图8.15中,两个实边图是同构的,但它们的对偶⼒(虚边图)是不同构的.(2) 任何平⾯图的对偶图都是连通图.设G 是⾮连通的平⾯图,显然有.**~G G ≠ (3) 当G 是⾮连通的平⾯图时,,1*+-=k n r 其中k 为G 的连通分⽀数.8.23 答案 A:④;B ②;C ②.分析根据库期基定理可知,所求的图必含有5K 或3,3K 同胚⼦图,或含可收缩成5K 或3,3K 的⼦图.由于顶点数和边数均已限定,因⽽由3,3K 加2条边的图可满⾜要求,由5K 增加⼀个顶点,⼀条边的图可满⾜要求,将所有的⾮同构的简单图画出来,共有4个,其中由3,3K 产⽣的有2个,由5K 产⽣的有2个.见图8.16所⽰.。