以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [离散习题8.2] 无向连通图G为欧拉图当且仅当G的每个块都是欧拉图  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=30619)


--  作者:Logician
--  发布时间:4/15/2006 1:25:00 PM

--  [离散习题8.2] 无向连通图G为欧拉图当且仅当G的每个块都是欧拉图
证明:


充分性。

每个块都是欧拉图的话,那么每个顶点在各自所属的块中都是偶数度的。
我们要证明,每个顶点在G中也是偶数度的。

首先,若A={G_i|i=1,2,...,k}是G中所有的块的话,则G=∪A。

其次,对任意G_i,G_j,若i≠j,则V(G_i)∩V(G_j)中至多只有一个顶点
(否则G_i∪G_j将是一个更大的2-连通图,与G_i、G_j的极大性矛盾)。

这样,G_i∩G_j要么是空图,要么是只有1个顶点的图。若这个图中有边,
也只能是环,从而顶点在G_i∩G_j中的度数也是偶数。

利用度数的定义和容斥原理可以知道,v在G中的度数d_{G}(v)=Σd_{G_i}(v)
- Σd_{G_i∩G_j}(v) + Σd_{G_i∩G_j∩G_k}(v) - ..... + (-1)^{n+1}∩A

对上面的公式中,若v不在V(G_i)中,则规定d_{G_i}(v)=0。

由于G_i是欧拉图,所以d_{G_i}(v)是偶数,由于G_i∩G_j要么没有边,要么只
有环,所以d_{G_i∩G_j}(v)也是偶数。从而d_{G}(v)也是偶数。


必要性。

由于任何欧拉图都是若干边不重的圈的并。
设这些圈是C_1,C_2,...,C_k(注意:如果G中有环,则每个环本身也是一个圈)。
容易证明,任意圈C_i如果与某个块G_j有公共边,则C_i必是G_j的子图。(这是因为:
若C_i为环,则结论显然成立。否则,C_i中有非环的边(u v),由于C_i本身是2-连通
的,所以C_i可以扩展成了一个块G_t。由于G_t和G_j有公共边(u v),从而有两个公共
顶点。上次已经证明了,两个不同的块最多有一个公共顶点,所以必有G_t=G_j,而
C_i是G_t的子图,也就是G_j的子图)。

因此,对每个块G_i,设A_i={C_{j_1},C_{j_2},...,C_{j_s}}为所有与G_i有公共
边的圈的集合。
由于C_1,C_2,...,C_k覆盖了G中每一条边,所以G_i是∪A_i的子图。
另一方面,由于A_i中每一个圈都是G_i的子图,所以∪A_i也是G_i子图。
从而G_i=∪A_i也是若干边不重的圈的并。


--  作者:yrf
--  发布时间:4/15/2006 1:48:00 PM

--  
充分性。

每个块都是欧拉图的话,那么每个顶点在各自所属的块中都是偶数度的。
我们要证明,每个顶点在G中也是偶数度的。

首先,若A={G_i|i=1,2,...,k}是G中所有的块的话,则G=∪A。

其次,对任意G_i,G_j,若i≠j,则V(G_i)∩V(G_j)中至多只有一个顶点
(否则G_i∪G_j将是一个更大的2-连通图,与G_i、G_j的极大性矛盾)。

其实,到这一步是不是就可以说明G为欧拉图了?
因为对于任意G_i,G_j至多只有一个顶点(若有的话设为v。),又因为v。在G_i和G_j中的度都是偶数,那么,它在G_i∪G_j中的度数也为偶数。进而,对于所有的G_k(v。属于G_k),
∪G_k中v。的度也为偶数。又有“若A={G_i|i=1,2,...,k}是G中所有的块的话,则G=∪A”所以G
为欧拉图


--  作者:yrf
--  发布时间:4/15/2006 1:58:00 PM

--  
还是你的对,我做的时候没考虑有环的情况。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
46.875ms