跳转至

# 哈密顿图

## 定义

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

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

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

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

## 性质

设 𝐺 =⟨𝑉,𝐸⟩G=⟨V,E⟩ 是哈密顿图，则对于 𝑉 V 的任意非空真子集 𝑉 1 V 1，均有 𝑝(𝐺 −𝑉 1) ≤|𝑉 1|p(G−V 1)≤|V 1|．其中 𝑝(𝑥)p(x) 为 𝑥 x 的连通分支数．

推论：设 𝐺 =⟨𝑉,𝐸⟩G=⟨V,E⟩ 是半哈密顿图，则对于 𝑉 V 的任意非空真子集 𝑉 1 V 1，均有 𝑝(𝐺 −𝑉 1) ≤|𝑉 1| +1 p(G−V 1)≤|V 1|+1．其中 𝑝(𝑥)p(x) 为 𝑥 x 的连通分支数．

完全图 𝐾 2 𝑘+1(𝑘 ≥1)K 2 k+1(k≥1) 中含 𝑘 k 条边不重的哈密顿回路，且这 𝑘 k 条边不重的哈密顿回路含 𝐾 2 𝑘+1 K 2 k+1 中的所有边．

完全图 𝐾 2 𝑘(𝑘 ≥2)K 2 k(k≥2) 中含 𝑘 −1 k−1 条边不重的哈密顿回路，从 𝐾 2 𝑘 K 2 k 中删除这 𝑘 −1 k−1 条边不重的哈密顿回路后所得图含 𝑘 k 条互不相邻的边．

## 充分条件

设 𝐺 G 是 𝑛(𝑛 ≥2)n(n≥2) 的无向简单图，若对于 𝐺 G 中任意不相邻的顶点 𝑣 𝑖,𝑣 𝑗 v i,v j，均有 𝑑(𝑣 𝑖) +𝑑(𝑣 𝑗) ≥𝑛 −1 d(v i)+d(v j)≥n−1，则 𝐺 G 中存在哈密顿通路．

推论 1：设 𝐺 G 是 𝑛(𝑛 ≥3)n(n≥3) 的无向简单图，若对于 𝐺 G 中任意不相邻的顶点 𝑣 𝑖,𝑣 𝑗 v i,v j，均有 𝑑(𝑣 𝑖) +𝑑(𝑣 𝑗) ≥𝑛 d(v i)+d(v j)≥n，则 𝐺 G 中存在哈密顿回路，从而 𝐺 G 为哈密顿图．

推论 2：设 𝐺 G 是 𝑛(𝑛 ≥3)n(n≥3) 的无向简单图，若对于 𝐺 G 中任意顶点 𝑣 𝑖 v i，均有 𝑑(𝑣 𝑖) ≥𝑛 2 d(v i)≥n 2，则 𝐺 G 中存在哈密顿回路，从而 𝐺 G 为哈密顿图．

设 𝐷 D 为 𝑛(𝑛 ≥2)n(n≥2) 阶竞赛图，则 𝐷 D 具有哈密顿通路．

若 𝐷 D 含 𝑛(𝑛 ≥2)n(n≥2) 阶竞赛图作为子图，则 𝐷 D 具有哈密顿通路．

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

若 𝐷 D 含 𝑛(𝑛 ≥2)n(n≥2) 阶强连通的竞赛图作为子图，则 𝐷 D 具有哈密顿回路．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, Tiphereth-A, Enter-tainer
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用