跳到主要内容

图论

图论（Graph Theory）是研究图的结构和性质的数学分支。图由顶点和边组成，用于模拟对象之间的二元关系。从社交网络到地图导航，从网页链接到电路设计，图论的应用无处不在。它是离散数学中最直观、最实用的分支之一。

图的基本概念​

图的定义​

图（Graph）GG 由两个部分组成：

  • 顶点集（Vertex Set）：V(G)V(G)，图中的节点集合
  • 边集（Edge Set）：E(G)E(G)，连接顶点的边的集合

图记作 G=(V,E)G = (V, E)。

边是顶点的无序对（无向图）或有序对（有向图）。如果边 ee 连接顶点 uu 和 vv，记作 e={u,v}e = \{u, v\}（无向）或 e=(u,v)e = (u, v)（有向）。

无向图与有向图​

无向图：边没有方向，$\{u, v\}$ 和 $\{v, u\}$ 表示同一条边。适合表示对称关系，如"朋友关系"、"道路连接"。

有向图：边有方向，(u,v)(u, v) 表示从 uu 指向 vv 的边。适合表示非对称关系，如"关注关系"、"单向道路"。

# 用邻接表表示图
# 无向图
undirected_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B'],
    'D': ['B']
}

# 有向图
directed_graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['B'],
    'D': []
}

图的基本术语​

相邻（Adjacent）：如果两个顶点之间有边连接，则它们相邻。

关联（Incident）：边与其端点相关联。边 $e = \{u, v\}$ 与顶点 uu 和 vv 都关联。

度数（Degree）：顶点的度数是与该顶点关联的边的数量。在有向图中：

  • 出度（Out-degree）：从该顶点出发的边数
  • 入度（In-degree）：指向该顶点的边数

握手定理：在无向图中，所有顶点的度数之和等于边数的两倍：

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|

推论：在任何图中，度数为奇数的顶点个数必为偶数。

def calculate_degrees(graph):
    """计算无向图各顶点的度数"""
    degrees = {}
    for vertex in graph:
        degrees[vertex] = len(graph[vertex])
    return degrees

# 验证握手定理
graph = {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}
degrees = calculate_degrees(graph)
total_degree = sum(degrees.values())
edges = sum(len(neighbors) for neighbors in graph.values()) // 2
print(f"度数之和: {total_degree}, 边数×2: {edges * 2}")  # 相等

特殊类型的图​

简单图：没有自环（顶点到自身的边）和重边（两顶点间多条边）的图。

完全图 KnK_n：nn 个顶点的简单图，任意两个顶点之间都有边。边数为 (n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2}。

二分图（Bipartite Graph）：顶点可以分成两个不相交的集合，所有边都连接两个集合中的顶点，同一集合内的顶点之间没有边。

完全二分图 Km,nK_{m,n}：二分图的两个部分分别有 mm 和 nn 个顶点，两个部分之间的所有顶点对都有边连接。

正则图：所有顶点的度数都相同的图。kk-正则图中每个顶点的度数都是 kk。

图的表示方法​

邻接矩阵：用 n×nn \times n 矩阵表示图，其中 nn 是顶点数。如果顶点 ii 和 jj 之间有边，则 Aij=1A_{ij} = 1，否则 Aij=0A_{ij} = 0。

对于无向图，邻接矩阵是对称的。

# 邻接矩阵表示
def adjacency_matrix(graph):
    vertices = list(graph.keys())
    n = len(vertices)
    matrix = [[0] * n for _ in range(n)]
    vertex_to_index = {v: i for i, v in enumerate(vertices)}
    
    for vertex, neighbors in graph.items():
        for neighbor in neighbors:
            i = vertex_to_index[vertex]
            j = vertex_to_index[neighbor]
            matrix[i][j] = 1
    
    return matrix

邻接表：对每个顶点，列出与其相邻的顶点。适合稀疏图（边数远小于 n2n^2）。

# 邻接表表示（Python 字典）
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1]
}

比较：

表示方法空间复杂度检查边是否存在遍历邻居
邻接矩阵O(n2)O(n^2)O(1)O(1)O(n)O(n)
邻接表O(n+m)O(n + m)O(deg⁡(v))O(\deg(v))O(deg⁡(v))O(\deg(v))

路径与连通性​

路径​

路径（Path）：顶点和边交替组成的序列 v0,e1,v1,e2,…,ek,vkv_0, e_1, v_1, e_2, \ldots, e_k, v_k，其中每条边 eie_i 连接 vi−1v_{i-1} 和 viv_i。

简单路径：顶点不重复的路径。

