图论基本定理与手算算例

图论的许多基本定理都可以用“数边的端点”或“分块矩阵”这样的初等论证证明，它们也是检查数据和代码是否正确的“守恒律”。下面列出最常用的几条，并配上可以手算的例子。本页只涉及“表示”层面的定理；路径长度、聚集系数等结构指标见网络结构指标与随机图。

定理 1：握手定理

无向图中 $\sum_i k_i = 2M$；有向图中 $\sum_i k_i^{\text{out}}=\sum_i k_i^{\text{in}}=M$。

推论：无向图中奇数度节点的个数必为偶数。

算例：一份 PPI 文件声称有 5 个蛋白，度分别为 3、3、3、3、3。这不可能——度之和为 15，是奇数。这类检查可以快速发现数据整理中的错误（例如去重时只删了一个方向）。

定理 2：Euler 定理

连通的无向（多重）图存在欧拉回路（每条边恰好经过一次并回到起点）当且仅当所有节点的度都是偶数；存在欧拉路径（不要求回到起点）当且仅当奇数度节点的个数为 0 或 2，且若为 2，路径必须以这两个节点为起点和终点。

有向图的对应条件：弱连通（且所有带边节点处于同一分支）、每个节点入度等于出度时存在有向欧拉回路；恰有一个节点出度比入度多 1（起点）、一个节点入度比出度多 1（终点）、其余相等时存在有向欧拉路径。

算例：七桥图的度为 5、3、3、3，四个奇数度节点，不存在欧拉路径。若在两个度为 3 的陆地之间加一座桥，这两块陆地的度变为 4，只剩 2 个奇数度节点，欧拉路径存在，且必须从这两个奇数度节点之一出发。Barabási 的教材提到，1875 年哥尼斯堡确实新建了一座桥，此后欧拉路径就存在了。

定理 3：游走计数

$(A^r)_{ij}$ 等于从 $i$ 到 $j$ 的长度为 $r$ 的游走条数。推论：$\operatorname{tr}(A^2)=2M$，无向简单图的三角形数为 $\operatorname{tr}(A^3)/6$。

算例：4 个节点构成的环 a–b–c–d–a。$A^2$ 的对角元都是 2；$(A^2)_{ac}=2$（a→b→c 与 a→d→c 两条）；$\operatorname{tr}(A^3)=0$，没有三角形。

定理 4：连通分支与分块结构

若图有 $c$ 个连通分支，则适当重排节点顺序后，邻接矩阵和拉普拉斯矩阵都是 $c$ 个对角块构成的分块对角矩阵；拉普拉斯矩阵特征值 0 的重数恰为 $c$。

算例：边为 a–b、c–d 的 4 节点图有 2 个分支，$L$ 的特征值为 $0,0,2,2$。

定理 5：二分图判据

一张图是二分图，当且仅当它不含奇数长度的环。

证明思路：若是二分图，任何环都要在两侧之间来回，回到起点时走过的边数必为偶数。反之，若没有奇环，从任一节点做广度优先搜索，把距离为偶数的节点放一侧、奇数的放另一侧；若有一条边连接了同侧两点，就能构造出一个奇环，矛盾。

算例：三角形 a–b–c 不是二分图（有长度 3 的环）；4 节点的环是二分图（{a, c} 与 {b, d}）。药物–靶点网络若在整理后出现了“药物–药物”的边，用这一判据就能立即发现。

定理 6：树的边数

$N$ 个节点的树恰好有 $N-1$ 条边；更一般地，$N$ 个节点、$c$ 个连通分支的森林有 $N-c$ 条边。任何连通图至少有 $N-1$ 条边。

算例：一张有 100 个节点、连通的网络如果只有 99 条边，它一定是树，没有任何环，删去任意一条边都会使它断开。这也给出了“连通”的最低成本：在构建脑网络时，最小生成树（minimum spanning tree）恰好用 $N-1$ 条边保证所有脑区连通。