图的圈空间与键空间

图的圈空间与键空间是代数图论中的核心概念，它们从线性代数的角度揭示了图结构中圈（环）和割（键）的内在对称性与关联性。

1. 基本概念：向量空间与域

   • 为了理解圈空间和键空间，我们首先需要一个基础：向量空间。简单来说，一个向量空间是一个集合，其中的元素（称为向量）可以进行加法和数乘运算，并且这些运算满足特定的规则（如交换律、结合律等）。
   • 这里的“数”来自于一个“域”，最常用的域是二元域 GF(2)。在 GF(2) 中，只有两个元素 {0, 1}，其加法规则为 1+1=0（即模 2 加法），乘法规则与普通算术相同。这种运算特性非常适合描述图论中的“奇偶性”或“出现与否”的概念。

2. 边空间

   • 给定一个图 G（允许有重边和自环），我们固定其边的总数为 m，并为每条边赋予一个固定的方向（这个方向仅用于理论定义，其选择不影响最终结果）。
   • 我们定义图的边空间。这个空间中的每个“向量”实际上是一个边的子集。更形式化地说，一个向量是一个从边集 E 到 GF(2) 的函数。如果一条边在子集中，则其函数值为 1；如果不在，则为 0。
   • 向量的加法对应于对应边集的对称差 (XOR)。例如，子集 A 和 B 的和 A+B 是那些恰好只在 A 或只在 B 中出现的边构成的集合。
   • 边空间是 m 维的。我们可以选择一组基，例如，每条边单独作为一个基向量，那么任何一个边的子集都可以由这组基线性表出。

3. 圈空间

   • 圈：一个圈是一个闭合的路径，其起点和终点相同，且除起点（终点）外其他顶点不重复出现。
   • 欧拉子图：一个更一般的概念是欧拉子图。一个子图是欧拉子图，如果它的每个顶点的度都是偶数。显然，一个圈是欧拉子图，多个边不交的圈的并集也是欧拉子图。
   • 圈空间的定义：图 G 的所有欧拉子图（作为边集的子集）在边空间中构成一个子空间，这个子空间就称为圈空间。
   • 为什么是子空间？ 因为任意两个欧拉子图的对称差（即向量加法）仍然是一个欧拉子图（每个顶点的度的奇偶性在对称差下保持不变）。同时，数乘运算也封闭（在 GF(2) 上，乘以 1 是自身，乘以 0 是空集）。
   • 维数与基：对于一个具有 n 个顶点、m 条边、c 个连通分支的图，其圈空间的维数是 ν = m - n + c。这个数也称为图的圈数或零维贝蒂数。一组自然的基可以通过图的一棵生成树 T 来构造：对于不在 T 中的每一条边 e，将 e 加入 T 会形成一个唯一的圈，称为关于 T 的基本圈。所有这些基本圈构成了圈空间的一组基。

4. 键空间（上圈空间）

   • 键/上圈：一个键（或上圈）是图的一个极小边割。一个边割是这样一个边集，删除它们会使图的连通分支数增加，而“极小”意味着它的任何真子集都不具备这个性质。一个键通常对应着将顶点集划分成两个非空子集 (S, V\S) 后，连接这两个子集的所有边。
   • 键空间的定义：图 G 的所有边割（包括空割）在边空间中构成一个子空间，这个子空间就称为键空间或上圈空间。
   • 为什么是子空间？ 同样，任意两个边割的对称差仍然是一个边割。数乘运算也封闭。
   • 维数与基：键空间的维数是 n - c。一组自然的基也可以通过一棵生成树 T 来构造：删除 T 中的一条边会将其分成两棵子树，连接这两棵子树的所有边构成一个键，称为关于 T 的基本键。所有这些基本键构成了键空间的一组基。

5. 圈空间与键空间的对偶关系

   • 圈空间和键空间是边空间中的正交补子空间。这意味着：
     1. 任何一个圈向量与任何一个键向量的点积（在 GF(2) 下）为 0。因为一个圈与一个边割相交，其交边数总是偶数。
     2. 边空间可以直和分解为圈空间和键空间。任何一个边的子集都可以唯一地表示为一个圈向量和一个键向量之和。
   • 这种对偶关系在图是平面图时表现得尤为优美：一个平面图的圈空间与其几何对偶图的键空间是同构的。