|
以文本方式查看主题 - 计算机科学论坛 (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的每个块都是欧拉图 证明: 每个块都是欧拉图的话,那么每个顶点在各自所属的块中都是偶数度的。 首先,若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要么是空图,要么是只有1个顶点的图。若这个图中有边, 利用度数的定义和容斥原理可以知道,v在G中的度数d_{G}(v)=Σd_{G_i}(v) 对上面的公式中,若v不在V(G_i)中,则规定d_{G_i}(v)=0。 由于G_i是欧拉图,所以d_{G_i}(v)是偶数,由于G_i∩G_j要么没有边,要么只 由于任何欧拉图都是若干边不重的圈的并。 因此,对每个块G_i,设A_i={C_{j_1},C_{j_2},...,C_{j_s}}为所有与G_i有公共 |
|
-- 作者:yrf -- 发布时间:4/15/2006 1:48:00 PM -- 充分性。 每个块都是欧拉图的话,那么每个顶点在各自所属的块中都是偶数度的。 首先,若A={G_i|i=1,2,...,k}是G中所有的块的话,则G=∪A。 其次,对任意G_i,G_j,若i≠j,则V(G_i)∩V(G_j)中至多只有一个顶点 其实,到这一步是不是就可以说明G为欧拉图了? |
|
-- 作者:yrf -- 发布时间:4/15/2006 1:58:00 PM -- 还是你的对,我做的时候没考虑有环的情况。
|
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
46.875ms |