跳转至

图论基础

概述

图论是离散数学的重要分支，研究由顶点和边组成的图结构。图论在计算机科学中有广泛应用，从网络设计到社交网络分析，从电路布局到调度问题。

1. 基本概念

1.1 图的定义

图 \(G = (V, E)\) 由顶点集 \(V\) 和边集 \(E\) 组成。

graph LR
    A((a)) --- B((b))
    A --- C((c))
    B --- C
    B --- D((d))
    C --- D

图的分类：

类型 描述 边的表示
无向图 边无方向 \(\{u, v\}\)
有向图 边有方向 \((u, v)\)
加权图 边带权值 \(w(u, v)\)
简单图 无自环、无重边 —
多重图 允许重边 —
完全图 任意两点间有边 \(K_n\)

1.2 基本术语

  • 度 (degree)：顶点 \(v\) 的度 \(\deg(v)\) 是与之关联的边数
  • 入度/出度：有向图中，\(\deg^+(v)\) 和 \(\deg^-(v)\)
  • 邻接：若 \(\{u, v\} \in E\)，则 \(u, v\) 邻接
  • 路径：顶点序列 \(v_0, v_1, \ldots, v_k\)，相邻顶点间有边
  • 环：起点和终点相同的路径
  • 连通：任意两顶点间存在路径

1.3 握手定理

\[ \sum_{v \in V} \deg(v) = 2|E| \]

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

2. 特殊图

2.1 二部图（二分图）

顶点集可划分为两个不相交子集 \(V_1, V_2\)，所有边都连接 \(V_1\) 中的顶点和 \(V_2\) 中的顶点。

graph LR
    subgraph V1
        a((a))
        b((b))
        c((c))
    end
    subgraph V2
        x((x))
        y((y))
    end
    a --- x
    a --- y
    b --- x
    c --- y

判定定理：图 \(G\) 是二部图 \(\iff\) \(G\) 不含奇数长度的环。

完全二部图 \(K_{m,n}\)：\(V_1\) 中每个顶点与 \(V_2\) 中每个顶点都有边。

2.2 度序列

图的度序列是所有顶点度数的非递减排列。

Erdos-Gallai定理：非负整数序列 \(d_1 \geq d_2 \geq \cdots \geq d_n\) 是某简单图的度序列当且仅当：

  1. \(\sum d_i\) 是偶数
  2. 对所有 \(k \in \{1, \ldots, n\}\)：\(\sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{i=k+1}^{n} \min(d_i, k)\)

3. 欧拉路径与哈密顿路径

3.1 欧拉路径与欧拉回路

  • 欧拉路径：经过每条边恰好一次的路径
  • 欧拉回路：起点终点相同的欧拉路径

欧拉定理：

条件 欧拉回路 欧拉路径
无向连通图 所有顶点度为偶数 恰有0或2个奇度顶点
有向连通图 所有顶点入度=出度 至多1个顶点出度-入度=1，至多1个入度-出度=1

柯尼斯堡七桥问题

欧拉在1736年证明柯尼斯堡七桥不可能一次走完所有桥且不重复，因为该图有4个奇度顶点。这是图论的起源。

3.2 哈密顿路径与哈密顿回路

  • 哈密顿路径：经过每个顶点恰好一次的路径
  • 哈密顿回路：起点终点相同的哈密顿路径

与欧拉路径的对比：

  • 欧拉：经过每条边恰好一次（可以多项式时间判定）
  • 哈密顿：经过每个顶点恰好一次（NP完全问题）

Dirac定理：若简单图 \(G\) 有 \(n \geq 3\) 个顶点，且每个顶点的度 \(\geq n/2\)，则 \(G\) 有哈密顿回路。

Ore定理：若简单图 \(G\) 有 \(n \geq 3\) 个顶点，且任意不相邻的顶点 \(u, v\) 满足 \(\deg(u) + \deg(v) \geq n\)，则 \(G\) 有哈密顿回路。

4. 平面图与图着色

4.1 平面图

平面图：可以画在平面上使得边不交叉的图。

欧拉公式：对于连通平面图：

\[ V - E + F = 2 \]

其中 \(V\) 是顶点数，\(E\) 是边数，\(F\) 是面数（包括无界面）。

推论：

  • 若 \(V \geq 3\)，则 \(E \leq 3V - 6\)
  • 若无三角形（最小环长 \(\geq 4\)），则 \(E \leq 2V - 4\)

Kuratowski定理：图 \(G\) 是平面图 \(\iff\) \(G\) 不包含 \(K_5\) 或 \(K_{3,3}\) 的子式。

4.2 图着色

顶点着色：给每个顶点分配颜色，使相邻顶点颜色不同。

