找它们的公共点的运算中，这些运算不超出p2*(q-p+w)次，故是好算法。

14．证明：H2r?1,p是?2r?1??连通的。

分析：只要证明H2r?1,p不存在少于2r?1个顶点的顶点割集。设V'是一个|V'|?2r?1的任一顶点子集，可分|V'|?2r和|V'|?2r两种情形证明。 证明：

(1) 当|V'|?2r时，根据定理7.3.1的证明，V'不是H2r,p的顶点割集，当然更不是在

H2r,p上加些边的H2r?1,p的顶点割集。

(2) 当|V'|?2r时，设V'是H2r?1,p的顶点割集，i,j属于H2r?1,p?V'的不同分支。考察顶点集合

S?{i,i?1,...,j?1,j}

和 T?{j,j?1,...,i?1,i} 这里加法取模n

若S或T中有一个含V'的顶点少于r个，则在H2r?1,p?V'中存在从i到j的路。与V'为顶点割集矛盾。

若S和T中都有V'的r个顶点，则： ? 若S或T中，有一个(不妨说S)中V'的r个顶点不是相继连成段，则S?V'中存在从

i到j的路。与V'为顶点割集矛盾。

? 若S与T中，V'的r个顶点都是相继连成一段的。若S与T中至少有一个没有被分成两段，则立即与V'为顶点割集矛盾；若S?V'被分成两段：含i的记S1，含j的记S2，且T?V'也被分为两段：含i的记T1，含j的记T2。这样，V?V'被分为两段：含i的S1?T1 和含j的S2?T2。这两段都是连通的，且含i段的中间点(或最靠近中间的一点)i0与含j段的类似点j0满足：

34

n?i??02j0??n?1?i0?2?(n为偶数)

(n为奇数)故i0与j0有边相连，在H2r?1,p?V'中有路(i,...,i0,j0,...,j)，与V'为顶点割集矛盾。 综上所述，H2r?1,p是?2r?1?连通的。

15．证明：?Hm,n??Hm,n?m.

? m分析：根据定理7.3.1，图Hm,n是m-连通图，因此有 ? （ H m ,n ）

????又根据Hm,n的构造，可知 H m ,n ） ? m ，再由定理7.1.1可证。 ? （ 证明：由定理7.3.1知： ? （ H m , n） ? m

已知：k≦λ ≦δ

而?（Hm,n）?m.因此m?k?????m.

故?（Hm,n）?m.

16．试画出H4.8、H5.8和H5.9

分析：根据书上第54页构造Hm,n的方法可构造出H4.8、H5.8和H5.9。

(i)

H4.8: r = 2 ,p=8,对任意 i,j ∈V(H4.8), ︱i- j︱≤r 或者

i??j?r,其中，i??i(modp),j??j(modp).?i?0,j?7,6??i??8,j??7,6?i?1,j?7??i??9,j??76071则H4.8如下图：

2534H4,8图(ii) H5.8图：r =2,p=8,则在H4.8中添加连接顶点i 与 i+p/2(mod p)的边，其中1≤i≤p/2, ∴1→5; 2 →6; 3 →7; 4 →0. 则H5.8图如下

35

07126534(iii) H5.9图:

H5,8图：

r=2,在H4,.9图上添加连接顶点0与（p-1）/2和(p+1）/2的边，以及顶点 i 与 i +（p+1）/2(mod p) 的边，其中1≤ i< （p-1）/2.

????i?9,j?8,7?i??10,j??8 ?∴0→4; 0 →5; 1 →6; 2 →7; 3→8. 则H5.9图如下：

?i?0,j?8,7?i?1,j?8780165324H5,9图36

习题8

1、图中8.10中哪些是E图？哪些是半E图？ (a)(b)(c)

分析：根据欧拉定理及其推论，E图是不含任何奇点的图，半E图是最多含两个奇点的图。

解： (a) 半E 图 。（b）E 图。 （c）非半E 图 和 E 图

2、试作出一个E图G(p,q),使得p与q均为奇数。能否作出一个E图G(p,q)，使得p为偶数，而q为奇数？如果是p为奇数，q为偶数呢？

解：以下 E 图中， p与 q 的奇偶如下表 G1 G2 G3

p 奇数 偶数 奇数 q 奇数 奇数 偶数 G1G3G23、求证：若G 是 E 图，则 G 的每个块也是 E 图。

分析：一个图如果含有E回路，则该图是E图；另一方面一个块是G中不含割点的极大连通不可分子图，且非割点不可能属于两个或两个以上的块。这样沿G中的一条E回路遍历G的所有边时，从一个块到达另一个块时，只能经过割点才能实现。

证明：设B是G的块，任取G中一条E回路C，由B中的某一点v出发，沿C前进，C只有经过G的割点才能离开B，也就是说只有经过同一个割点才能回到B中，注意到这个事实后，我们将C中属于B外的一个个闭笔回路除去，最后回到v时，我们得到的就是B上的一个E回路，所以B也是E图。

4、求证：若G无奇点，则G中存在边互不重的回路 C , C ，使得 1, ?m

E(G)?E(C1)?E(C2)???E(Cm)分析：G中无奇点，则除了孤立点后其他所有点的度至少为2，而孤立点不与任何边关联，因此在分析由边构成的回路时可以不加考虑；而如果一个图所有的顶点的度至少为2，则由第五章习

37