哈密顿图
定义
通过图中所有顶点一次且仅一次的通路称为哈密顿通路．
通过图中所有顶点一次且仅一次的回路称为哈密顿回路．
具有哈密顿回路的图称为哈密顿图．
具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图．
性质
设 𝐺 =⟨𝑉,𝐸⟩G=⟨V,E⟩
是哈密顿图，则对于 𝑉V 的任意非空真子集 𝑉1V1，均有 𝑝(𝐺 −𝑉1) ≤|𝑉1|p(G−V1)≤|V1|．其中 𝑝(𝑥)p(x) 为 𝑥x 的连通分支数．
推论：设 𝐺 =⟨𝑉,𝐸⟩G=⟨V,E⟩ 是半哈密顿图，则对于 𝑉V 的任意非空真子集 𝑉1V1，均有 𝑝(𝐺 −𝑉1) ≤|𝑉1| +1p(G−V1)≤|V1|+1．其中 𝑝(𝑥)p(x) 为 𝑥x 的连通分支数．
完全图 𝐾2𝑘+1(𝑘 ≥1)K2k+1(k≥1) 中含 𝑘k 条边不重的哈密顿回路，且这 𝑘k 条边不重的哈密顿回路含 𝐾2𝑘+1K2k+1 中的所有边．
完全图 𝐾2𝑘(𝑘 ≥2)K2k(k≥2) 中含 𝑘 −1k−1 条边不重的哈密顿回路，从 𝐾2𝑘K2k 中删除这 𝑘 −1k−1 条边不重的哈密顿回路后所得图含 𝑘k 条互不相邻的边．
充分条件
设 𝐺G 是 𝑛(𝑛 ≥2)n(n≥2) 的无向简单图，若对于 𝐺G 中任意不相邻的顶点 𝑣𝑖,𝑣𝑗vi,vj，均有 𝑑(𝑣𝑖) +𝑑(𝑣𝑗) ≥𝑛 −1d(vi)+d(vj)≥n−1，则 𝐺G 中存在哈密顿通路．
推论 1：设 𝐺G 是 𝑛(𝑛 ≥3)n(n≥3) 的无向简单图，若对于 𝐺G 中任意不相邻的顶点 𝑣𝑖,𝑣𝑗vi,vj，均有 𝑑(𝑣𝑖) +𝑑(𝑣𝑗) ≥𝑛d(vi)+d(vj)≥n，则 𝐺G 中存在哈密顿回路，从而 𝐺G 为哈密顿图．
推论 2：设 𝐺G 是 𝑛(𝑛 ≥3)n(n≥3) 的无向简单图，若对于 𝐺G 中任意顶点 𝑣𝑖vi，均有 𝑑(𝑣𝑖) ≥𝑛2d(vi)≥n2，则 𝐺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 协议之条款下提供，附加条款亦可能应用