★ 形成性考核作业 ★
7
四、证明题
1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．
证明：设a 为G 中任意一个奇数度顶点，由定义，a 仍为顶点，为区分起见，记为a ’, 则deg(a)+deg(a ’)=n-1, 而n 为奇数，则a ’必为奇数度顶点。由a 的任意性，容易得知结论成立。
2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2
k 条边才能使其成为欧拉图．
证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则k 是偶数。又由欧拉图的充要条件是图G 中不含奇数度结点。因此，只要在每对奇数度结点间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图。故最少要加条边才能使其成为欧拉图。
百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库2024国家开放大学离散数学(本)形考任务4答案(7)在线全文阅读。
相关推荐：
