问答题
证明:有割边的无向连通图不是欧拉图,有割点的无向连通图不是哈密顿图.
【正确答案】
(1)若连通无向图G有割边e,则过e一次且仅一次的回路不存在,故G不是欧拉图.
(2)若连通图有割点v,则W[G-{v}]>1,这与G为哈密顿图的必要条件W[G-{v}]≤|{v}|矛盾,故G不是哈密顿图.
【答案解析】
提交答案
关闭