什么是循环基

date

Jul 9, 2025

slug

xunhuanji

status

Published

🔁 什么是循环基（Cycle Basis）？

在一个连通图中，所有可能的循环（cycles）构成一个向量空间（在 \(\mathbb{F}_2\) 或 \(\mathbb{R}\) 上），这个空间的维度是：

\[ \text{维度} = m - n + 1 \]

其中：

\(m\) 是边的数量，

\(n\) 是顶点的数量。

一个 循环基 就是这个空间的一组基向量，每个基向量对应一个循环。只要我们能找到一组线性无关的循环，且数量等于 \(m - n + 1\)，就构成一个循环基。

🧠 循环基的选择方法

文章中介绍了两种主要的循环基构造方法：

方法 1：Fundamental Cycle Basis（基于生成树）

构造一个生成树（spanning tree）\(T\)，包含所有顶点，无环。

对于每条不在生成树中的边 \(e = (u, v)\)，加入它会形成一个唯一的循环 \(C_e\)。

所有这样的循环 \(C_e\) 构成一个循环基。

✅ 优点：

总是可以构造出来。

保证线性无关。

保证 total unimodularity（整数解）。

⚠️ 缺点：

循环长度可能较长，导致计算慢。

方法 2：Small Cycle Basis（基于 Delaunay 三角形）

从 Delaunay 三角网中提取所有三角形（每个三角形是一个 3 边循环）。

对于冗余边（即非 Delaunay 边），找到连接其两端点的最短路径（在 Delaunay 图中），构成一个新的循环。

将这些循环加入基中。

✅ 优点：

循环长度短，计算更快。

更适合 Delaunay 图结构。

⚠️ 缺点：

不一定 total unimodular（但文章中证明了整数解仍然成立）。

🧪 具体例子：5×5 网格图

我们以一个简单的 5×5 网格图 为例，展示如何构造 Fundamental Cycle Basis。

图结构：

顶点数 \(n = 25\)

边数 \(m = 40\)

循环基维度：\(m - n + 1 = 16\)

步骤：

构造生成树（如图 9 所示）：

从左上角开始，向右向下延伸，形成一个树状结构。

这个树包含 24 条边（\(n - 1\)）。

找出所有非树边：

图中共有 16 条边不在生成树中。

每条非树边加入后，会形成一个唯一的循环。

构造循环基：

每个循环由一个非树边 + 生成树中连接其两端点的路径组成。

这些循环就是 Fundamental Cycle Basis。

示例循环（部分）：

加入边 \((1, 6)\)：形成循环 \((1, 6, 5, 0, 1)\)

加入边 \((2, 7)\)：形成循环 \((2, 7, 6, 1, 2)\)

加入边 \((6, 11)\)：形成循环 \((6, 11, 10, 5, 6)\)

每个循环都是一个 4 边形的“小方格”，如图 10 所示。

🧩 图示（来自原文）

<figure> <img src="https://ipolcore.ipol.im/demo/clientApp/demo.html?id=77777000528" alt="Grid graph and spanning tree" /> <figcaption>图 9：5×5 网格图及其生成树</figcaption> </figure>

<figure> <img src="https://ipolcore.ipol.im/demo/clientApp/demo.html?id=77777000528" alt="Fundamental cycle basis" /> <figcaption>图 10：对应的 16 个 Fundamental Cycles</figcaption> </figure>

✅ 总结

方法	构造方式	优点	缺点
Fundamental Cycle Basis	基于生成树 + 非树边	简单、通用、保证整数解	循环可能较长
Small Cycle Basis	基于 Delaunay 三角形 + 最短路径	循环短、计算快	不一定 total unimodular

如果你希望我画一个具体的图（比如 3×3 网格）并手动标出循环基，我也可以为你画出来。是否需要？

当然可以！我们来详细解释一下循环基（cycle basis）的选择方法，并给出一个具体的例子。

🔁 什么是循环基（Cycle Basis）？

在一个连通图中，所有可能的循环（cycles）构成一个向量空间（在 F2 或 R 上），这个空间的维度是：

维度=

−

其中：

m 是边的数量，

n 是顶点的数量。

一个 循环基 就是这个空间的一组基向量，每个基向量对应一个循环。只要我们能找到一组线性无关的循环，且数量等于 m−n+1，就构成一个循环基。

🧠 循环基的选择方法

文章中介绍了两种主要的循环基构造方法：

方法 1：Fundamental Cycle Basis（基于生成树）

构造一个生成树（spanning tree）T，包含所有顶点，无环。

对于每条不在生成树中的边 e=(uv)，加入它会形成一个唯一的循环 Ce。

所有这样的循环 Ce 构成一个循环基。

✅ 优点：

总是可以构造出来。

保证线性无关。

保证 total unimodularity（整数解）。

⚠️ 缺点：

循环长度可能较长，导致计算慢。

方法 2：Small Cycle Basis（基于 Delaunay 三角形）

从 Delaunay 三角网中提取所有三角形（每个三角形是一个 3 边循环）。

对于冗余边（即非 Delaunay 边），找到连接其两端点的最短路径（在 Delaunay 图中），构成一个新的循环。

将这些循环加入基中。

✅ 优点：

循环长度短，计算更快。

更适合 Delaunay 图结构。

⚠️ 缺点：

不一定 total unimodular（但文章中证明了整数解仍然成立）。

🧪 具体例子：5×5 网格图

我们以一个简单的 5×5 网格图 为例，展示如何构造 Fundamental Cycle Basis。

图结构：

顶点数 n=25

边数 m=40

循环基维度：m−n+1=16

步骤：

构造生成树（如图 9 所示）：

从左上角开始，向右向下延伸，形成一个树状结构。

这个树包含 24 条边（n−1）。

找出所有非树边：

图中共有 16 条边不在生成树中。

每条非树边加入后，会形成一个唯一的循环。

构造循环基：

每个循环由一个非树边 + 生成树中连接其两端点的路径组成。

这些循环就是 Fundamental Cycle Basis。

示例循环（部分）：

加入边 (1,6)：形成循环 (1,6,5,0,1)

加入边 (2,7)：形成循环 (2,7,6,1,2)

加入边 (6,11)：形成循环 (6,11,10,5,6)

每个循环都是一个 4 边形的“小方格”，如图 10 所示。

🧩 图示（来自原文）

<figure> <img src="https://ipolcore.ipol.im/demo/clientApp/demo.html?id=77777000528" alt="Grid graph and spanning tree" /> <figcaption>图 9：5×5 网格图及其生成树</figcaption> </figure>

<figure> <img src="https://ipolcore.ipol.im/demo/clientApp/demo.html?id=77777000528" alt="Fundamental cycle basis" /> <figcaption>图 10：对应的 16 个 Fundamental Cycles</figcaption> </figure>

✅ 总结

TableCopy

方法	构造方式	优点	缺点
Fundamental Cycle Basis	基于生成树 + 非树边	简单、通用、保证整数解	循环可能较长
Small Cycle Basis	基于 Delaunay 三角形 + 最短路径	循环短、计算快	不一定 total unimodular

如果你希望我画一个具体的图（比如 3×3 网格）并手动标出循环基，我也可以为你画出来。是否需要？