习 题 六
1．设G是一个无回路的图, 求证：若G中任意两个顶点间有惟一的通路, 则G是树. 证明：由假设知，G是一个无回路的连通图，故G是树。
2．证明：非平凡树的最长通路的起点和终点均为悬挂点. 分析：利用最长通路的性质可证。
证明：设P是树T中的极长通路。若P的起点v满足d(v)?1，则P不是T中极长的通路。对终点u也可同理讨论。故结论成立。
3．证明：恰有两个悬挂点的树是一条通路.
分析：因为树是连通没有回路的，所以树中至少存在一条通路P。因此只需证明恰有两个悬挂点的树中的所有的点都在这条通路P中即可。
证明：设u,v是树T中的两个悬挂点，即d(u)?d(v)?1。因T是树，所以存在(u,v)-通路
P：uw1?wkv,k?0。显然，d(wi)?2。若d(wi)?2，则由T恰有两个悬挂点的假设，可知T中有回路；若T中还有顶点x不在P中，则存在(u,x)-通路，显然u与x不邻接，且d(x)?2。于是，可推得T中有回路，矛盾。故结论成立。
4．设G是树, ??G??k, 求证：G中至少有k个悬挂点.
分析：由于??G??k，所以G中至少存在一个顶点v的度≥k，于是至少有k个顶点与邻接，又G是树，所以G中没有回路，因此与v邻接的点往外延伸出去的分支中，每个分支的最后一个顶点必定是一个悬挂点，因此G中至少有k个悬挂点。
证明：设u?V(G)，且d(u)?m?k。于是，存在v1,?,vm?V(G)，使
若vi不是悬挂点，则有vi??V(G),使。如此下去，有vi(l)?V(G)，uvi?E(G),i?1,?,m。满足vi(l)?vj,i?j,且d(vi(l))?1, i?1,?,m。故G中至少有k个悬挂点。
5．设G?p,q?是一个图, 求证：若q?p, 则G中必含回路.
分析：利用树是没有回路且连通的图，且树中的顶点数和边数的关系可证。
证明：设G(p,q)有k个分支：G[V1]?G1(p1,q1),?,G[Vk]?Gk(pk,qk)。显然，
p?p1???pk,q?q1???qk。若G无回路，则每个Gi(pi,qi)均是树，i?1,?,k。于是qi?pi?1,i?1,?,k。从而 q?p?k?p，k?1，即q?p。此为矛盾，故G必
含回路。
6．设G?p,q?是有k个连通分支的图, 求证：G是森林当且仅当q?p?k.
证明：见题5的证明。
22
7．画出K4的所有16棵生成树.
解，K4的所有16棵生成树如下图所示。
1
4 4 1
4 2
1
3 4 2 1
3
4 2
1
3
4 23
2
1
3 4 2 1
3 4 2
1
3
4 2
3
2
3
2
3
1
2
1
2
1
2
4 3
4 3
4 3
1
2
1
2
1
2
4 3
4 3
4 3
1
2
4 3
8．设G?p,q?是连通图, 求证：q?p?1.
分析：树应该是具有p个顶点中边数最少的连通图，而树中的边数q=p-1可证。
证明：设G是连通图。若G无回路，则G是树，于是q?p?1。若G有回路，则删去G中k?0条边使之保持连通且无回路。于是q?k?p?1，即q?p?1?k?p?1。 9．递推计算K2,3的生成树数目.
24
e e =
e +
K2,3 e e +
+ +
e =
+ + + +
e e + +
25
=
e e
=
+ +
+ + + + + +
e +
+ =
+ + + + + =12
+ + + + + +
10．通过考虑树中的最长通路, 直接验证有标记的5个顶点的树的总数为125.
分析：设树中5个顶点的标记分别为1，2，3，4，5。而5个顶点的树的最长通路只能是4、3、2，如下（1）（2）（3）所示。 (1) 最长通路长度为4；
(2) 最长通路长度为3；
（3） 最长通路长度为2。 对于（1），把每个顶点看作是一个空，不同的顶点序列对应不同的树，但由于对称性12345和54321所形成的树应该是同一棵树，因此这种情况下所有有标记的树的数目为：5！/2=60个； 对于（2），把上面四个顶点分别看作一个空，在构造树的时候可以先构造这四个顶点，剩下的一
个顶点只能放在下面，选择上面四个顶点的数目应为可以从所有有标记的树的数目为
，但同样由对称性，如1234这样的排列和顶点5构成的树与1235这样的排列和4构C54*4！
成的数是一样的。因此这种情况下所有有标记的树的数目为：C5*4！/2=60个；
对于（3），只要确定了中间度为4的顶点，这棵树就构造完了，所有这种情况下有标记的树的数
目为：C5?5个；
26
14
解：有标记的5个顶点的树的总数为：60+60+5=125个。
11．用T?n?表示n个顶点的有标记树的个数, 求证：
k 2?n?1?T?n???k?n?k?T?k?T?n?k?Cnk?1n?1由此得恒等式
?kk?1?n?k?k?1n?1n?k?1kCn?2?n?1?nn?2
分析：每个n阶树可由下面的方法构造出来：先从这n个顶点中任取k个顶点构造出一个k阶树，
对剩下的n-k个顶点构造出一个n-k阶树，再将这两个树合并成一个树，显然这样得到的树是一个n阶的树。又由定理6.2.4有i个顶点的无标记的生成树共有ii-2个，可得下面的证明。 证明：任取k个顶点的一棵k阶树与 (n–k)个顶点构成的n–k阶树之间连接两点就是一棵n阶树，这里有k (n–k) 种连接。并注意到一来一往每条边用了两次，因此， k (n–k) T(k) T (n–k)Cnk =2T(n)。上式两边对k从1到n–1求和，得2(n?1)T(n)??k(n?k)T(k)T(n?k)Ck?1n?1kn。再将T(n) = nn–2,
T(k) = kk–2, T (n–k)= (n–k)n–k–2, 代入上式便可得恒等式：
?kk?1n?1k?1k(n?k)n?k?1Cn?2(n?1)nn?2
12. 如何用Kruskal算法求赋权连通图的权最大的生成树（称为最大树）？ 证明：将Kruskal算法中的“小”改成“大”即可得到“最大树”。
13．设G是一个赋权连通图, V?G???1,2,?,n?,n?2. 求证：按下列步骤（Prim算法）可以得出G的一个最优树.
1,T:??； （i）置U:???（ii）选取满足条件i?U,j?V?G??U且C?i,j?最小的?i,j?； （iii）T:T??i,j?,U:?U??j?；
27
（iv）若U?V?G?则转（ii）, 否则停止, T中的边就是最优树的边.
解： (1) 设T是按Prim算法得出的图。由Prim算法的初值及终止条件，可知T连通，且
*
*
T*为G的生成子图。又由（ⅱ）知T*无回路。故T*是生成树。
（2）设T(G)?{T|T是G的生成树，T?T*}，仿定理6.3.1的证明，可证结论成立。
14．按题13的Prim算法, 求出图6. 9的最优树.
6 8 7 3 6 6 3 4 2 2 3 1 图6.9
解：最优树如下。（权为20）
1 6 6 3 5 1 6 2 7 2 2 3 4
28
习题七
1．对图7.7中的两个图，各作出两个顶点割。
（a）
图7.7
（b）
解： 对图7.7增加加节点标记如下图所示，
则(a)的两个顶点割为： V11={a,b} ； V12={c,d} (b)的两个顶点割为： V21={u,v} ； V12={y}
yacwduvxb(a)图7.7(b)
2．求图7.7中两个图的??G?和??G?.
3．试作出一个连通图G, 使之满足：??G????G????G?
解：做连通图G如下，于是有 ： k(G)??(G)??(G)
解：如上两个图，有 k(G1)=λ(G1)=2, k(G2)=1, λ(G2)=2
4．求证, 若G?p,q?是k?边连通的, 则q?kp/2.
29
证明：设G是k—边连通的，由定义有λ(G)≧k. 又由定理7.1.2知λ(G)≦ ? ，因此有 k
?p??2q≦λ(G) ≦ ? 2≦q ?p??p??
即 k≦ 2 q ，从而 q ? kp 。
?2q?25．求证, 若G是p阶简单图, 且??G??p?2, 则??G????G?.
p分析：由G是简单图，且??G??p?2，可知G中的δ(G)只能等于 p-1或p-2；
如δ(G)= p-1,则G是一个完全图，根据书中规定，有k(G)=p-1=δ(G)；
如δ(G)= p-2,则从G中任取V（G）的子集V1，其中|V1|=3，则V(G)-V1的点导出子图是连通的，否则在V1中存在一个顶点v，与其他两个顶点都不连通。则在G中，顶点v最多与G中其他p-3个顶点邻接，所以d(v)≤p-3，与δ(G)= p-2矛盾。这说明了在G中，去掉任意p-3个顶点后G还是连通的，按照点连通度的定义有k(G)>k-3，又根据定义7.1.1，??G????G?，有k(G)=k-2。
证明：因为G是简单图 ,所以d(v)≦p-1,v∈V(G),已知δ(G)≧p-2 （ⅰ）若δ(G)= p-1,则G=Kp（完全图），故k(G)=p-1=δ(G)。
（ⅱ）若δ(G)= p-2, 则 G≠Kp,设u,v不邻接，但对任意的w∈V(G),有 uw,vw ∈E(G).于是，对任意的V1?V(G),
| V1|=p-3 ,G-V1必连通.
因此必有k(G) ≧p-2=δ(G),但k(G) ≦δ(G)。 故k(G) =δ(G)。
6．找出一个p阶简单图, 使??G??p?3, 但??G????G?. 解： 如图G，p?5,?(G)?2?p?3,?(G)?1??(G)。uG
7．设G为3?正则简单图, 求证??G????G?.
分析：G是一个3?正则简单图，所以δ(G)=3，根据定理7.1.1有??G????G???(G)，所以
30
1，2，3这四种情况。下面的证明中分别讨论了这四种情况下??G?和??G???G?只能等于0，的关系。
证明：(1)若??G?=0，则G不连通,所以λ(G)=K(G).
(2) 设 K(G)=1,且u 是G中的一个割点，G-u不连通,由于d(u)=3,从而至少存在一个分
支仅一边与u相连,显然这边是G的割边,故λ(G)＝１，所以λ(G)=K(G)
(３) 设K(G)=2,且{v1,v2}为G的一个顶点割。G1=G-v1连通,则v2是G1的割点且v2
在G1中的度小于等于３，类似于(2)知在G1中存在一割边e2(关联v2)使得G1-e2不连通．另一方面由于λ(G)>=K(G)=2故G-e2连通．由于G1-e2= (G-e2)-v1，故v1是G-e2的割点，且v1在G-e2中的度小于等于３，于是类似于(2)知，在G-e2中存在一割边e1，即(G-e2)-e1=G-{e1,e2}不连通，故λ(G)=2.所以λ(G)=K(G).
(４) 设k(G) =3,于是，
有3 =k（G） ≦ ) ≦δ(G)=3 ,知 ?（G）? ( G??(G)?3
8．证明：一个图G是2?边连通的当且仅当G的任意两个顶点由至少两条边不重的通路所连通.
分析：这个题的证明关键是理解2?边连通的定义。 证明：（必要性）因为G是2?边连通的，所以G没有割边。设u，v是G中任意两个顶点，由G的连通性知u，v之间存在一条路径P1，若还存在从u到v的与P1边不重的路径P2，设C=P1∪P2，则C中含u,v的回路，若从u到v的任意另外路径和P1都有一条（或几条）公共边，也就是存在边e在从u到v的任何路径中，则从G中删除e，G就不连通了，于是e成了G中一割边，矛盾。
（充分性）假设G不是一个2-边连通的，则G中有割边，设e=(u,v)为G中一割边，由已知条件可知，u与v处于同一简单回路C中，于是e处在C中，因而从G中删除e后G仍然连通，这与G中无割边矛盾。
9．举例说明：若在2?连通图G中, P是一条
?u,???通路, 则G不一定包含一条与P内部不相
交的?u,???通路Q。
u V1 V2 解 如右图G，易知G是2—连通的， 若取P为uv1v2v， 则G中不存在Q了。
31
G v
10．证明：若G中无长度为偶数的回路, 则G的每个块或者是K2, 或者是长度为奇数的回路.
分析：块是G的一个连通的极大不可分子图，按照不可分图的定义，有G的每个块应该是没有割点的。因此，如果能证明G的某个块如果既不是K2，也不是长度为奇数的回路，再由已知条件G中无长度为偶数的回路，则可得出G的这个块肯定存在割点，则可导出矛盾。本题使用反证法。
证明： 设K是G的一个块，若k既不是 K2也不是奇回路，则k至少有三个顶点，且存在割边e=uv,于是u,v中必有一个是割点，此与k是块相矛盾。
11．证明：不是块的连通图G至少有两个块, 其中每个块恰含一个割点.
分析：一个图不是块，按照块的定义，这个图肯定含有割点v，对图分块的时候也应该以割点为标准进行，而且分得的块中必定含这个割点，否则所得到的子图一定不是极大不可分子图，从而不会是一个块。
证明：由块的定义知，若图G不是块且连通，则G有割点，依次在有割点的地方将G分解成块，一个割点可分成两块，每个块中含G中的一个割点。如下图G。
易知 u,v是割点，G可分成四个块K1 ～K4 。其中每个块恰含一个割点。
k3vuvuk2v3Guvvk1k4
12．证明：图G中块的数目等于
??G???b????1? 其中, b???表示包含?的块的数目. ?????VG分析：一个图G的非割点只能分布在G的一个块中，即b???=1（当v是G的非割点时），且每个块至少包含一个割点。因此下面就从G的割点入手进行证明。证明中使用了归纳法。 证明：先考虑G是连通的情况（??G??1），对G中的割点数n用归纳法。 由于对G的非割点v，b(v)=1，即b(v)-1 =0，故对n=0时，G的块数为1?成立。
32
?b????1?结论?????VG
假设G中的割点数n≤k（k≥0）时，结论成立。
对n=k+1的情况，任取G的一个割点a，可将G分解为连通子图Gi，使得a在Gi中不是割点，a又是Gi的公共点。这样，每一个Gi，有且仅有一个块含有a，若这些Gi共有r个，则b(a)=r，又显然Gi的块也是G的块，且Gi的割点数li≤k。故由归纳法假设Gi的块的块数为1??b????1?(i?1,2,?,r)，这里b(v)是G中含v的块的块数，注意到G中异于a的v，????iii
i
?VGib(v)= bi(v)，而a在每一个Gi中均为非割点，故bi(a)(i?1,2,?,r)。于是Gi的块数为1??b????1?(i?1,2,?,r) ?????VGiv?a将所有Gi的块全部加起来，则得到G的块数为： r??b????1?=r???b????1?=1+(r-1) ???b????1?=1???b????1? ??????????????i?1?VGv?ar?VGv?a?VGv?a?VG由归纳法可知，当G连通时，结论成立。
当G不连通时，对每个连通分支上述结论显然成立。 因此有图G中块的数目等于
??G???b????1? ?????VG
13． 给出一个求图的块的好算法。
分析：设G是一个具有p个顶点，q条边，w个连通分支的图。求图G的块可先求图G的任一生成森林F，且对每一边e?F，求F+e中的唯一回路，设这些回路C1，C2，?，Cq-p+w都已求得，（这些都有好算法）。在此基础上，我们注意到，两个回路（或一个回路与一个块）若有多于1个公共点，则它们属于同一块。此外，由割边的定义知，G的任一割边不含于任何回路中，且它们都是G的块。基于这些道理，可得如下求图G的块的好算法。 解：
求图的块的算法：
（1）令s=1，t=1，n=q-p+w
（2）若n>0，输入C1，C2，?，Cn；否则，转第4步。
（3）若|V(Cs)?V(Cs?t)|?1且对i=s+t，?，n-1，令，令Cs?Cs?Cs?t，Ci?Ci?1，n?n?1，转第4步；否则，t=t+1，转第5步。
（4）若s （5）若s+t≤n转第3步；否则，s=s+1，转第4步。 本算法除了求回路有已知的好算法外，计算量主要在第3步，比较Cs与Cs?t的顶点寻 33 找它们的公共点的运算中，这些运算不超出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. ?分析：根据定理7.3.1，图Hm,n是m-连通图，因此有 ? （ H m ,n ） m ????又根据Hm,n的构造，可知 H m ,n ） ? m ，再由定理7.1.1可证。 ? （ 证明：由定理7.3.1知： ? （ H m , ? m n） 已知：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如下图： 254H4,8图3(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 071654(iii) H5.9图: 23H5,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?88701654H5,9图2336 习题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 题18知该图必含回路。 证明：将G中孤立点去掉以后得到图G1，显然G1也是一个无奇点的E图，且?(G1)?2。由第五章习题18知，G1必含有回路C1；在图G1-C1中去掉孤立点，得图G2，显然G2仍然是一个无奇点的图，且?(G2)?2，于是G2中也必含回路C2，?如此直到Gm中有回路Cm，且Gm-Cm全为孤立点为止，于是有： 5、求证：若G有2k>0个奇点，则G中存在k个边互不重的链 Q 1 , , Q k ,使得： ? E(G)?E(C1)?E(C2)???E(Cm)E(G)?E(Q1)?E(Q2)???E(Qk)分析：一个图的E回路去掉一条边以后，将得到一条E链。 证明：设 1, V 2 , ? , V k , V k ? 1 ,? , 2 k为 G 中的奇数度顶点，k≥1在Vi和Vi+k 之间用新边ei连VV接，ⅰ=1，2….k,所得之图记为G*，易知G*的每个顶点均为偶数，从而G*存在 E 闭链C* 。现从C*中删去ei （ⅰ=1，2….k），则C*被分解成 k 条不相交的链Qi(ⅰ=1，2….k),显然有: E(G)?E(Q1)?E(Q2)???E(Qk)6、 证明：如果 （1）G不是2—连通图，或者（2）G是二分图 ?(G)?1，于是?(G)?1或?(G)?0，如果?(G)?0，则说明G 不连通，如G不连通，显然G不是H图，如?(G)?1则G中存在孤立点，因此有ω(G-v)≥2，由定理8.2.1G不是H图。若G是二分图 证明：若（1）成立则G不连通或者是G有割点u，若G不连通,则G不是H图，若G有割点u，取S={u},于是ω(G-u)> S因此 G不是H图. 若（2）成立，不妨设X?Y.令S?X,则 ?（G?S）?Y?X?S 即：?（G?S）?S.因此 G不是H图. ?(G?S)?S?1. 38 7、证明：若 G 是半 H 图,则对于V(G)的每一个真子集S，有: '')分析：图G的权与它的生成子图 G 的连通分支数满足： ? ( G ) ? ? (G ，因为一个图的生成子图 是在该图的基础上去掉若干边得到的，显然去掉边以后只能使该图的连通分支增加。 ?对于图G的一条H通路C，满足任取S?V, ( C ? S ) ? S ? 1 . 证明:设C是G的一条H通路，任取S?V, 易知 ?(C?S)?S?1.而 C-S是 G-S 的生成子图. 故?(G?S)??(C?S)?S?1.故?(G?S)?S?1. 8、试述 H 图与 E 图之间的关系。 分析：H图是指存在一条从某个点出发经过其他顶点有且仅有一次的回路；而E图是指从某点出发通过图中所有的边一次且仅有一次的回路。从定义可看出，这两者之间没有充分或必要的关系。 解 ： 考虑如下四个图: G1G2G3G4 易知G1是E图，但非H图; G2是H图，但非E图; G3既非E图，又非H图；G4既是E图，也是H图。 9、作一个图，它的闭包不是完全图 分析：一个p阶图的闭包是指对G中满足d(u)+d(v)≥p的顶点u,v，若uv?E(G)，则将边uv加到G中，得到G+uv，如此反复加边，直到满足d(u)+d(v)≥p的所有顶点均邻接。由闭包的定义，如果一个图本身不存在任何一对顶点u,v，满足d(u)+d(v)≥p，则它的闭包就是其自身。显然可找到满足这种条件的非完全图。 G，G?G，但G不是完全图。 解：如右图 10、若 G 的任何两个顶点均由一条 H 通路连接着，则称G 是H连通的。 ??G?1?(1)证明：若G是H连通的，且p?4,则q??(3p?1)?.?2? ?1?? ? ( （2）对于p≧4，构造一个具有 q 3 p ? 1 ) ?的H连通图G。 ?2 39 ? 分析：根据定理5.3.1有2q?pd(vi)/2 ?d(v)，因此q??i?1ii?1pp而 ?d(v)?p??(G)，所以q≥p*δ(G)/2，因此如果能判断δ(G)≥3，则有 ii?1 q ? p ) / 2 ? 3 P / 2 ? ? (3 p ? 1 ) ? ;下面的证明关键是判断δ(G)≥3。 ? ?(G???2? 证明：（1）任取w∈V(G),由于G是连通的，所以d(w)≥1。 若d(w)=1,则与w邻接的顶点u与w之间不可能有一条H 通路连接它们，否则因为p≥4，所以G中除了u与w外还有其他顶点，因此，如果u与w之间有一条H通路的话，这条H通路与u与w的连线就构成了一个回路，这样与d(w)=1矛盾，所以d(w)≠1； 同样的道理，若d(w)=2，则与w邻接的顶点u与v之间不存在H通路。 因此δ(G) ≥3。 从而 2q=∑d(u)≥3p, 即：2q≥3p,也即q ≥ 3p/2 (ⅰ) 若p为奇数，于是 1q?1(3p?1);2(ⅱ) 若p为偶数，则3p为偶数，于是 ?1?q??(3p?1)?;?2??1?q?(3p?1)? 2 ?;综合以上各种情况 ，有： ?? （2）(ⅰ)当p=偶数时，q=3p/2，满足条件的图如下图(a); (ⅱ) 当p=奇数时， q ? ( 3 p ? 1 ) 满足条件的图如下图(b); ,?1?2????? ? 图(a) 40 ? ? 图(b) 11、证明：若G是一个具有 p≧2δ的连通简单图，则 G 有一条长度至少是2δ的通路。 分析：使用反证法，假设G 中没有一条长度大于或等于2δ的通路。先找到图G的一条最长通路P，设其长度为m，由假设m<2δ。再在P的基础上构造一条长度为m+1的回路C，显然C中包含的顶点数小<2δ，由于p≧2δ，所以图G至少还有一个顶点v不在该圈中，又由于G是连通的，所以v到C上有一条通路P’。于是P’+C的长度等于通路P的长度的通路构成了一条比P更长的通路，这与P是G的一条最长通路矛盾。从而本题可得到证明。 证明：(用反证法)设 P ? V ? V是G的最长通路,其长度为m，假设m<2δ。 V由P是G的最长通路，则V1,Vm+1只能与 P中的顶点相邻，注意到 G 是简单图 令S?{viv1vi?1?E(G)},T?{vivm?1vi?E(G)} ?S?d（v1）??，T?d（vm?1）??。12m?1由定义知：vm?1?S?T,因此，S?T?m?2?,于是S?T??, 事实上，?2??S?T?S?T?S?T?????S?T?2??S?T S?T?0,即S?T??。? 设vi?S?T??,从而有G中的长为m?1的回路C：v1v2?vivm?1vm?vi?1v1.因p?2?,m?1?2?,所以，C外至少还有一个顶点v0?V（G）。 由G连通可知，有一条P外的通路与C连接。不妨设v0vj?E（G），1?j?m?1. 是有通路P?：vvv?vv?vvvv?v.且P??P,此与P的假设矛盾！0jj?11i?1mm?1ii?11 故结论成立。 12、设p(?3)阶简单图G的度序列为：d1?d2???dp.证明：若对任何m,1 1?m?(p?1)/2,均有dm?m若p为奇数，还有d1?（p?1）则G是H图。（p?1） 41 22 但 ?pi?1ki?p,?qi?q，?ri?r?k?1 i?1i?1kk故 p?q?r?k?1?2k 即 p?q?r?k?1 7．证明：k5?e是平面图，其中e∈E（K5） 分析：由于k5 的对称性,只须考虑其中的一条边e，验证k5?e是可平面图即可. 证明：任选k5的某条边e，则k5?e如下图所示，显然这是一个平面图。 8．证明：k3,3?e是平面图，其中e∈E（K3，3） 分析：仿照第7题，由于k3,3的对称性，因此也只须考虑其中的一条边e，验证k3,3?e是可平面图即可. 证明：任选k3,3的某条边e，则k3,3?e如下图所示，显然是一个平面图。 9．一个图的围长是图中最短回路之长度，若图中无回路，则围长定义为无穷大。证明：如果G(p,q,r)是连通平面图，围长g≥3且有限，则 q≤g(p-2)/(g-2) )?分析：由定理11.1.1 对任何平面图G(p,q,r)，满足 d ( f i 2 q ，又由于G是简单连通图， i?1?r因此还满足欧拉公式p?q?r?2。利用这两个结论可证明本题。 67 证明:由于G的围长为g,故d(fi)≥g，由定理11.1.1知： r gr?d(fi)?2q i?1?可以得到 r?2q/g将它代入Euler公式就可以得到q≤g(p-2)/(g-2) 10．利用题9证明Peterson图是不可平面图。 分析：Petersen图参看书上80页的图10.2.，由图可知道，g=5.p=10,q=15比较q和g(p-2)/(g-2)， 将会发现不满足条件q≥g(p-2)/(g-2)，因此Peterson图是不可平面图。 证明： Petersen图中顶点数p=10，边数q=15，围长g=5 g(p-2)/(g-2)=5*（10-2）/（5-2）=40/3<15=q 不满足9题的结论,所以Peterson图是不可平面图. 11．图11-11是可平面图吗？若是，则请给出平面嵌入，否则说明它是一个包含K5或K3，3的剖分图。 (a） (b） (c） 图11-11 (d） 分析：存在一个平面嵌入的图是可平面图，因此利用这个定义如果能找到G的一个平面嵌入，则可以判断这个图是可平面图。再由定理11.3.1一个图是可平面图的充分必要条件是该图不包含一个K5或K3，3的剖分图，利用这个定理如果能找到一个图的K5或K3，3的剖分图，则该图不是可平面图。 解：这四个图均是平面图，其平面嵌入分别如下所示： 68 (a） (b） (c） 图11-11 12．平面M上有n条直线将平面M分成若干区域，为了使相互邻接的区域着不同的颜色，最少需要几种颜色？ 分析：先将r个区域编成号（如图12-1所示）。 将直线的交点看做图的顶点，所有无限区域的两条无限边都交于一顶点v（等价于所有直线的两端均在无穷远点相交），所得图的示意图为图12-2所示。显然12-2所示的面数与12-1的区域数相同，并且12-1中所示图是区域2-可着色的，当且仅当12-2中所示的图是面2-可着色的。可是12-2是无环的E平面图，利用13题结论可知12-2是面2-可着色的，从而12-1所示的图是区域2-可着色的。 解：最少需要两种颜色。 (d） 1 2 6 7 4 5 图12-1 3 6 1 2 7 4 5 3 图12-2 69 13．设G是一个连通的平面地图，证明?*(G)?2当且仅当G是欧拉图。 分析：本题的证明利用了图G和其对偶图G*的关系以及第16题的结论：G是二分图当且仅当G*是欧拉图。 又G是点2-可着色的当且仅当G是二分图。因为若G是点2-可着色的，则G中的所有顶点可按着的颜色划分为两个集合，显然着相同颜色的顶点互不邻接，因此这两个集合中的任意两个顶点不邻接，因此G是二分图；反过来，如G是二分图，则G中的所有顶点可划分为两个集合，且每个集合中任意两个顶点不邻接，因此按G的这两个集合将G中所有顶点着两种不同的颜色，是G的正常2着色，因此?(G)?2。 证明：设G是一连通的平面地图，则G是一无割边的连通平面图，设G*是G的对偶图，则G*是无环的连通的平面图，因此G是面2-可着色的当且仅当G*是点2-可着色的，而G*是点2-可着色的当且仅当G*是二分图，由题16结论有G*是二分图当且仅当G是欧拉图。 14．将平面分成r个区域，使任意两个区域都相邻，问r最大为多少？ 分析：显然当r=1，2，3，4时，可以构造出满足条件的图，如下图是当r=4时满足条件的平面图 *f0 f1 f3 f2 因此如果能证明不存在具有5个或5个以上面的平面图，其每两个面都共享一条边。则满足条件的r最大为4。 解：r最大为4。 证明：假设存在这样的平面G，设G的对偶图为G*，则G*也是平面图。由于G至少有5个面，所有G*至少具有5个顶点。设v*为G*的任一顶点，设它位于G的面R中，由于R与其余至少4个面均有公共边，所有v*与其余面中的顶点均相邻，于是d(v*)≥4，而且G*为简单图，于是G*必为Kn(n≥5)，当n=5时，显然K5为非平面图，当n>5时，由于Kn包含一个K5的剖分，所以Kn也不是平面图，这与G*为平面图矛盾。 15．证明：在平面上画有限个圆所得的地图是两色的，即有一个正常2面着色。 分析：本题的证明主要用到了欧拉图的概念和13题的结论，即图G是欧拉图当且仅当G无奇数度的顶点以及G是欧拉图当且仅当?(G)?2。 证明：在平面上画有限个圆所得的地图G显然是一个欧拉图，由13题结论有?(G)?2，即G 70 ** 是两色的。 16．设G是平面图，证明：若G是二分图，则G*是欧拉图，又若一个平面图的对偶图是欧拉图，则此平面图是二分图。 分析：该题的证明主要用到了二分图的定义、欧拉图的判定定理及图G的对偶图G*中的顶点的度与G中对应面的次数的关系。即图G是二分图当且仅当G中无奇数长度的回路，而图G是欧拉图当且仅当G无奇数度的顶点。而G*的顶点的度等于图G对应面的次数之和。 证明：设G*是G的对偶图，则G*是连通的，若G是二分图，则G中无奇数长度的回路，因此G*中所有顶点的度数均为偶数，所以G*是欧拉图。 若G*是欧拉图，所以G*中每个顶点的度数都为偶数，所以G中无奇数长度的回路，因此G为二分图。 17．若一个平面图与它的对偶图同构，则称此图是自对偶的，试证明：若G（p,q）是自对偶的，则q=2p-2 分析：由对偶图及同构的定义有：如G（p,q,r）是一个自对偶图，图G*(p*,q*,r*)是它的对偶图，则有p*=r ，q*=q，p=p*,q=q*,r=r*；又因为G是平面图，因此满足欧拉公式p-q+r=2。最后可得q=2p-2。 证明：设G（p,q,r）是一个自对偶图,图G*(p*,q*,r*)是G的对偶图。 则由对偶图的定义有：p*=r q*=q 有G与G*同构，因此有p=p*,q=q*,r=r* 又G是一个平面图，所以p-q+r=2 于是有：2p-q=2 即q=2p-2 18．画一个非简单图的自对偶图。 分析：一个图G的对偶图是按如下方式构造出来的： 在G的每个面f内放上一个顶点f*，这些顶点就构成了G*的顶点集V(G*)，若G的两个面f和g有一条公共边e，则画一条以f*和g*为端点的边e*仅穿过e一次；对于G中属于一个面的割边e，则画一条以f*为端点的环仅穿过e一次。非简单图是有环或重边的图。按照第17题有自对偶图是图G与它的对偶图G*同构的图。由这几方面的定义，可构造如下非简单图的自对偶图。 解：非简单图的自对偶图如下图所示。 G G* 习 题 十 二 71 百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第二在线全文阅读。
相关推荐：
