以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  急！！求问！！  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=79511)

--  作者：sky_18219
--  发布时间：1/14/2010 2:39:00 PM

--  急！！求问！！
证明：图G是连通的，G是eulerian的当且仅当G的每点的度是偶数

证明：图G是连通的平面图，其点数为n，边数为e，则n-e+f=2

就这两道 谢谢！！！急啊…………

--  作者：sky_18219
--  发布时间：1/14/2010 2:46:00 PM

--  
急……………………死我了
--  作者：xuchao1221
--  发布时间：1/14/2010 8:35:00 PM

--  
问题一:因为G是欧拉图,则G中存在欧拉回路,设C是G的一条欧拉回路,C=v0v1...vm(v0=vm),则对于任意v，在C中出现一次就获得2度，若出现k次，就获得2k度，即v的度数是偶数。

问题二：（数学归纳）对边数m进行归纳：
（1）m=0，因为G是连通图，所以为平凡图，结论成立。
（2）设当m=k（k〉=1）时结论成立，下面证m=k+1时结论成立：
     1〉若G是树，则G为非平凡树，因而G中存在树叶，设v为G的一片树叶，令G‘=G-v，则G’仍然连通，则G‘边数m’=m-1，由归纳假设知 n'-m'+r'=2，其中n' r'分别为G‘的顶点数和面数，而
n'=n-1，r‘=r，所以n-m+r=(n'+1)-(m'+1)+r'=n'-m'+r'=2.
        2>若G不是树，则G中必含圈，设e为G的某圈上的一条边，令G'=G-e,则G‘仍然是连通的，且m'=m-1=k,有归纳假设知 n'-m'+r'=2,其中n'=n,r'=r-1,所以
    n-m+r=n'-(m'+1)+(r'+1)=n'-m'+r'=2.

--  作者：sky_18219
--  发布时间：1/16/2010 1:38:00 AM

--  
佩服~！
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 93.750ms