路径长度：路径中边的数量。

距离：两顶点之间最短路径的长度。

环​

环（Cycle）：起点和终点相同的路径。

简单环：除起点和终点外，顶点不重复的环。

无环图：不包含任何环的图。无向无环图就是森林（连通时是树）。

连通性​

连通（Connected）：在无向图中，如果顶点 uu 和 vv 之间存在路径，则称 uu 和 vv 连通。

连通图：任意两个顶点都连通的无向图。

连通分量：无向图中的极大连通子图。一个图可能有多个连通分量。

强连通（有向图）：有向图中，如果从 uu 可以到达 vv，从 vv 也可以到达 uu，则称 uu 和 vv 强连通。

强连通分量：有向图中的极大强连通子图。

def is_connected(graph, start, end, visited=None):
    """检查无向图中两点是否连通（DFS）"""
    if visited is None:
        visited = set()
    
    if start == end:
        return True
    
    visited.add(start)
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            if is_connected(graph, neighbor, end, visited):
                return True
    
    return False

def count_components(graph):
    """计算连通分量数"""
    visited = set()
    count = 0
    
    for vertex in graph:
        if vertex not in visited:
            # BFS 或 DFS 遍历整个连通分量
            stack = [vertex]
            while stack:
                v = stack.pop()
                if v not in visited:
                    visited.add(v)
                    stack.extend(graph.get(v, []))
            count += 1
    
    return count

图的遍历​

深度优先搜索（DFS）​

深度优先搜索沿着一条路径尽可能深入，直到无法继续，然后回溯。

算法思想：

  1. 从起点开始，标记为已访问
  2. 对每个未访问的邻居，递归执行 DFS
  3. 当所有邻居都访问过，回溯
def dfs(graph, start, visited=None):
    """深度优先搜索"""
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')  # 处理当前顶点
    
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    
    return visited

# 示例
graph = {0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1]}
dfs(graph, 0)  # 输出: 0 1 3 4 2（取决于字典顺序）

应用：

  • 检测连通性
  • 拓扑排序
  • 检测环
  • 寻找路径

广度优先搜索（BFS）​

广度优先搜索逐层遍历，先访问距离起点近的顶点。

算法思想：

  1. 从起点开始，加入队列
  2. 取出队列首元素，访问其所有未访问的邻居，加入队列
  3. 重复直到队列为空
from collections import deque

def bfs(graph, start):
    """广度优先搜索"""
    visited = set([start])
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')  # 处理当前顶点
        
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

# 示例
graph = {0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1]}
bfs(graph, 0)  # 输出: 0 1 2 3 4

应用：

  • 最短路径（无权图）
  • 层次遍历
  • 连通分量

DFS 与 BFS 的比较​

特性DFSBFS
数据结构栈（递归）队列
空间复杂度O(h)O(h)，hh 是深度O(w)O(w)，ww 是宽度
适用场景路径搜索、拓扑排序最短路径、层次遍历
完备性可能陷入无限深度保证找到最短路径

最短路径​

无权图的最短路径​

在无权图中，BFS 可以找到从起点到其他所有顶点的最短路径。

from collections import deque

def shortest_path_unweighted(graph, start, end):
    """无权图的最短路径（BFS）"""
    visited = {start}
    queue = deque([(start, [start])])
    
    while queue:
        vertex, path = queue.popleft()
        
        if vertex == end:
            return path
        
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # 没有路径

Dijkstra 算法​

Dijkstra 算法用于求解带非负权重的图中单源最短路径问题。

算法思想：

  1. 初始化：起点距离为 0，其他顶点距离为无穷大
  2. 选择未访问顶点中距离最小的顶点
  3. 更新其邻居的距离
  4. 重复直到所有顶点访问完
import heapq

def dijkstra(graph, start):
    """Dijkstra 算法
    graph: {顶点: {邻居: 权重}}
    返回: {顶点: 最短距离}
    """
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]  # 优先队列：(距离, 顶点)
    visited = set()
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current in visited:
            continue
        visited.add(current)
        
        for neighbor, weight in graph[current].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# 示例
weighted_graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 8},
    'D': {'B': 5, 'C': 8}
}
print(dijkstra(weighted_graph, 'A'))  # {'A': 0, 'B': 3, 'C': 2, 'D': 8}

时间复杂度：使用优先队列时为 O((V+E)log⁡V)O((V + E) \log V)

Floyd-Warshall 算法​

Floyd-Warshall 算法用于求解所有顶点对之间的最短路径。

算法思想：动态规划，逐步允许通过更多顶点作为中转点。

