问答题
证明:有桥的图不是哈密顿图.
【正确答案】
利用定理的推论(有割点的图一定不是哈密顿图)证明本题.
设G为带桥(割边)e的连通无向图.若G是含e的K
2
,G当然不是哈密顿图,否则,G的阶数n≥3,设桥e=(u,v),则由于G的连通性,u与v中至少有一个不是悬挂顶点,不妨设u不是悬挂顶点,可知,u是割点,由定理的推论可知,G不是哈密顿图.
【答案解析】
提交答案
关闭