哈工大集合论习题课-第五章图的基本概念习题课(学生)|江阴雨辰互联

2023年7月19日发(作者：)

第五章图的基本概念

习题课 1

1. 画出具有 6、8、10、…、2n个顶点的三次图；是否有7个顶点的三次图？

2. 无向图G有21条边，12个3度数顶点，其余顶点的度数均为2，求G的顶点数p。

解：设图的顶点为p，根据握手定理：deg(vi)2q，有

i1p1232(p12)221，得2p30，p15。

3. 下列各无向图中有几个顶点？

（1）16条边，每个顶点的度为2；

（2）21条边，3个4度顶点，其余的都为3度数顶点；

（3）24条边，各顶点的度数相同。

解：设图的顶点为p，根据握手定理：

（1）deg(vi)2q，即2p2q21632；所以p16，即有16个顶点。

i1pp（2）deg(vi)2q，即433(p3)2q22142，所以p13。

i1（3）各点的度数为k，则deg(vi)2q，即kp2q22448，于是

i1p① 若k1，p48； ② 若k2，p24；

③ 若k3，p16；

⑤ 若k6，p8；

⑦ 若k12，p4；

④ 若k4，p12；

⑥ 若k8，p16；

⑧ 若k16，p3；

1 ⑨ 若k24，p2； ⑩ 若k48，p1。

4．设图G中9个顶点，每个顶点的度不是5就是6。证明G中至少有5个6度顶点或至少有6个5度顶点。

证：由握手定理的推论可知，G中5度顶点数只能是0，2，6，8五种情况，此时6度顶点数分别为9，7，5，3，1个。以上五种情况都满足至少5个6度顶点或至少6个5度顶点的情况。

5．有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药箱中，问药箱里共有多少种药？[就是求一个完全图Kn的边数q(p1)(p2)/2]

6.设G是有p个顶点，q条边的无向图，各顶点的度数均为3。则

（1）若q3p6，证明G同构意义下唯一，并求p,q；

（2）若p6，证明G在同构的意义下不唯一。

分析：在图论中，对于简单无向图和简单有向图，若涉及到边q与顶点p的问题，握手定理是十分有用的。

解：（1）由于各顶点的度数均为3，现在有p个顶点，q条边，所以由握手定理知：deg(vi)2q，即3n3q，故n2m/3；

i1p又q3p632q/362q6，故q6，则p2/364。

即q4，p4，此时所得的无向图如图1所示，该图是4个顶点的简单无向图中边最多的图，即为无向完全图K4。

对于4个顶点的完全图，在同构意义下，4个顶点的完全图是唯一的。

（2）若p6，由握手定理：deg(vi)2q，即362q。

i1p故q9，此时有p6,q9，且每个顶点的度数为3；此时对于简单无向图，6个顶点，9条边及每个度数为3的有如图2所示两个非同构的图；(a)与(b)是非同构的图，所以p6,q9，度数为3的无向图G在同构的意义下是不唯一的。

（a） (b)

图1 图2

7.已知p阶简单图G中有q条边，各顶点的度数均为3，又2qp3，试画出满足条件的所有不同构的G。

解：由握手定理：deg(vi)3p2q，又2pq3，即q2p3。故

i1p3p2q2(2p3)4p6，即p6，q2p39。

此时有p6，q9且每个顶点的度数都为3，则不同构的无向图有两个，如图3所示。

图3

8．9个学生，每个学生向其他学生中的3个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？

解：否，因为不存在9（奇数）个顶点的3－正则图

习题课2

例3设p,q为正整数，则

（1）p为何值时，无向完全图Kp是欧拉图？p为何值时Kp为半欧拉图？

（2）p,q为何值时Kp,q为欧拉图？

（3）p,q为何值时Kp,q为哈密整图？

3 （3）p为何值时，轮图Wp为欧拉图？

证：（1）一般情况下，不考虑无向图K1。因此

因为Kp各顶点的度均为p1，若使Kp为欧拉图，p1必为偶数，因而p必为奇数。即p(p3)为奇数时，完全图Kp是欧拉图。

若p2或p(p3)为奇数时，Kp是半欧拉图。

（2）当p,q2均为偶数时，Kp,q为欧拉图。

（3）当pq时，Kp,q为哈密整图。

（4）设Wp(p4)为轮图，在Wp中，有p1个顶点的度为3，因而对于任意

取值p(p4)，轮图Wp都不是欧拉图。