色数 \(\chi(G)\)：所需最少颜色数。

图 色数
偶数环 \(C_{2n}\) 2
奇数环 \(C_{2n+1}\) 3
完全图 \(K_n\) \(n\)
二部图 2
树 2
平面图 \(\leq 4\)

四色定理（1976年计算机辅助证明）：任何平面图的色数 \(\leq 4\)。

贪心着色算法：

def greedy_coloring(graph, vertices):
    """贪心图着色"""
    color = {}
    for v in vertices:
        # 收集邻居已使用的颜色
        used = {color[u] for u in graph[v] if u in color}
        # 分配最小可用颜色
        c = 0
        while c in used:
            c += 1
        color[v] = c
    return color

贪心着色的局限

贪心着色的结果依赖于顶点排序，最坏情况可能使用 \(\Delta(G) + 1\) 种颜色（\(\Delta\) 为最大度），不一定达到 \(\chi(G)\)。

5. 树

5.1 树的定义与性质

树：连通无环图。

等价定义（对于 \(n\) 个顶点的图）：

  • 连通且有 \(n - 1\) 条边
  • 无环且有 \(n - 1\) 条边
  • 任意两顶点间恰有一条路径
  • 连通且删除任何一条边后不连通
  • 无环且添加任何一条边后恰产生一个环

5.2 生成树

生成树：包含图所有顶点的树。

Cayley公式：\(K_n\) 有 \(n^{n-2}\) 棵不同的生成树。

\(n\) 生成树数 \(n^{n-2}\)
2 1
3 3
4 16
5 125

6. 网络流

6.1 最大流问题

给定有向图 \(G = (V, E)\)，源点 \(s\)，汇点 \(t\)，每条边 \((u,v)\) 有容量 \(c(u,v)\)，求从 \(s\) 到 \(t\) 的最大流量。

流的约束：

  • 容量约束：\(0 \leq f(u, v) \leq c(u, v)\)
  • 流量守恒：对 \(v \neq s, t\)，\(\sum_u f(u, v) = \sum_w f(v, w)\)

6.2 最大流最小割定理

\[ \max \text{flow} = \min \text{cut} \]

割：将 \(V\) 划分为 \(S\) 和 \(T = V \setminus S\)（\(s \in S, t \in T\)），割的容量为：

\[ c(S, T) = \sum_{u \in S, v \in T} c(u, v) \]

6.3 Ford-Fulkerson方法

while 存在从s到t的增广路径P:
    计算P上的瓶颈容量 Δ
    沿P增广流量 Δ
    更新残余图

时间复杂度：\(O(|E| \cdot |f^*|)\)，其中 \(f^*\) 是最大流值。

Edmonds-Karp算法：使用BFS寻找最短增广路径，复杂度 \(O(VE^2)\)。

7. Ramsey理论简介

7.1 基本思想

Ramsey理论研究"完全无序是不可能的"——足够大的结构中必然包含特定的有序子结构。

7.2 Ramsey数

\(R(s, t)\) 是最小的正整数 \(n\)，使得 \(K_n\) 的边无论怎样2-着色（红/蓝），必然包含红色 \(K_s\) 或蓝色 \(K_t\)。

已知值：

\(R(s,t)\) \(t=3\) \(t=4\) \(t=5\)
\(s=3\) 6 9 14
\(s=4\) 9 18 25
\(s=5\) 14 25 43--48

Ramsey数的计算困难

\(R(5,5)\) 的精确值至今未知，只知道 \(43 \leq R(5,5) \leq 48\)。Erdos曾说："如果外星人威胁要摧毁地球除非我们计算出 \(R(5,5)\)，我们应该集中所有计算机来完成这个任务。但如果他们要求 \(R(6,6)\)，我们应该尝试摧毁外星人。"

上界：\(R(s, t) \leq \binom{s+t-2}{s-1}\)

8. 图的表示与存储

8.1 邻接矩阵

\(n \times n\) 矩阵 \(A\)，\(A[i][j] = 1\) 表示边 \((i, j)\) 存在。

  • 空间：\(O(n^2)\)
  • 查询边：\(O(1)\)
  • 遍历邻居：\(O(n)\)

8.2 邻接表

每个顶点维护一个邻居列表。

  • 空间：\(O(n + m)\)
  • 查询边：\(O(\deg(v))\)
  • 遍历邻居：\(O(\deg(v))\)

选择建议：稠密图用邻接矩阵，稀疏图（\(m \ll n^2\)）用邻接表。

参考资料

  • Diestel, Graph Theory（研究生经典教材）
  • West, Introduction to Graph Theory
  • Bondy & Murty, Graph Theory

相关章节：

评论 #