作业帮 > 数学 > 作业

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

来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/03/29 23:10:05
离散数学证明题:设连通图G有k个奇数度的结点,证明在图G中至少要添加k/2条边才能使其成为欧拉图.
图G是欧拉图的充要条件是图G连通且所有的结点的度数都是偶数,因此要使连通图G成为欧拉图,既是要使所有的结点度数变为偶数.
添加一条边后,可能会出现两种情况:
1、边的两端连接在同一个结点上(环),此时该点的度数加2,奇偶性不变;
2、边的两端连接在两个不同的结点上,此时此两点的度数各加1,两个点改变奇偶性.
如题,图G有k个奇度数的结点,要使该图成为欧拉图,需要改变这k个结点的奇偶性,因此最少需要添加k/2条边.