> 数学 >
哈密尔顿图证明题
设G是简单图,删去G中任一边e,则G-e是一棵生成树.证明是哈密尔顿图
人气:290 ℃ 时间:2020-07-12 23:01:03
解答
根据题意可得g为一个有回路的简单图,然后假设有点不再回路上,去掉与这个点相连的边,与G-e是一棵生成树是一颗生成树矛盾,所以所有点必在这个回路上,所以必为哈密尔顿图
推荐
猜你喜欢
© 2026 79432.Com All Rights Reserved.
电脑版|手机版