================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

为此，我们证明： 对任意二顶点u和v，都有deg(u)+deg(v)≥h-１。分情况

证明如下： 1）若u和v相邻，则有 deg(u)+deg(v) ≥(n-2)+2=n＞n-1 2）

若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的一个划分{X，Y}，有两上划分块，而 划分和等价关系对应，因此我们将判定G是二分图转化为判定

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 11 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

某一相应的关系是等价关系。 u v w 其余n-2个 顶点 ?1 ,当(vi,vj)或(vjvi)? 令A：=(aij)nxn，其中aij=? 0 ,否则? No2. 求A：=AοA=(a(2) (2)ij)nxn，其中a(2)ij=?(aik∧akj)。 k?1nvi，vj∈XVY， (2)=1? vi，vj∈Y aijNo3. 令B：=E∨A(2)=(bij)，其中 23 ,当i?j时?1 bij=?(2) a ,当i?j时 .(则B显然是自反的对称的.)?ijNo4. 求B=BB= E是n阶单位）其中b (2) ij= k?1?(bik∧bkj)。 nNo5. 求B(2)=B，输出“图G是二分图”，出 口；否则输出“G不是二分图”，出口。 n228．证明：如果G是二分图G为图，那么m? 。 4[证] 设二分图G=的项点集V是划分为二部分X，Y。因为| V |=n，所以不 妨设|X|?nn?k，从而|Y|??k。 22 因于二分图的边数小于其对应的完全二分图的边数 故此： nnn2n22?k? m?(?k)(?k)? 222429．设G=是二分圈，V=V1∪V2，证明： 1）若G中

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 12 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

有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=是二分图中的一条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

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 13 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

|个孤立点。因此习题23有Hamilton路的必要条件，可知 | V1 |=W(G\\\\V2)≤|V2 |+1 | V2 |=W(G\\\\V1)| V1 |+1，于是| V2|-1≤|V1| 故此 | V1 |-1≤| V1 |≤|V2 |+1 。 证法二：设C=是二分图中的一条Hamilton路，从而V={v1，v2，?，v }，于是| V |=τ。根据1）的证法二： 若v1∈V1，vτ∈V1，则vτ-1∈V2 故此τ-1为偶数，τ为奇数，于是 | V1 |= ??1?-1?1, 而| V2|? 因此 22 | V1 |=|V2 |+1 若v1∈V1 vτ∈V1，则τ为偶数，于是 | V1 |= ?=| V2| 2 若v1∈V2，vτ∈V1，同可证| V1 |=|V2| 若v1∈V2，vτ∈V2，则同可证 | 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

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 14 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

[解] 不存在{v1，v2，v3，v4}到{u1，u2，u3，u4，u5}的完美匹配。 因为这两个互补结点子集的结点个数不相同。 31．某展览会共有25个展室，布置如下图所示，有阴影的展室陈列实物，无阴影的 展室陈列图片，邻室之间均有门可通。有人希望每个展室都恰去一次，您能否为他设计一条路线？ [解] 不能。 因为，若我们将每个展室看作一个项点，并且V1是无阴影展室的项点集，V2是有阴影展室的项点集，将邻室之间的门通道看作相应两顶点的边，于是我们得到一个二分图G。从而问题转化为问图G中是否有从起点uv1到终点v∈V2的一条Hamilton路？而这样的H路存在的必须条件是| V1|=| V2|证法=b))。但是|V1|=121≠3=|V2|，故不满足必要条件，所以没有从u到v的Hamilton路。 32．证明：小于30条边的平面简单图有一个结点的度数小于等于4。 [证] 用反法：假设简单平面

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 15 ~