def floyd_warshall(graph):
    """Floyd-Warshall 算法
    graph: 邻接矩阵，graph[i][j] = 权重，inf 表示无边
    返回: 距离矩阵
    """
    n = len(graph)
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    
    # 对角线设为 0
    for i in range(n):
        dist[i][i] = 0
    
    # 动态规划
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

时间复杂度：O(V3)O(V^3)

最小生成树​

生成树​

生成树（Spanning Tree）：连通图的生成树是包含图中所有顶点的无环连通子图。生成树的边数为 n−1n-1，其中 nn 是顶点数。

最小生成树（MST）：带权连通图中，边权之和最小的生成树。

Prim 算法​

Prim 算法从任意顶点开始，逐步扩展生成树。

算法思想：

  1. 从一个顶点开始
  2. 每次选择连接树内和树外的最小权边
  3. 将新顶点加入树
  4. 重复直到包含所有顶点
import heapq

def prim(graph):
    """Prim 算法
    graph: {顶点: {邻居: 权重}}
    返回: 最小生成树的边列表和总权重
    """
    start = next(iter(graph))  # 任选一个起点
    visited = set([start])
    edges = []  # (权重, 顶点1, 顶点2)
    mst = []
    total_weight = 0
    
    # 初始化：将与起点相连的边加入优先队列
    for neighbor, weight in graph[start].items():
        heapq.heappush(edges, (weight, start, neighbor))
    
    while edges and len(visited) < len(graph):
        weight, u, v = heapq.heappop(edges)
        
        if v in visited:
            continue
        
        visited.add(v)
        mst.append((u, v, weight))
        total_weight += weight
        
        for neighbor, w in graph[v].items():
            if neighbor not in visited:
                heapq.heappush(edges, (w, v, neighbor))
    
    return mst, total_weight

时间复杂度：使用优先队列时为 O(Elog⁡V)O(E \log V)

Kruskal 算法​

Kruskal 算法按边权从小到大选择边，避免形成环。

算法思想：

  1. 将所有边按权重排序
  2. 依次考虑每条边，如果加入后不形成环，则加入
  3. 直到选了 n−1n-1 条边

判断是否形成环需要用并查集（Union-Find）数据结构。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(n, edges):
    """Kruskal 算法
    n: 顶点数
    edges: [(权重, 顶点1, 顶点2), ...]
    返回: 最小生成树的边列表和总权重
    """
    edges.sort()  # 按权重排序
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    
    for weight, u, v in edges:
        if uf.union(u, v):  # 如果不形成环
            mst.append((u, v, weight))
            total_weight += weight
            if len(mst) == n - 1:
                break
    
    return mst, total_weight

时间复杂度：O(Elog⁡E)O(E \log E)，主要由排序决定

拓扑排序​

拓扑排序是处理有向无环图（DAG）的重要算法，它将图中的顶点排成一个线性序列，使得对于图中的每条有向边 (u,v)(u, v)，顶点 uu 在序列中位于顶点 vv 之前。

拓扑排序的定义​

设 G=(V,E)G = (V, E) 是一个有向无环图。GG 的拓扑排序是顶点的一个线性排列 v1,v2,…,vnv_1, v_2, \ldots, v_n，使得如果存在边 (vi,vj)∈E(v_i, v_j) \in E，则 i<ji < j。

存在条件：一个有向图存在拓扑排序，当且仅当它是有向无环图（DAG）。如果图中存在环，则无法进行拓扑排序。

非唯一性：一个 DAG 可能有多个不同的拓扑排序。例如，如果三个顶点 a,b,ca, b, c 中，只有 aa 到 bb 和 aa 到 cc 的边，则 [a,b,c][a, b, c] 和 [a,c,b][a, c, b] 都是合法的拓扑排序。

应用场景​

拓扑排序在实际中有广泛的应用：

任务调度：项目管理中，某些任务必须在其他任务完成后才能开始。例如，编译程序时，必须先编译依赖库，再编译主程序。

课程安排：大学课程有先修要求，必须按拓扑顺序安排课程。

依赖解析：软件包管理器需要按照依赖关系安装软件包。

编译器优化：确定表达式求值的顺序，数据流分析。

# 任务依赖关系的例子
tasks = {
    '编译': ['链接'],
    '链接': ['打包'],
    '打包': ['部署'],
    '测试': ['部署']
}
# 拓扑排序: ['编译', '链接', '测试', '打包', '部署']

Kahn 算法（基于入度）​

Kahn 算法通过不断移除入度为 0 的顶点来实现拓扑排序。

