内容发布更新时间 : 2024/12/23 17:16:48星期一 下面是文章的全部内容请认真阅读。
================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============
为此,我们证明: 对任意二顶点u和v,都有deg(u)+deg(v)≥h-1。分情况
证明如下: 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 ~