哈密顿图


定义

通过图中所有顶点一次且仅一次的通路称为哈密顿通路。

通过图中所有顶点一次且仅一次的回路称为哈密顿回路。

具有哈密顿回路的图称为哈密顿图。

具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图。

性质

是哈密顿图,则对于 的任意非空真子集 ,均有 。其中 的连通分支数。

推论:设 是半哈密顿图,则对于 的任意非空真子集 ,均有 。其中 的连通分支数。

完全图 中含 条边不重的哈密顿回路,且这 条边不重的哈密顿回路含 中的所有边。

完全图 中含 条边不重的哈密顿回路,从 中删除这 条边不重的哈密顿回路后所得图含 条互不相邻的边。

充分条件

的无向简单图,若对于 中任意不相邻的顶点 ,均有 ,则 中存在哈密顿通路。

推论 1:设 的无向简单图,若对于 中任意不相邻的顶点 ,均有 ,则 中存在哈密顿回路,从而 为哈密顿图。

推论 2:设 的无向简单图,若对于 中任意顶点 ,均有 ,则 中存在哈密顿回路,从而 为哈密顿图。

阶竞赛图,则 具有哈密顿通路。

阶竞赛图作为子图,则 具有哈密顿通路。

强连通的竞赛图为哈密顿图。

阶强连通的竞赛图作为子图,则 具有哈密顿回路。

贡献者:@mgt@Ir1dXD

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组