算法步骤：

  1. 计算所有顶点的入度
  2. 将所有入度为 0 的顶点加入队列
  3. 从队列中取出一个顶点，加入结果序列
  4. 删除该顶点的所有出边，更新相邻顶点的入度
  5. 如果某顶点入度变为 0，加入队列
  6. 重复步骤 3-5，直到队列为空
  7. 如果结果序列中的顶点数等于图中顶点数，则成功；否则图中存在环
from collections import deque

def kahn_topological_sort(graph):
    """
    Kahn 算法实现拓扑排序
    graph: 邻接表表示的有向图 {顶点: [邻居列表]}
    返回: 拓扑排序结果，如果存在环则返回 None
    """
    # 计算所有顶点的入度
    in_degree = {v: 0 for v in graph}
    for vertex in graph:
        for neighbor in graph[vertex]:
            if neighbor not in in_degree:
                in_degree[neighbor] = 0
            in_degree[neighbor] += 1
    
    # 将入度为 0 的顶点加入队列
    queue = deque([v for v in in_degree if in_degree[v] == 0])
    result = []
    
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        
        # 更新相邻顶点的入度
        for neighbor in graph.get(vertex, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 检查是否存在环
    if len(result) != len(in_degree):
        return None  # 图中存在环
    
    return result

# 示例
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}
print(kahn_topological_sort(graph))
# 可能的输出: ['A', 'B', 'C', 'D', 'E', 'F'] 或 ['B', 'A', 'D', 'C', 'E', 'F'] 等

时间复杂度：O(V+E)O(V + E)，每个顶点和边都只处理一次。

基于深度优先搜索的算法​

DFS 也可以实现拓扑排序。关键思想是：顶点在其所有后继顶点都被访问后才加入结果序列。

算法步骤：

  1. 对每个未访问的顶点执行 DFS
  2. 在 DFS 完成一个顶点的所有邻居后，将该顶点加入结果序列
  3. 最后反转结果序列
def dfs_topological_sort(graph):
    """
    基于 DFS 的拓扑排序
    """
    visited = set()
    result = []
    
    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                dfs(neighbor)
        result.append(vertex)  # 在完成所有后继节点后添加
    
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
    
    return result[::-1]  # 反转结果

# 检测环的版本
def dfs_topological_sort_with_cycle_detection(graph):
    """
    带环检测的拓扑排序
    返回: (拓扑排序结果, 是否存在环)
    """
    # 0: 未访问, 1: 正在访问, 2: 已完成
    state = {v: 0 for v in graph}
    for vertex in graph:
        for neighbor in graph[vertex]:
            if neighbor not in state:
                state[neighbor] = 0
    
    result = []
    has_cycle = False
    
    def dfs(vertex):
        nonlocal has_cycle
        if state[vertex] == 1:  # 遇到正在访问的节点，存在环
            has_cycle = True
            return
        if state[vertex] == 2:  # 已完成访问
            return
        
        state[vertex] = 1  # 标记为正在访问
        for neighbor in graph.get(vertex, []):
            dfs(neighbor)
        state[vertex] = 2  # 标记为已完成
        result.append(vertex)
    
    for vertex in list(state.keys()):
        if state[vertex] == 0:
            dfs(vertex)
    
    if has_cycle:
        return None, True
    return result[::-1], False

拓扑排序与偏序关系​

拓扑排序与偏序关系有深刻的数学联系。给定一个 DAG，可以定义顶点之间的偏序关系：u≤vu \leq v 当且仅当从 uu 可以到达 vv。拓扑排序就是这个偏序关系的一个线性扩展（Linear Extension），即将偏序扩展为全序。

这意味着：

  • 偏序关系中的可比元素在拓扑排序中保持顺序
  • 偏序关系中的不可比元素在拓扑排序中可以有任意顺序

唯一性条件​

一个 DAG 的拓扑排序是唯一的，当且仅当拓扑排序中的每对相邻顶点之间都有边。这等价于 DAG 存在哈密顿路径。

二分图匹配​

二分图匹配是图论中的重要问题，在资源分配、任务调度、婚姻问题等领域有广泛应用。

二分图的判定​

定理：一个无向图是二分图，当且仅当它不包含奇环。

判定方法：使用 BFS 或 DFS 进行双色着色。如果能用两种颜色给顶点着色，使得相邻顶点颜色不同，则是二分图。

