哈工大集合论习题课-第五章 图的基本概念习题课

第五章 图的基本概念

习 题 课 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；

⑨ 若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)g(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?2g(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）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

fg

(a) (b)

图3 图4

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

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

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

(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?v0v1Lvl，其长度为l?2?。因为degv0??，

degv1??，所以存在0?i?l?1，使v0vi?1 与viv1在G中相邻，得一长为l?1的回

路：v0v1Lviv1v1?1Lvi?1v0。

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