5. 哈密顿图的充要条件及相关定理

# 1. 哈密顿图的概述

## 1.1 哈密顿图的定义
在图论中，哈密顿图是指包含了图中每个顶点的一个哈密顿回路或哈密顿路径的图。哈密顿回路是指经过图中每个顶点恰好一次的闭合路径，而哈密顿路径则是指经过图中每个顶点恰好一次的路径。

## 1.2 哈密顿回路与哈密顿路径
哈密顿回路是一条从某个顶点出发，沿着边遍历每个顶点并最终回到起始顶点的路径。而哈密顿路径则是一条从某个顶点出发，沿着边遍历每个顶点但不要求回到起始顶点的路径。

## 1.3 哈密顿图在实际应用中的意义
哈密顿图在实际应用中具有广泛的意义和应用价值。例如，在网络规划中，哈密顿图可以用来解决如何对网络中的节点进行布线的问题。在旅行商问题中，哈密顿图可以用来寻找最优的路径，从而使得旅行商可以依次经过每个城市并最终返回出发点。此外，哈密顿图还可以应用于电路设计、项目调度等领域。

通过对哈密顿图的充分了解，可以更好地应用于实际问题的求解，提高问题的解决效率和质量。在接下来的章节中，我们将进一步探讨哈密顿图的充要条件及相关定理，以及其在各个领域的应用和算法实现。

# 2. 哈密顿图的充要条件**

**2.1 定义哈密顿图的必要条件**

在研究哈密顿图的充要条件之前，我们首先回顾一下哈密顿图的定义。哈密顿图是指一个图G=(V,E)，其中V是图的顶点集合，E是图的边集合。如果存在一个哈密顿回路，即一条经过图G的每个顶点恰好一次的回路，则称该图为哈密顿图。

要验证给定的图是否为哈密顿图，有一些必要条件可以利用。首先，一个图如果是哈密顿图，那么它至少要有n个顶点（n≥3）才能成为哈密顿图。这是因为一个哈密顿回路必须经过图中的每个顶点一次，所以至少需要有n个顶点。

**2.2 定理一：Dirac定理**

Dirac定理是一条判定图是否为哈密顿图的充分条件。该定理由Dirac在1952年提出，表明在图中，如果任意一个顶点的度数大于等于n/2（其中n是图中顶点的个数），则该图一定是哈密顿图。

我们可以用以下代码来验证一个给定的图是否满足Dirac定理：

def is_hamiltonian(graph):
    n = len(graph)
    for i in range(n):
        if graph[i].count(1) < n / 2:
            return False
    return True

# 测试例子
G = [
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0]
]

print(is_hamiltonian(G)) # 输出 True

代码解析：我们通过一个循环遍历图中每个顶点的度数，如果存在一个度数小于n/2的顶点，则返回False，否则返回True。

运行结果：我们将给定的图G传入函数is_hamiltonian中进行判定，最终得到输出True，表示该图满足Dirac定理，是一个哈密顿图。

**2.3 定义哈密顿图的充分条件**

除了Dirac定理外，还有其他一些充分条件可以帮助判定一个图是否为哈密顿图。下面介绍两个常见的充分条件。

**2.4 定理二：Ore定理**

Ore定理是由Ore在1960年提出的，它表明在图中，如果任意两个不相邻的顶点的度数之和大于等于n，则该图一定是哈密顿图。

我们可以使用以下代码来验证一个给定的图是否满足Ore定理：

public class HamiltonianGraph {

    public static boolean isHamiltonian(int[][] graph) {
        int n = graph.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 0 && i != j && graph[i].length + graph[j].length < n) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] G = {
            {0, 1, 0, 1},
            {1, 0, 1, 0},
            {0, 1, 0, 1},
            {1, 0, 1, 0}
        };
        System.out.println(isHamiltonian(G)); // 输出 true
    }
}

代码解析：我们通过一个双重循环遍历图中的每对顶点，如果两个顶点不相邻且它们的度数之和小于n，则返回False，否则返回True。

运行结果：我们将给定的图G传入isHamiltonian方法进行判断，最终输出结果为true，表示该图满足Ore定理，是一个哈密顿图。

**2.5 定理三：Pósa定理**

Pósa定理是由Pósa在1976年提出的，它表明在图中，如果对于任意一个非连续的顶点对u, v以及它们之间的任意一个顶点w，满足degree(u) + degree(v) ≥ n，则该图一定是哈密顿图。

我们可以使用以下代码验证一个给定的图是否满足Pósa定理：

package main

import "fmt"

func isHamiltonian(graph [][]int) bool {
    n := len(graph)
    for u := 0; u < n; u++ {
        for v := 0; v < n; v++ {
            if graph[u][v] == 0 && u != v {
                count := 0
                for w := 0; w < n; w++ {
                    if graph[u][w] != 0 && graph[v][w] != 0 {
                        count++
                    }
                }
                if count < n {
                    return false
                }
            }
        }
    }
    return true
}

func main() {
    graph := [][]int{
        {0, 1, 0, 1},
        {1, 0, 1, 0},
        {0, 1, 0, 1},
        {1, 0, 1, 0},
    }
    fmt.Println(isHamiltonian(graph)) // 输出 true
}

代码解析：我们通过两重循环遍历图中的每对顶点，然后再通过一重循环遍历它们之间的所有顶点，统计