def is_bipartite(graph):
    """
    判断图是否为二分图
    返回: (是否为二分图, 着色方案)
    """
    color = {}
    
    def bfs(start):
        queue = deque([start])
        color[start] = 0
        
        while queue:
            vertex = queue.popleft()
            for neighbor in graph.get(vertex, []):
                if neighbor not in color:
                    color[neighbor] = 1 - color[vertex]
                    queue.append(neighbor)
                elif color[neighbor] == color[vertex]:
                    return False
        return True
    
    for vertex in graph:
        if vertex not in color:
            if not bfs(vertex):
                return False, None
    
    # 分成两部分
    left = {v for v, c in color.items() if c == 0}
    right = {v for v, c in color.items() if c == 1}
    return True, (left, right)

匹配的定义​

匹配（Matching）：图中边的子集，其中任意两条边都没有公共顶点。

最大匹配（Maximum Matching）：边数最多的匹配。

完美匹配（Perfect Matching）：每个顶点都被匹配覆盖的匹配。只有顶点数为偶数的图才可能有完美匹配。

最大匹配与完美匹配的关系：完美匹配一定是最大匹配，但最大匹配不一定是完美匹配。

增广路径​

增广路径（Augmenting Path）：在当前匹配中，连接两个未匹配顶点的路径，且路径上的边交替为"匹配边"和"非匹配边"。

增广路径的关键性质：将增广路径上的匹配边和非匹配边互换，匹配数增加 1。

Berge 定理：一个匹配是最大匹配，当且仅当图中不存在增广路径。

这一定理给出了寻找最大匹配的基本思路：不断寻找增广路径并进行增广，直到不存在增广路径为止。

匈牙利算法​

匈牙利算法用于求解二分图的最大匹配，时间复杂度为 O(V⋅E)O(V \cdot E)。

算法思想：

  1. 初始化匹配为空
  2. 对于左部每个未匹配的顶点 uu，尝试寻找增广路径
  3. 使用 DFS 或 BFS 寻找从 uu 出发的增广路径
  4. 如果找到增广路径，进行增广（翻转路径上的匹配状态）
  5. 重复直到无法增广
def hungarian_algorithm(graph, left_vertices, right_vertices):
    """
    匈牙利算法求二分图最大匹配
    
    graph: 邻接表 {左顶点: [右顶点列表]}
    left_vertices: 左部顶点集合
    right_vertices: 右部顶点集合
    
    返回: 匹配字典 {左顶点: 匹配的右顶点}
    """
    match = {}  # 右顶点 -> 左顶点
    
    def dfs(u, visited):
        """尝试为左顶点 u 找匹配"""
        for v in graph.get(u, []):
            if v in visited:
                continue
            visited.add(v)
            
            # 如果 v 未匹配，或者 v 的当前匹配可以换到其他顶点
            if v not in match or dfs(match[v], visited):
                match[v] = u
                return True
        return False
    
    result = {}
    for u in left_vertices:
        if dfs(u, set()):
            # 更新结果
            for v, matched_u in match.items():
                result[matched_u] = v
    
    return result

# 示例：工作分配问题
# 左部是工人，右部是工作，边表示工人能胜任的工作
workers = {'A', 'B', 'C'}
jobs = {'1', '2', '3', '4'}

work_ability = {
    'A': ['1', '2'],
    'B': ['2', '3'],
    'C': ['3', '4']
}

matching = hungarian_algorithm(work_ability, workers, jobs)
print(f"工作分配: {matching}")
# 可能的输出: {'A': '1', 'B': '2', 'C': '3'} 或其他有效分配

算法执行过程：

假设图中有左顶点 {1,2,3}\{1, 2, 3\}，右顶点 {a,b,c}\{a, b, c\}，边为 (1,a),(1,b),(2,a),(2,c),(3,b)(1, a), (1, b), (2, a), (2, c), (3, b)。

  1. 为顶点 1 寻找匹配：找到边 (1,a)(1, a)，匹配变为 {a:1}\{a: 1\}
  2. 为顶点 2 寻找匹配：尝试 (2,a)(2, a)，但 aa 已匹配给 1；尝试 (2,c)(2, c)，成功，匹配变为 {a:1,c:2}\{a: 1, c: 2\}
  3. 为顶点 3 寻找匹配：尝试 (3,b)(3, b)，成功，匹配变为 {a:1,b:3,c:2}\{a: 1, b: 3, c: 2\}
  4. 所有左顶点都已匹配，算法结束

Hall 婚姻定理​

Hall 婚姻定理给出了二分图存在完美匹配的充要条件。

定理：设 G=(X∪Y,E)G = (X \cup Y, E) 是二分图。XX 中的每个顶点都能被匹配，当且仅当对于 XX 的任意子集 SS，SS 的邻居集合 N(S)N(S) 满足 ∣N(S)∣≥∣S∣|N(S)| \geq |S|。

