哈密顿图
1. 定义
1.1 哈密顿通路 & 哈密顿回路
- 经过图（无向图或有向图）中所有顶点一次且仅一次的通路称作哈密顿通路。
- 经过图（无向图或有向图）中所有顶点一次且仅一次的回路称作哈密顿回路。
1.2 哈密顿图 & 半哈密顿图
- 具有哈密顿回路的图称作哈密顿图。
- 具有哈密顿通路但不具有哈密顿回路的图称作半哈密顿图。
【注】规定平凡图是哈密顿图。
2. 性质
【注】p(G) 表示 G 的连通分支数。
- 设无向图 G = \lt V,E \gt是哈密顿图，则对于任意的 V_1 \subset V 且 V_1 \ne \varnothing ，均有
\begin{array}{c} p(G-V_1) \leq |V_1| \end{array}
- 设无向图G = \lt V,E \gt 是半哈密顿图，则对于任意的V_1 \subset V 且 V_1 \ne \varnothing ，均有
\begin{array}{c} p(G-V_1) \leq |V_1| + 1 \end{array}
- 设 G 是 n 阶无向简单图，若对于 G中任意不相邻的顶点u,v 均有
\begin{array}{c} d(u) + d(v) \geq n-1 \end{array}
则 G 中存在哈密顿通路。
- 设 G 是n(n \geq 3)阶无向简单图，若对于 G 中任意不相邻的顶点u,v均有
\begin{array}{c} d(u) + d(v) \geq n \end{array}
则 G 中存在哈密顿回路。
- 设 u,v为 n阶无向简单图 G 中两个不相邻的顶点，且d(u) + d(v) \geq n ，则 G 为哈密顿图当且仅当 G \cup (u,v)为哈密顿图。
- n(n \geq 2) 阶竞赛图中都有哈密顿通路。
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录