图论：通路、回路与图的连通性 + 图的矩阵表示
北京大学《离散数学》课程第四部分”图论”讲义（7.2-7.3 节），olefile 提取自老式 .ppt。
通路与回路
- 通路：图 G=<V,E> 中顶点与边的交替序列 Γ=v0e1v1e2…elvl，其中 vi-1、vi 是 ei 的端点（有向图要求 vi-1 是始点、vi 是终点）。v0 为起点，vl 为终点，l 为长度。v0=vl 时称为回路。
- 初级通路（路径）/初级回路（圈）：通路中所有顶点各异（回路除 v0=vl）。
- 简单通路/简单回路：所有边各异；否则为复杂通路/回路。
- 表示方法：顶点边交替序列、边序列、简单图中顶点序列、非简单图混合表示法。
- 环是长度为 1 的圈；两条平行边构成长度为 2 的圈。无向简单图圈长 ≥3，有向简单图圈长 ≥2。
- 圈的计数：定义意义下无向图长度 l 的圈算 2l 个（起点×方向），有向图算 l 个（起点）；同构意义下长度相同的圈算 1 个。
关键定理（长度上界）
- n 阶图中 vi 到 vj 若存在通路，则存在长度 ≤ n−1 的通路（且存在长度 ≤ n−1 的初级通路）。
- n 阶图中 vi 到自身若存在回路，则存在长度 ≤ n 的回路（初级回路同理）。
无向图连通性
- u 与 v 连通 ⟺ 之间有通路；连通关系是 V 上的等价关系。
- 连通分支：V/R 各等价类的导出子图，个数记 p(G)；G 连通 ⟺ p(G)=1。
- 短程线与距离 d(u,v)：最短通路长度，不连通规定为 ∞。性质：非负、对称、三角不等式。
点割集与边割集
- 点割集 V′⊂V：p(G−V′) > p(G) 且 V′ 的任何真子集不增加分支数。单点集 {v} 为点割集时 v 称割点。
- 边割集 E′⊆E：p(G−E′) > p(G) 且最小性同上。单边形成的边割集称割边/桥。
- 说明：完全图 Kn 无点割集；n 阶零图点割边割皆无；G 连通时删边割集后 p=2，删点割集后 p≥2。
有向图连通性
- u 可达 v：u 到 v 有通路；可达具有自反性和传递性。
- 三级分类：弱连通（基图为无向连通图）⊂ 单向连通（任意两点至少一向可达）⊂ 强连通（任意两点相互可达）。强⇒单⇒弱。
- 强连通判别法：D 强连通 ⟺ 存在经过每个顶点至少一次的回路。
- 单向连通判别法：D 单向连通 ⟺ 存在经过每个顶点至少一次的通路。
- 有向距离 d⟨u,v⟩ 无对称性。
图的矩阵表示
- 无向图关联矩阵 M(G)=(mij)n×m，mij = vi 与 ej 的关联次数（0/1/2）。
- 有向图关联矩阵（无环）：mij 取 1（vi 是 ej 始点）/ −1（终点）/ 0；平行边对应列相同。
- 邻接矩阵 A(D)：aij 为 vi 邻接到 vj 的边数。
- 通路计数定理：Al 元素 (i,j) = vi 到 vj 长度为 l 的通路数；(i,i) = vi 长度 l 回路数；全元素和 = 长度 l 通路总数；主对角线和 = 长度 l 回路总数。推论：Bl=A+A²+…+Al 统计长度 ≤l 的通路/回路数。
- 可达矩阵 P(D)：pij=1 ⟺ vi 可达 vj。主对角线全 1；D 强连通 ⟺ P 全为 1。
- 例题结论：4 阶有向图长度 1/2/3/4 的通路数分别 1/2/3/4 阶幂之和统计得到（示例数据：通路合计 50、回路合计 8）。
可行动点 / 关联
- 邻接矩阵幂求通路计数是算法题常用技巧，可与 算法分析与设计-第10讲-计算复杂性理论-屈婉玲 中矩阵乘法复杂度关联。
- 强连通分量、割点/桥是图算法（Tarjan）的离散数学基础。
- 同课程系列：算法设计与分析课程-第1讲-引言-屈婉玲（同为屈婉玲北大课程资料）。