这个条件称为 Hall 条件。它告诉我们：要为 XX 中的每个元素找到匹配，任意 kk 个元素的邻居必须至少有 kk 个。

应用示例：判断是否能给每个学生分配一个他们感兴趣的项目。

  • 设 SS 是任意一组学生
  • N(S)N(S) 是这些学生感兴趣的所有项目集合
  • 只有当 ∣N(S)∣≥∣S∣|N(S)| \geq |S| 对所有 SS 成立时，才能确保每个学生都分配到项目

匹配的应用​

任务分配：将任务分配给工人，每个工人最多完成一个任务，每个任务最多由一个工人完成。目标是最大化完成的任务数。

婚姻问题：将男士和女士配对，使得尽可能多的人找到伴侣。

课程安排：将课程分配到时间段，避免冲突。

网络流：二分图最大匹配可以转化为网络最大流问题求解。

图着色​

图着色问题​

顶点着色：给图的每个顶点分配一种颜色，使得相邻顶点颜色不同。

着色数 χ(G)\chi(G)：使图 GG 能够正常着色所需的最少颜色数。

特殊图的着色数​

  • 完全图 KnK_n：χ(Kn)=n\chi(K_n) = n（每个顶点都需要不同颜色）
  • 二分图：χ(G)=2\chi(G) = 2（两部分各用一种颜色）
  • 树：χ(T)=2\chi(T) = 2（树是二分图）
  • 环图 CnC_n：当 nn 为偶数时为 2，当 nn 为奇数时为 3

贪心着色算法​

def greedy_coloring(graph):
    """贪心着色算法"""
    colors = {}
    vertices = list(graph.keys())
    
    for vertex in vertices:
        # 找出邻居已使用的颜色
        used_colors = set()
        for neighbor in graph[vertex]:
            if neighbor in colors:
                used_colors.add(colors[neighbor])
        
        # 分配最小的可用颜色
        color = 0
        while color in used_colors:
            color += 1
        colors[vertex] = color
    
    return colors

贪心算法不一定得到最优解，但提供了上界：χ(G)≤Δ(G)+1\chi(G) \leq \Delta(G) + 1，其中 Δ(G)\Delta(G) 是图的最大度数。

着色的应用​

调度问题：将任务着色，同一颜色的任务可以同时进行（因为它们不冲突）。

寄存器分配：编译器优化中，将变量分配到有限的寄存器中，冲突的变量不能共享寄存器。

地图着色：相邻区域着不同颜色，著名的四色定理说明平面图最多需要四种颜色。

欧拉路径与哈密顿路径​

欧拉路径和哈密顿路径是图论中两个经典问题，它们表面相似但本质截然不同。欧拉路径要求经过每条边恰好一次，而哈密顿路径要求经过每个顶点恰好一次。前者有高效的多项式时间算法，后者则是 NP 完全问题。

欧拉路径​

欧拉路径（Eulerian Path） 是经过图中每条边恰好一次的路径。如果路径的起点和终点相同，则称为欧拉回路（Eulerian Circuit）。

欧拉路径问题源于著名的哥尼斯堡七桥问题：能否从某一点出发，经过每座桥恰好一次，最后回到出发点？1736 年，欧拉证明了这是不可能的，并由此开创了图论这一数学分支。

欧拉定理​

欧拉定理给出了判断图是否存在欧拉路径或欧拉回路的充要条件。

欧拉回路的条件：连通图存在欧拉回路，当且仅当所有顶点的度数都是偶数。

欧拉路径的条件：连通图存在欧拉路径，当且仅当奇数度顶点的个数是 0 或 2。

  • 如果有 0 个奇数度顶点，所有欧拉路径都是欧拉回路
  • 如果有 2 个奇数度顶点，欧拉路径必须从一个奇数度顶点出发，到另一个奇数度顶点结束

直观理解：除了起点和终点外，路径经过任何顶点时，必须"进一次出一次"，所以度数必须是偶数。起点多一次"出"，终点多一次"进"，所以只有起点和终点可以度数为奇数。

def has_eulerian_path(graph):
    """判断图是否存在欧拉路径或欧拉回路"""
    # 检查连通性（假设图是连通的）
    odd_degree_count = sum(1 for v in graph if len(graph[v]) % 2 == 1)
    
    if odd_degree_count == 0:
        return "Eulerian circuit&quot;  # 存在欧拉回路
    elif odd_degree_count == 2:
        return "Eulerian path&quot;     # 存在欧拉路径（非回路）
    else:
        return None                # 不存在欧拉路径

