在计算机科学中，我们不仅需要知道如何证明命题的正确性，还需要掌握如何建模现实世界中的复杂关系。图论（Graph Theory）和模运算（Modular Arithmetic）为我们提供了描述这些关系的语言与工具。本文将继续探索CS70中的核心内容，重点介绍图论的基本概念、特殊图结构以及模运算这一强大的代数工具。
一、图论：关系的抽象表示
图论是研究对象之间关系结构的数学分支。一个图（Graph）由顶点（Vertex） 的集合和边（Edge） 的集合组成。顶点代表对象，边代表对象之间的关系。
1.1 图的基本概念
- 图的定义：一个图 ( G ) 可以表示为 ( G = (V, E) )，其中：
- ( V ) 是顶点的有限集合。
- ( E ) 是边的集合，描述顶点间关系。
- 无向图与有向图：
- 在无向图中，边没有方向，表示为 ( {u, v} )。
- 在有向图中，边有方向，表示为 ( (u, v) )，其中 ( u ) 是起点（tail），( v ) 是终点（head）。
- 度（Degree）：
- 在无向图中，顶点的度是指与其相连的边的数量。
- 在有向图中，分为入度（In-Degree）（以该顶点为终点的边的数目）和出度（Out-Degree）（以该顶点为起点的边的数目）。
- 路径与环：
- 路径是顶点和边的序列，其中每条边连接相邻的顶点。
- 环是起点和终点相同的路径。
- 连通性：
- 连通图：图中任意两个顶点之间都存在路径。
- 非连通图：存在至少两个顶点之间没有路径的图。
- 强连通图：有向图中，任意两个顶点互相可达。
- 弱连通图：有向图的边替换为无向边后可以得到一张连通图。
1.2 特殊类型的图
树（Tree）
树是一种特殊的无向图，满足以下等价定义：
- 连通且无环。
- 连通且有 ( n-1 ) 条边（其中 ( n ) 是顶点数）。
- 任意两个顶点之间有且仅有一条路径。
- 移除任何一条边都会使其不连通。
性质：
- 树是最小连通图。
- 树广泛用于算法设计中，如二叉搜索树、最小生成树等。
完全图（Complete Graph）
完全图是指每对顶点之间都有一条边的图，记为 ( K_n )。它具有以下性质：
- 顶点数：( n )
- 边数：n * ( n-1 ) / 2
- 每个顶点的度：( n-1 )
完全图是“最连通”的图，但其边数随顶点数平方增长，在实际应用中可能不高效。
超立方体（Hypercube）
( n ) 维超立方体是一种具有 ( 2^n ) 个顶点的图，每个顶点用一个 ( n ) 位二进制串标识。两个顶点之间有边当且仅当它们的二进制表示仅有一位不同。
性质：
- 顶点数：( 2^n )
- 边数：( n \cdot 2^{n-1} )
- 具有对称性和高连通性，常用于并行计算和网络设计。
1.3 图的存储方式
图的存储方式直接影响算法的效率。以下是两种常见的存储方法：
| 存储方式 | 适用场景 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 邻接矩阵 | 稠密图 | O(V²) | 查询快，实现简单 | 空间开销大 |
| 邻接表 | 稀疏图 | O(V + E) | 空间效率高，灵活 | 查询效率相对较低 |
邻接矩阵使用二维数组存储边的关系，适合边数较多的稠密图。邻接表则为每个顶点维护一个链表，存储其邻接顶点，适合边数较少的稀疏图。
1.4 基础图算法
深度优先搜索（DFS）与广度优先搜索（BFS）
DFS 和 BFS 是图遍历的两种基本算法，用于访问图中的所有顶点。
- DFS 采用栈（递归或显式栈）实现，优先深入探索分支。
- BFS 采用队列实现，按层次遍历图。
DFS 常用于连通性检测、拓扑排序等场景；BFS 常用于求最短路径（无权图）、社交网络扩散分析等。
最短路径算法
- Dijkstra算法：适用于边权非负的图，求单源最短路径。使用优先队列优化后，时间复杂度为 O(E log V)。
- Floyd-Warshall算法：动态规划求解所有顶点对之间的最短路径，时间复杂度为 O(V³)。
最小生成树（MST）
- Prim算法：类似Dijkstra，每次添加当前与生成树相连的最小权边。时间复杂度 O(E log V)。
- Kruskal算法：按边权升序排序，逐条添加且不形成环。使用并查集优化后，时间复杂度 O(E log E)。
拓扑排序
针对有向无环图（DAG），将顶点线性排序，使得所有边的方向一致。常用 Kahn算法（基于入度）或基于DFS的算法实现，时间复杂度 O(V + E)。
二、模运算：有限世界中的算术
模运算是一种在有限整数范围内进行的算术运算，常用于密码学、哈希算法和错误检测等领域。
2.1 模运算的基本概念
- 定义：对于整数 ( a ) 和正整数 ( m )，( a \mod m ) 表示 ( a ) 除以 ( m ) 的余数，取值范围为 ( {0, 1, \ldots, m-1} )。
- 同余关系：如果 ( a \mod m = b \mod m )，则称 ( a ) 与 ( b ) 模 ( m ) 同余，记作 ( a \equiv b \pmod{m} )。
- 含义：( a ) 和 ( b ) 除以 ( m ) 的余数相同。
- 等价定义：( a \equiv b \pmod{m} ) 当且仅当 ( m ) 整除 ( (a - b) )，即 ( (a - b) ) 是 ( m ) 的倍数。
2.2 模运算的性质
模运算保留了加法和乘法的许多性质：
- ( (a + b) \mod m = (a \mod m + b \mod m) \mod m )
- ( (a \cdot b) \mod m = (a \mod m \cdot b \mod m) \mod m )
注意：除法在模运算中不直接成立，需要通过模逆元来实现。
2.3 模逆元与扩展欧几里得算法
- 模逆元：如果存在整数 ( x ) 使得 ( a \cdot x \equiv 1 \pmod{m} )，则称 ( x ) 是 ( a ) 模 ( m ) 的逆元。
- 存在条件：( a ) 与 ( m ) 互质（即 ( \gcd(a, m) = 1 )）时，逆元存在。
- 扩展欧几里得算法：用于求解 ( \gcd(a, m) ) 并找到整数 ( x, y ) 使得 ( a \cdot x + m \cdot y = \gcd(a, m) )。若 ( \gcd(a, m) = 1 )，则 ( x ) 即为 ( a ) 模 ( m ) 的逆元。
2.4 其他求模逆元的方法
除了扩展欧几里得算法，还有以下方法：
- 费马小定理：当 ( m ) 为质数时，有 ( a^{m-1} \equiv 1 \pmod{m} )，因此 ( a^{-1} \equiv a^{m-2} \pmod{m} )。结合快速幂算法，可高效计算。
- 牛顿迭代法：通过迭代公式逼近逆元，适用于模数为 ( p^l ) 的情况。
不同方法的比较如下表所示：
| 算法 | 时间复杂度 | 适用条件 | 特点 |
|---|---|---|---|
| 扩展欧几里得算法 | O(log(max(a, m))) | ( \gcd(a, m) = 1 ) | 通用，高效 |
| 二进制扩展欧几里得算法 | O(log(max(a, m))) | ( \gcd(a, m) = 1 ) | 常数因子更小，效率略高 |
| 费马小定理+快速幂 | O(log m) | ( m ) 为质数 | 实现简单，但仅限于模数为质数 |
| 牛顿迭代法 | O(l · log p) | 模数为 ( p^l ) | 适用于高次幂模数 |
2.5 中国剩余定理（Chinese Remainder Theorem）
中国剩余定理提供了一种方法，用于求解一组同余方程：
- $x = a_1(mod ~m_1)$
- $x = a_2(mod ~m_2)$
- $x = a_3(mod ~m_3)$
- …
- $x = a_K(mod ~m_K)$
其中 $m_1.m_2.m_3…m_k$ 两两互质。该定理保证存在唯一解模 $M ~= ~m_1.m_2.m_3…m_k$ 。
应用：在密码学（如RSA算法）、数值计算和计算机代数系统中，中国剩余定理用于加速计算和简化问题。
2.6 模运算的应用
- 哈希表：将键映射到数组的索引。
- 密码学：如RSA算法大量使用模运算。
- 校验和：用于检测数据传输中的错误。
- 随机数生成：线性同余生成器使用模运算。
- 时间计算：例如，计算几天后的星期几。
三、图的连通性与模运算的应用
3.1 图的连通性
- 连通图：图中任意两个顶点之间都存在路径。
- 连通分量：图的极大连通子图。
- 最小割：为了使图不连通所需移除的最少边数。
定理：一个具有 ( n ) 个顶点和 ( k ) 条边的图至少有 ( n - k ) 个连通分量。
3.2 模运算在算法中的应用
- 快速幂取模：用于高效计算 ( a^b \mod m )，时间复杂度为 ( O(\log b) )。
- 哈希函数：利用模运算将键映射到有限范围的索引。
- 加密算法：如RSA算法，依赖模运算和模逆元的性质。
四、经典问题：欧拉回路与图的遍历
4.1 欧拉回路（Eulerian Circuit）
欧拉回路是指图中经过每条边恰好一次并回到起点的路径。欧拉在解决柯尼斯堡七桥问题时提出了以下定理：
定理：一个无向图具有欧拉回路当且仅当：
- 图是连通的（忽略孤立顶点）。
- 每个顶点的度都是偶数。
4.2 哈密顿回路（Hamiltonian Circuit）
哈密顿回路是指图中经过每个顶点恰好一次并回到起点的路径。判断一个图是否存在哈密顿回路是NP完全问题，没有已知的高效算法。
总结
本文介绍了图论和模运算的基本概念及其在计算机科学中的应用。图论帮助我们建模对象之间的关系，而模运算则提供了在有限范围内进行计算的工具。两者都是离散数学的核心内容，为算法设计、密码学和网络分析等领域奠定了坚实的基础。
通过理解这些概念，我们不仅能够更好地理解和分析复杂系统，还能设计出更高效、更可靠的算法。这正是CS70课程的精髓所在——通过数学的严谨性，提升计算机科学的实践能力。
