3）画一个图示，使它没有一条E—圈，但有一条H—圈； 4）画一个图示，使它既没有一条E—圈，又没有一条H—圈； [解] （a）图1既有E-圈，又有H圈。
（b）图2有E-圈，但没有H-圈。 （c）圈3有H-圈，但没有E-圈。 （d）图4既没有E-圈，又没有H-圈。
图1 图2 图3 图4
图2不存在H-圈，是因为存在着S={中间点}，使W（G\\S）=2个连通支数，而| S |=1，从而W（G\\S）?| S |故由定理1判定H-图的必要条件可知不存在H-圈。
图3不存在E—圈，是因为G中存在8个结点的度均为3，是奇数。图4中不存在H—圈，因为G是一个偶图（二分图），而偶图要有圈，必须结点数为偶数（即|X|=|Y|,|V|=|X|+|Y|=2|X|），而G的结点数为11个，是奇数，不是偶数。 23．若G=（V，E）有Hamilton路，证明对V中任一非空子集S，均有W(G\\S)| S |+1。 [证] 设G=（V，E）中的Hamilton路为C，路的两个端点为v1，及v2。我们给G增
加一个新结点，v*及两个新边（v*，v1）和（v*，v2）而得到图G*，于是G*中就有Hamilton圈G*（它由Hamilton路C及关联新点v*的两个新边构成）。令S*=S∪{v*}，则显然有G\\S=C*\\S*。从而根据定理1有Hamiltou圈的必要条件，有 W（G\\S）=W（G*\\S*）≤|S*|=|S|+1 。 24．雄辩地证明下面的图示中没有Hamilton路。
图1
[证] （1）将图1标记为图3。
图2
图3中存在着Hamilton路，此如H=（b，c，h，g，k，i，d，e，a，f，j）
21
但是，图3中不存在Hamilton圈。因为，结点e，j均为2度结点，故若Hamilto
圈，则引H-必通过e，j及其关联的四条边，因此在边（a，e）及（f，j）上各增加一个结点l，m，得到图4，显然，图1，即图3有H-圈当且仅当图4有H-圈。 取S={a，e，l，g，i，c}，则G\\S={m，f，j，k，b，h，d}这7个孤立点，
因此W（G\\S）=7，而|S|=6，故此有 W(G\\S)?|S|
根据定理1，有H-圈的必要条件，知图4中没有
H-圈，因此图中没有H-圈。 （2）图2中不存在H路。
证法一：将图中偶结点全标为A，奇结点全标为
B，取S={偶结点}则G\\S为8个孤立奇结点，于是W=8，而| S |=6。从而有W（G\\S）?|S|+1，于是根据第23题的结论，有H-路的必要条件，知无H-路存在。
证法二：注意到图中的标号，奇、偶结点交错，
A B B B B A A B A B A B B B A 图5 因此是一个偶图（二分图）于是若有H-路，则奇偶结点之差不得超过1。但是这里奇结点（标为B）有8个，偶结点（标为A）有6个，其差为2。所以不可能有一条H-路。
25．有七位客人入席，A只会讲英语；B会讲汉语；C会讲英语，意大利语及俄语；
D会讲汉语及日语；E会讲意大利语及德语；F会讲法语，日语及俄语；G会讲德语和法语。问主人能否把诸位安排在一张圆桌上，使每一位客人与左右邻不用翻译便可交谈。若能安排，请给出一个方案。 [解] 能安排，其方案为：
H=（A，B，D，F，G，E，C，A） 将每个人作为一个项点，如果两个人会
讲同一种语言，就在代表他们的二个项点间连一条边，边上标明二人公用的语言，这样就可得一简单无向图G。所求问题转化为图G中有无Hamilton圈问题。
图G
E C 英语 G 德语 F 俄语 英语 D B 英语 A 而上边指出的圈H正好是图G的一条Hamilton圈，因此问题得到解决。 26．假设在一次集合上，任意两人合起来能够认识其余n-2 个人。证明这n个人可以
排成一行，使得除排头与排尾外，棋逢对手余的每个人都认识自己的左右邻。
22
[证] 我们来构造一个n阶图G，图G的项点代表n个人，两个认识的人对应的顶点
间连一条边，从而图G满足：
对任意二顶点u和v，都有deg(u)+deg(v)≥h-2（不包括u，v在内）。 所求问题转化为，证明图G中存在一条Hamilton路。为此，我们证明： 对任意二顶点u和v，都有deg(u)+deg(v)≥h-１。分情况证明如下： 1）若u和v相邻（即u和v表示之二人认识），则有
deg(u)+deg(v) ≥(n-2)+2=n＞n-1
2）若u和v不相邻（即u和v表示之二人不认识）则仍有
deg(u)+deg(v) ≥n-1＞n-2
否则，由已知deg(u)+deg(v)≥n-2知deg(u)+deg(v)=n-2。那么，G中除u和v外
的余n-2个点，每个顶点都恰与u或v之一相邻。今考察其中一点w，设它与v相邻，则它必不与u相邻。于是对于v，w这一对顶点，它们都不与除去它们之后的n-2个顶点中之一顶点u相邻，这就与题设条件：任二顶点合起来都与其余n-2个项点相邻，相矛盾。
综合1），2）并且根据定理2，有Hamiltou
路的充分条件，可知图G中存在着一条H路。 27．如何由无向图G的邻接矩阵判断G是否为二分图？
[解] 二分图G=（V，E）实际上是项点集V的一个划分{X，Y}，有两上划分块，而
划分和等价关系对应，因此我们将判定G是二分图转化为判定某一相应的关系是等价关系。
u v w 其余n-2个
顶点
?1 ,当(vi,vj)或(vjvi)?E.No1. 令A：=(aij)nxn，其中aij=?
0 ,否则?（于是A显然是对称短矩阵，即AT=A。） No2. 求A：=AοA=(a(2)
(2)ij)nxn，其中a(2)ij=?(aik∧akj)。
k?1n（由于(A(2))T=ATοAT=AοA= A(2) 故A(2)是对称矩阵。）vi，vj∈XVY，
(2)=1? vi，vj∈Y（同时） aijNo3. 令B：=E∨A(2)=(bij)，（其中E是n阶单位）其中
23
,当i?j时?1 bij=?(2)
a ,当i?j时 .(则B显然是自反的对称的.)?ijNo4. 求B=BB=（b
(2)
(2)
，（其中ij）
E是n阶单位）其中b
(2)
ij=
k?1?(bik∧bkj)。
nNo5. 求B(2)=B，（即B是传递的，因而是等价的。）输出“图G是二分图”，出
口；否则（即B不是传递的，因而不是等价的。）输出“G不是二分图”，出口。
n228．证明：如果G是二分图G为（n，m）图，那么m? 。
4[证] 设二分图G=（V，E）的项点集V是划分为二部分X，Y。因为| V |=n，所以不
妨设|X|?nn?k，（这里k≥0）从而|Y|??k。 22 因于二分图的边数小于其对应的完全二分图的边数
故此：
nnn2n22?k? m?(?k)(?k)?
222429．设G=（V，E）是二分圈，V=V1∪V2，证明： 1）若G中有H—圈，则| V1 |=| V2 |；
2）若G中有H—路，则| V2|-1≤| V1|≤|V2|+1 。
[证] 1）证法一：若G中有H—图，由于G是二分图，则在G 中去掉V2后，就只剩
下V1中的| V1 |个孤立点；同样，在G中去掉V1后，就只剩下V2中的| V2 |个孤立点。因此由定理1，有Hamilton圈的必要条件，可知： | V1 |=W(G\\V2)≤| V2 |，| V2 |=W(G\\V1)≤| V1 |
因此，可得| V1 |=| V2 | 。
证法二：设C=（v1，v2，v3，?，vl-1，vl，v1）是二分图中的一条Hamilton圈，从而有V={v1，v2，?vl}，于是| V |=l。
不妨设v1∈V1，观察圈C中的各结点，有： v1∈V1?v2∈V2?v3∈V1? v4∈V2???vτ∈V2 从而有v1，v3?，vτ-1∈V1∪V2，故此 V1={v1，v3，?vτ-1}，V2={v2，v4，?vτ} 所以
24
| V1 |=
?=| V2 | 。 22）证法一：若G中有H—路，由于G是二分图，则在G中去掉2后，就只剩下V1中的| V1 |个孤立点；同样，在G中去掉V1后，就只剩下V2中的| V2 |个孤立点。因此由习题23有Hamilton路的必要条件，可知
| V1 |=W(G\\V2)≤|V2 |+1
| V2 |=W(G\\V1)| V1 |+1，于是| V2|-1≤|V1|
故此
| V1 |-1≤| V1 |≤|V2 |+1 。
证法二：设C=（v1，v2，?vτ）是二分图中的一条Hamilton路，从而V={v1，v2，?，v }，于是| V |=τ。根据1）的证法二：
（a）若v1∈V1，vτ∈V1，则vτ-1∈V2 故此τ-1为偶数，τ为奇数，于是 | V1 |=
??1?-1?1, 而| V2|? 因此 22 | V1 |=|V2 |+1
（b）若v1∈V1 vτ∈V1，则τ为偶数，于是 | V1 |=
?=| V2| 2 （c）若v1∈V2，vτ∈V1，同（b）可证| V1 |=|V2| （d）若v1∈V2，vτ∈V2，则同（a）可证 | V2 |=|V1|+1，即|V2|-1=| V1| 综合以上四点，有
| V2|-1≤|V1|≤|V2|+1 。
30．在下面的图示中，是否存在{v1，v2，v3，v4}到{u1，u2，u3，u4，u5}的完美匹配？
若存在，请指出它的一个完美匹配。
u1 u2 u3 25
u4 u5 v1
v2
v3
v4