哈密頓圖

定義

通過圖中所有頂點一次且僅一次的通路稱為哈密頓通路。

通過圖中所有頂點一次且僅一次的迴路稱為哈密頓迴路。

具有哈密頓迴路的圖稱為哈密頓圖。

具有哈密頓通路而不具有哈密頓迴路的圖稱為半哈密頓圖。

設 \(G=\langle V, E\rangle\) 是哈密頓圖，則對於 \(V\) 的任意非空真子集 \(V_1\)，均有 \(p(G-V_1) \leq |V_1|\)。其中 \(p(x)\) 為 \(x\) 的連通分支數。

推論：設 \(G=\langle V, E\rangle\) 是半哈密頓圖，則對於 \(V\) 的任意非空真子集 \(V_1\)，均有 \(p(G-V_1) \leq |V_1|+1\)。其中 \(p(x)\) 為 \(x\) 的連通分支數。

完全圖 \(K_{2k+1} (k \geq 1)\) 中含 \(k\) 條邊不重的哈密頓迴路，且這 \(k\) 條邊不重的哈密頓迴路含 \(K_{2k+1}\) 中的所有邊。

完全圖 \(K_{2k} (k \geq 2)\) 中含 \(k-1\) 條邊不重的哈密頓迴路，從 \(K_{2k}\) 中刪除這 \(k-1\) 條邊不重的哈密頓迴路後所得圖含 \(k\) 條互不相鄰的邊。

設 \(G\) 是 \(n(n \geq 2)\) 的無向簡單圖，若對於 \(G\) 中任意不相鄰的頂點 \(v_i, v_j\)，均有 \(d(v_i)+ d(v_j) \geq n - 1\)，則 \(G\) 中存在哈密頓通路。

推論 1：設 \(G\) 是 \(n(n \geq 3)\) 的無向簡單圖，若對於 \(G\) 中任意不相鄰的頂點 \(v_i, v_j\)，均有 \(d(v_i)+ d(v_j) \geq n\)，則 \(G\) 中存在哈密頓迴路，從而 \(G\) 為哈密頓圖。

推論 2：設 \(G\) 是 \(n(n \geq 3)\) 的無向簡單圖，若對於 \(G\) 中任意頂點 \(v_i\)，均有 \(d(v_i) \geq \frac{n}{2}\)，則 \(G\) 中存在哈密頓迴路，從而 \(G\) 為哈密頓圖。

設 \(D\) 為 \(n(n \geq 2)\) 階競賽圖，則 \(D\) 具有哈密頓通路。

若 \(D\) 含 \(n(n \geq 2)\) 階競賽圖作為子圖，則 \(D\) 具有哈密頓通路。

強連通的競賽圖為哈密頓圖。

若 \(D\) 含 \(n(n \geq 2)\) 階強連通的競賽圖作為子圖，則 \(D\) 具有哈密頓迴路。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用