例1 判断图5所示的图是否为哈密顿图，若是写出哈密顿回路，否则证明其不是哈密顿图。

ecfbadjdagjihiehcb

(a) (b)

图3 图4

例2 给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有degudegv9。

例3 试求Kp中不同的哈密顿回路的个数。

例4 (1) 证明具有奇数顶点的偶图不是哈密顿图；用此结论证明图8所示的图不是哈密顿图。

4 (2) 完全偶图Km,n为哈密顿图的充分必要条件是什么？

证：(1) 设G是一个具有奇数顶点的偶图，则G的顶点集V有一个二划分，

即V{V2,V2}且有|V1||V2|。

不妨设|V1||V2|，则有W(GV1)|V2||V1|。

由哈密顿图的必要条件可知：G不是哈密顿图。

题中所给的图中无奇数长的回路，因而此图是偶图。而且此图中有13个顶

点，因此它不是哈密顿图。

(2)

若|V1||V2|，有(1)可知Km,n不是哈密顿图；

若|V1||V2|，同理有Km,n不是哈密顿图。

故Km,n是哈密顿图时只有|V1||V2|，即mn。

若mn，则u,vV,degudegv|V|/2|V|/2|V|，由定理知：

Km,n是哈密顿图。

例5 菱形12面体的表面上有无哈密顿回路？

例6设G(V,E)是连通图且顶点数为p，最小度数为p2，则G中有一长至少为2的路。

分析: 采用最长路法，设连通图的最长路为L且|L|2。再看这条路的端点，端点只能与L上的顶点相邻，这样就可以构成一个回路，对于回路外的顶点，因为仍与此回路上的某些顶点相邻，所以可以把这个顶点连到回路上，然后再打开回路，显然这时有一条路比假设时的路更长了，所以假设不成立。

证：假设G中的最长路为L：Lv0v1vl，其长度为l2。因为degv0，

degv1，所以存在0il1，使v0vi1

与viv1在G中相邻，得一长为l1的回路：v0v1viv1v11vi1v0。

又因为G连通，且G的顶点数p2，故存在vvi(0il)与回路上

5 vj(0jl)相邻，则把回路在vj处断开，并把v连入回路中，得到一条长为l1的路，矛盾。

所以G中有一长至少为2的路。

例7 证明：彼德森(Petersen)图不是哈密顿图。

例8 某工厂生产由6种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他3种颜色搭配。证明：可以挑出3种不同的双色布，它们含有所有6种颜色。

证：用6个不同的点分别表示6种不同颜色的纱，两个点间联一条线当且仅当用这两点所表示的两种不同颜色的纱织成一种双色布。于是，我们得到一个有6个点的图G。由于每种颜色的纱至少和3种其他颜色的纱搭配，所以G的每个顶点的度至少是3。于是，由定理1，G有哈密顿回路。回路上有6条边，对应了6种不同的双色布。间隔取出3条边，它们包含了全部6种颜色。

与例8等价的例题：

例9 今要将6个人分成3组（每组2个人）去完成3项任务，已知每个人至少与其余5个人中的3个人能相互合作，问：

(1)能否使得每组2个人都能相互合作？(2)你能给出集中方案？（两种）

例10 某公司来了9名新雇员，工作时间不能互相交谈。为了尽快互相了解，他们决定利用每天吃午饭时间相互交谈。于是，每天在吃午饭时他们围在一张圆桌旁坐下，他们是这样安排的，每一次每人的左、右邻均与以前的人不同。问这样的安排法能坚持多久？

解：平面上9个互不相同的点分别代表9个新雇员。因为每个人都可以为其他每个人的左或右邻，所以用两点的联线表示相应的两个人互为左右邻。于是得到了有9个顶点的完全图K9。于是，我们的问题中的一种坐法就是K9的一个哈密顿回路。由于每次的安排中，每人的左、右邻均与以前的人不同，所以我们的问题就是求K9中有多少个两两无公共边的哈密顿回路。由图1.6.5不难发现，K9中恰有4个两两无公共边的哈密顿回路。它们是：1234567891，1357924681，1473825961，1584936271。

于是，他们的这种安排法仅能维持4天。

6 例10可推广为n个雇员的一般情况问题。这时，

当n为奇数时，这种安排法仅能维持(n-1)/2天；

当n为偶数时，这种安排法仅能维持(n-2)/2天。

习题课3

例2设d(d1,d2,,dn)，其中di为正整数，i1,2,,n。若存在n个顶点的简单图，使得顶点vi的度为di，则称d是可图解的。下面给出的各序列中哪些是可图解的？哪些不是，为什么？

