图G无向连通图,G中有割点或桥,则无汉密尔顿图,怎么证明

图G无向连通图,G中有割点或桥,则无汉密尔顿图,怎么证明
如题
就是证明这条定理,不用图
请问lca001,为什么连结桥的两个结点必有一个结点是割点?
wuzhipeng1 1年前 已收到1个回答 举报

想放弃孤单的ww 幼苗

共回答了17个问题采纳率:100% 举报

首先证明G中有割点,则G不是汉密尔顿图,反证法,如果图G是汉密尔顿图,则必存在汉密尔顿圈(回路),即所有结点均在一个回路中,此时删除任意一个结点图G必连通,于是它的任何点均不是割点,矛盾,即有割点的图不是汉密尔顿图.
另一方面,如果它有桥,则连结桥的两个结点必有一个是结点是割点,除非它是仅有一条边的图,显然这种情况它没有汉密尔顿回路,因此不是汉密尔顿图,如果不是这种情况,它必有割点,由上可知它也不是汉密尔顿图.

1年前

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