# 示例
graph1 = {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}  # 三角形
print(has_eulerian_path(graph1))  # None（每个顶点度数都是2，但没有欧拉路径因为不可能不重复走边）

graph2 = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}  # 线 A-B-C
print(has_eulerian_path(graph2))  # Eulerian path

Hierholzer 算法​

Hierholzer 算法用于在欧拉图中寻找欧拉回路，时间复杂度为 O(E)O(E)。

算法思想：

  1. 从任意顶点出发，沿着边走，直到回到起点，形成一个回路
  2. 如果回路没有覆盖所有边，找一个在回路中但还有未访问边的顶点，从它出发再走一个回路
  3. 将新回路插入到原回路中
  4. 重复直到所有边都被访问
def hierholzer(graph):
    """Hierholzer 算法寻找欧拉回路"""
    # 复制图（因为会修改）
    graph = {v: list(neighbors) for v, neighbors in graph.items()}
    
    # 找起点（如果有奇数度顶点，从奇数度顶点开始）
    start = next(iter(graph))
    for v in graph:
        if len(graph[v]) % 2 == 1:
            start = v
            break
    
    stack = [start]
    path = []
    
    while stack:
        v = stack[-1]
        if graph[v]:
            # 还有未访问的边
            u = graph[v].pop()
            graph[u].remove(v)  # 无向图，双向删除
            stack.append(u)
        else:
            # 当前顶点没有未访问的边，加入路径
            path.append(stack.pop())
    
    return path[::-1]  # 反转得到正确顺序

# 示例：一个欧拉图（每个顶点度数都是偶数）
euler_graph = {
    0: [1, 2, 3, 4],
    1: [0, 2],
    2: [0, 1, 3, 4],
    3: [0, 2],
    4: [0, 2]
}
print(hierholzer(euler_graph))
# 可能输出: [0, 1, 2, 3, 0, 4, 2, 0]

哈密顿路径​

哈密顿路径（Hamiltonian Path） 是经过图中每个顶点恰好一次的路径。如果路径的起点和终点相同，则称为哈密顿回路（Hamiltonian Cycle）。

哈密顿路径问题由威廉·哈密顿于 1857 年提出，与他发明的"周游世界"游戏有关——在正十二面体上找出一条经过每个顶点恰好一次的回路。

欧拉路径与哈密顿路径的对比​

特性欧拉路径哈密顿路径
定义经过每条边恰好一次经过每个顶点恰好一次
判定条件简单的度数条件没有简单的充要条件
算法复杂度多项式时间 O(E)O(E)NP 完全问题
实际应用DNA 测序、电路设计旅行商问题

哈密顿路径的判定​

与欧拉路径不同，判断一个图是否存在哈密顿路径是 NP 完全问题，没有已知的多项式时间算法。但有一些充分条件可以帮助判断。

Dirac 定理：设 GG 是 n≥3n \geq 3 个顶点的简单图。如果每个顶点的度数至少为 n/2n/2，则 GG 存在哈密顿回路。

Ore 定理：设 GG 是 n≥3n \geq 3 个顶点的简单图。如果对于任意两个不相邻的顶点 uu 和 vv，都有 deg⁡(u)+deg⁡(v)≥n\deg(u) + \deg(v) \geq n，则 GG 存在哈密顿回路。

注意：这些只是充分条件，不满足条件的图也可能存在哈密顿回路。

def has_hamiltonian_path_bruteforce(graph):
    """暴力搜索判断是否存在哈密顿路径（仅适用于小图）"""
    from itertools import permutations
    
    vertices = list(graph.keys())
    n = len(vertices)
    
    for perm in permutations(vertices):
        # 检查这个排列是否构成路径
        valid = True
        for i in range(n - 1):
            if perm[i + 1] not in graph[perm[i]]:
                valid = False
                break
        if valid:
            return list(perm)
    
    return None

# 示例
graph = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2]}
print(has_hamiltonian_path_bruteforce(graph))
# 可能输出: [0, 1, 2, 3] 或其他有效路径

与旅行商问题的关系​

旅行商问题（Traveling Salesman Problem，TSP）是组合优化中的经典问题：给定一组城市和城市之间的距离，找出访问每个城市恰好一次并回到起点的最短路线。

TSP 可以看作是在完全图上寻找最小权重的哈密顿回路。由于哈密顿回路问题是 NP 完全的，TSP 也是 NP 难问题。

近似算法：对于度量 TSP（满足三角不等式），存在多项式时间近似算法：

  • Christofides 算法：近似比为 1.5
  • 最近邻算法：近似比不保证，但实际效果尚可

