离散数学证明题:设连通图G有k个奇数度的结点,证明在图G中至少要添加k/2条边才能使其成为欧拉图.

sxm1985518 1年前 已收到1个回答 举报

爱我不悔 幼苗

共回答了18个问题采纳率:94.4% 举报

图G是欧拉图的充要条件是图G连通且所有的结点的度数都是偶数,因此要使连通图G成为欧拉图,既是要使所有的结点度数变为偶数.
添加一条边后,可能会出现两种情况:
1、边的两端连接在同一个结点上(环),此时该点的度数加2,奇偶性不变;
2、边的两端连接在两个不同的结点上,此时此两点的度数各加1,两个点改变奇偶性.
如题,图G有k个奇度数的结点,要使该图成为欧拉图,需要改变这k个结点的奇偶性,因此最少需要添加k/2条边.

1年前

4
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.029 s. - webmaster@yulucn.com