（1）（1，1，1，2，3）；（6）（1，3，3，3）；

（2）（0，1，1，2，3，3）；（7）（2，3，3，4，5，6）；

（3）（3，3，3，3）；（8）（1，3，3，4，5，6，6）；

（4）（2，3，3，4，4，5）；（9）（2，2，4）；

（5）（2，3，4，4，5）；（10）（1，2，2，3，4，5）。

解：（1），（2），（3）全是可图解的，它们对应的图分别如图3中(a),(b),(c)所示；其余的各序列都不是可图解的。

在（4），（7），（10）中均有奇数个奇度顶点，根据握手定理的推论，它们自然都不是可图解的。

另外在p阶简单图中，每个顶点的度至多为p1，因而（5）和（9）均不可图解。

若（6）是可图解的，则设degv11,degv2degv3degv43，因为v2,v3,v4的度都是3，因而要求v1与v2,v3,v4之间有边关联，但因v1的度为1，这是不可能的，所以（6）也是不可图解的。

在（8）中，n7，因而每个顶点至多6度。若（8）是可图解的，设degv11，degv6degv76，因而v6,v7均应与v1相邻，这也是不可能的，

因而（8）也不可图解。

图3

(a) (b) (c)

例3 至少要删除多少条边，才能使Kp(p2)不连通且其中有一个连通分支恰有k个顶点(0kp)？简述理由。

证：要使删除边后的图边数最多，则删除的边最少。满足有一个连通分支恰有k个顶点的图的最大边数为：

k(k1)(nk)(nk1)

22则至少应该删除的边数为：

n(n1)k(k1)(nk)(nk1)。

222例4若G是一个恰有两个奇度顶点u和v的无向图，则G连通Guv连通。

证： 显然成立。

 假设G不连通，则G有k(k2)个分支：G1,G2,,Gk，由题意u与v不在一个分支上，于是含有u或v的顶点的分支只有一个奇度数顶点与握手定理的推论矛盾。

于是假设不成立，即G是连通的。

例5设G为p阶简单无向图，p2且p为奇数，G和G的补图Gc中度数为奇数的顶点的个数是否一定相等？试证明你的结论。

解：一定相等。

因为p2为奇数，则对于奇数个顶点的p阶无向完全图，每个顶点的度数必为偶数。若G的奇度数顶点为p1个，则对应补图Gc在这p1个顶点的度数必为（偶数－奇数）＝奇数。另外，对于G中度数为偶数的顶点，其在补图Gc中，

8 这些顶点的度数仍为（偶数－偶数）＝偶数。所以，G中度数为奇数的顶点个数与Gc中度数为奇数的顶点个数相同。

例6证明：完全图K9中至少存在彼此无公共边的两条哈密顿回路和一条哈密顿路？

证：在K9中，vV,degv8p/2，由定理可知，必有一条哈密顿回路C1；令G1为K9中删除C1中全部边之后的图，则G1中每个顶点的度均为故G1仍为哈密顿图，因而存在G1中的哈密顿回路C2，显然C1与degv6p/2，C2无公共边。再设G2为G1中删除C2中的全部边后所得图，则G2每个顶点的度均为degv4。又由定理可知G2为半哈密顿图，因而G2中存在哈密顿路。设L为G2中的一条哈密顿路，显然C1,C2,L无公共边。

例7 已知a,b,c,d,e,f,g7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？

证：用a,b,c,d,e,f,g7个顶点代表7个人，若两人能交谈（会讲同一种语言），就在代表他们的顶点之间连一条无向边，所得无向图如图4(a)所示，此图中存在哈密顿回路：abdfgeca（如图4(b)粗边所示），于是按图4(c)所示的顺序安排座位即可。

bbacbdacacgfedgdfef

(a) (b) (c)

图4

9 例8将无向完全图K6的边随意地涂上红色或绿色，证明：无论何种涂法，总存在红色的K5或绿色的K5。

证：设K6的顶点为v1,v2,,v6。给K6的边任意用红、绿色涂上，由鸽巢原理可知，由v1引出的5条边中存在3条涂同种颜色的边。不妨设存在3条红色的边，又不妨设这3条边的另一个端点分别是v2,v3,v4（也可重新给顶点排序）。

若v2,v3,v4构成的K3中的边再有一条红色边。比如（v2,v4）着的是红色，

v1,v2,v4构成的三角形为红色的K3。若v2,v3,v4构成的K3的边全是绿色的边，则