应用​

欧拉路径的应用：

  • DNA 测序：将 DNA 片段组装成完整序列
  • 电路设计：CMOS 电路中晶体管的最优排序
  • 邮递员问题：寻找经过所有街道的最短路线

哈密顿路径的应用：

  • 旅行商问题：物流配送路线规划
  • 排程问题：任务排序
  • 电路测试：测试序列生成

平面图​

平面图的定义​

平面图（Planar Graph） 是可以在平面上画出，且边只在顶点处相交的图。如果图已经画在平面上且边不相交，则称为平面嵌入或平面表示。

判断一个图是否为平面图是一个重要问题。Kuratowski 定理给出了充要条件：一个图是平面图，当且仅当它不包含 K5K_5（5 个顶点的完全图）或 K3,3K_{3,3}（完全二分图）的细分。

欧拉公式​

对于连通平面图，欧拉公式建立了顶点数 VV、边数 EE 和面数 FF 之间的关系：

V−E+F=2V - E + F = 2

其中面（Face） 是平面嵌入中被边包围的区域，包括无界的外部区域。

推论：对于简单连通平面图，边数满足 E≤3V−6E \leq 3V - 6（当 V≥3V \geq 3 时）。

证明思路：每个面至少由 3 条边围成，每条边最多属于 2 个面。因此 3F≤2E3F \leq 2E。代入欧拉公式：V−E+F=2V - E + F = 2，得 V−E+2E/3≥2V - E + 2E/3 \geq 2，化简得 E≤3V−6E \leq 3V - 6。

这个不等式可以用来证明某些图不是平面图。例如 K5K_5 有 V=5V = 5，E=10E = 10，但 3×5−6=9<103 \times 5 - 6 = 9 < 10，所以 K5K_5 不是平面图。

def check_planar_simple(v, e):
    """简单检查：如果边数超过 3V-6，一定不是平面图"""
    if v < 3:
        return True  # 顶点少于3的图总是平面图
    return e <= 3 * v - 6

print(check_planar_simple(5, 10))  # False，K5 不是平面图
print(check_planar_simple(4, 6))   # True，K4 是平面图

四色定理​

四色定理：任何平面图的顶点都可以用不超过四种颜色着色，使得相邻顶点颜色不同。

这个定理看似简单，但证明极为复杂。它于 1976 年由 Appel 和 Haken 用计算机辅助证明，是第一个主要依赖计算机的数学定理证明。

与地图着色的关系：将地图上每个区域看作顶点，相邻区域之间连边，得到一个平面图。四色定理说明任何地图都可以用四种颜色着色，使得相邻区域颜色不同。

小结​

本章介绍了图论的基础知识：

  1. 基本概念：图的定义、顶点、边、度数、邻接矩阵与邻接表
  2. 路径与连通性：路径、环、连通图、连通分量
  3. 图的遍历：深度优先搜索（DFS）、广度优先搜索（BFS）
  4. 最短路径：无权图 BFS、Dijkstra 算法、Floyd-Warshall 算法
  5. 最小生成树：Prim 算法、Kruskal 算法
  6. 图着色：着色数、贪心着色
  7. 欧拉路径与哈密顿路径：定义、判定条件、算法与应用
  8. 平面图：定义、欧拉公式、四色定理

图论是算法设计的核心领域之一。社交网络分析、路线规划、网络流、编译器设计等众多应用都建立在图论的基础上。

练习​

  1. 证明握手定理：无向图中所有顶点的度数之和等于边数的两倍。

  2. 给定图的邻接矩阵，如何判断图是否连通？

  3. 实现一个算法，检测无向图中是否存在环。

  4. 在下面的带权图中，用 Dijkstra 算法求从 A 到所有其他顶点的最短路径：

    • A-B: 4, A-C: 2
    • B-C: 1, B-D: 5
    • C-D: 8, C-E: 10
    • D-E: 2

  5. 证明树是二分图。

  6. 判断下图是否存在欧拉路径或欧拉回路：顶点 {A, B, C, D}，边为 AB, AC, BC, BD, CD。

  7. 用欧拉定理证明：哥尼斯堡七桥问题无解。（提示：将每块陆地看作顶点，每座桥看作边）

  8. 证明 K5K_5（5 个顶点的完全图）不是平面图。

  9. 对于一个简单连通平面图，证明：如果每个面都至少由 4 条边围成，则 E≤2V−4E \leq 2V - 4。

  10. 什么是哈密顿路径？为什么判断一个图是否存在哈密顿路径是 NP 完全问题，而判断欧拉路径可以在多项式时间内解决？