图G无向连通图,G中有割点或桥,则无汉密尔顿图,怎么证明
题目
图G无向连通图,G中有割点或桥,则无汉密尔顿图,怎么证明
如题
就是证明这条定理,不用图
请问lca001,为什么连结桥的两个结点必有一个结点是割点?
答案
首先证明G中有割点,则G不是汉密尔顿图,反证法,如果图G是汉密尔顿图,则必存在汉密尔顿圈(回路),即所有结点均在一个回路中,此时删除任意一个结点图G必连通,于是它的任何点均不是割点,矛盾,即有割点的图不是汉密尔顿图....
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
热门考点