图的环空间与割空间 图论中，图的 环空间 和 割空间 是两个重要的向量空间，它们描述了图的结构特性，特别是与圈和割相关的性质。理解它们需要从线性代数和图的基本概念出发。 首先，想象一个无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集，\( E \) 是边集。我们为每条边赋予一个方向（任意指定），这有助于后续的代数处理。 第一步：关联矩阵与边向量空间 定义图 \( G \) 的 关联矩阵 \( B \)，其行对应顶点，列对应边。若边 \( e \) 以顶点 \( v \) 为起点，则 \( B_ {v,e} = 1 \)；若边 \( e \) 以顶点 \( v \) 为终点，则 \( B_ {v,e} = -1 \)；否则为 0。 所有定义在边集 \( E \) 上的实值函数构成一个向量空间 \( \mathbb{R}^E \)，每个函数对应一个边向量 \( \mathbf{x} \in \mathbb{R}^E \)，其分量表示每条边的“权重”或“流量”。 关联矩阵 \( B \) 定义了一个线性映射 \( B: \mathbb{R}^E \to \mathbb{R}^V \)，将边向量映射到顶点向量。 第二步：环空间（Cycle Space） 环空间 \( \mathcal{C}(G) \) 是所有满足“每个顶点处流入等于流出”的边向量组成的子空间。这等价于关联矩阵的零空间：\( \mathcal{C}(G) = \ker(B) \)。 直观上，环空间中的向量对应图的 圈 （闭合路径）的线性组合。例如，一个简单圈上的边赋予相同的权重（如 1），其余边为 0，这样的向量属于环空间。 环空间的维数是 \( m - n + c \)，其中 \( m = |E| \)、\( n = |V| \)、\( c \) 是连通分支数。这个维数等于图的基本圈个数，即生成树的补边数。 第三步：割空间（Cut Space） 割空间 \( \mathcal{B}(G) \) 是关联矩阵行张成的子空间，即 \( \mathcal{B}(G) = \operatorname{im}(B^T) \)。 直观上，割空间中的向量对应图的 割 （将顶点分成两部分的边集）的线性组合。例如，一个顶点集 \( S \subset V \) 对应的割边集，其边向量在 \( S \) 到 \( V\setminus S \) 的方向上赋 1，反向赋 -1（取决于初始定向），其余为 0。 割空间的维数是 \( n - c \)，等于图的基本割集个数，即生成树的树边数。 第四步：正交关系与对偶性 在标准内积下，环空间与割空间是正交补空间：\( \mathbb{R}^E = \mathcal{C}(G) \oplus \mathcal{B}(G) \)。 这意味着任何边向量唯一分解为一个环分量和一个割分量。这一性质在电路理论（基尔霍夫定律）和网络流问题中有核心应用。 第五步：应用示例 在电网络中，边对应导线，边向量表示电流。环空间对应满足基尔霍夫电压定律（沿圈电压和为零）的电流分布；割空间对应满足基尔霍夫电流定律（顶点处电流守恒）的电流分布。 在图算法中，环空间和割空间用于生成树构造、最小割计算，以及校验网络编码的正确性。 理解环空间与割空间，便掌握了图的一种深刻代数视角，将组合结构转化为线性对象进行分析和计算。