存在绿色边的K3。这就证明了我们的结论。

例9已知9个人v1,v2,,v9，其中v1和两个人握过手，v2,v3,v4,v5各和3个人握过手，v6和4个人握过手，v7,v8各和5个人握过手，v9和6个人握过手。证明这9个人中一定可以找出3个人互相握过手。

分析：以v1,v2,,v9为顶点，vi与vj握过手就连一条边vivj，得到一个无向图G。只要证明G中有三角形子图，即可得一定有3个人互相握过手。

证：设v1,v2,,v9为图G的9个顶点，vi与vj握过手就连一条边vivj，于是得

到图G。根据题意有：

deg(v1)2,deg(v2)deg(v3)deg(v4)deg(v5)3，

deg(v6)4,deg(v7)deg(v8)5,deg(v9)6。

与v9相邻的点有6个，其中必有一点vk为v6,v7,v8之一，因此有deg(vk)4。与v9相邻的其余5个点中必存在一点vh与vk相邻如图4所示，否则有deg(vk)853，矛盾。由此v9,vk,vh三个人互相握过手。

10 

图5 图6 图7

例10如图6所示的图G是哈密顿图。试证明：若图中的哈密顿回路中含边e1，则它一定同时也含e2。

证：设C为图中一条哈密顿回路，e1在C中，假设e2不在C中，要推出矛盾。图中除e1外，与a,b关联的边各有两条，而只能各有一条边在C中，由对称性设。这就相当于(f,a),(b,c)在C中（不可能(f,a),(g,b)或(a,e),(b,c)同时在C中）在图7中所示的图G1中求一条哈密顿回路，而此时，a,b均为图G1中割点，这是不可能的，因而e2必在C中。

例11某次会议有20人参加，其中每个人都至少有10个朋友，这20人围一圆桌入席，要想使与每个人相邻的两位都是朋友是否可能？根据什么？

证：可能。依题意，若用顶点代表人，两人是朋友时相应顶点间连一条边，则得到一个无向图G(V,E)，该题转化为求哈密顿回路问题。由于对任意u,vV,有deg(u)10，deg(v)10，因而deg(u)deg(v)20。又定理可知，G为哈密顿图，G中存在哈密顿回路，按此回路各点位置入席即为所求。

例12 设G是一个p(p3)个顶点的连通图。u和v是G的两个不邻接的顶点,并

且degudegvp。

证明：G是哈密顿图Guv是哈密顿图。

证明：

显然成立。

则由题意知，在G中必有一条从u到v的哈密顿路。假设G不是哈密顿图，不妨设此路为uv2v3vp1v，令deguk,degvl，则在G中与u邻接的顶点为

11 ui1,ui2,,uik，其中2i1i2ikp1。此时顶点uir1(r2,3,vir1vvp1,k)不能与顶点v邻接。否则G有哈密顿回路uv2viru，因此v至少与u,v2,,vp1中的k个顶点不邻接。于是lp1k，从而klp1，即degudegvp1，与题设矛盾。故假设不成立，因此G是哈密顿图。

例13设G为p阶无向简单图，已知(G)3，证明G中存在长度为偶数的回路。

证：对无向简单图G的顶点个数n进行数学归纳证明：

当n4时，G为完全图，结论显然成立，所得的回路的长度为4。

设当nk时结论成立，长度为偶数的回路为C。

则当nk1时，长度为偶数的回路C也在顶点数为k1的图中，则结论成立。

例14设G(V,E)是p(p3)个顶点的简单无向图，设G中最长的路L的长度为起点与终点分别为u,v，而且degudegvp。证明：G中必有与L不l(l2)，完全相同但长度也为l的路。

证：设图G的最长的路L为：uv1以与u,v相邻的顶点必在L上。

若u和v相邻，则构成一个回路uv1vl1vu，回路长为l1；

,vir，其中vl1v，其长度为l。因L为最长的路，所若u和v不相邻，设与u相邻的顶点为vi1,vi2,1vi1vi2virl1，则v必与某个vij1(2jr)邻接。否则，v至多与最长路上其余的顶点邻接，所以

degudegvr(p1r)p

这是不可能的。于是uvijvij1vl1vvij1vij2v1u是G中的一个回路，此回路长度为l1。去掉这个回路的任意一条边，便得到一条相应的最长的路，所以对于这个回路有l1个不同的最长的路且l2。

故G中必有与L不完全相同，但长度也为l的路。