Horton 最小权圈基算法

形式陈述

要优化的是一组圈

给定有限简单无向图 $G=(V,E)$ ， $n=|V|,m=|E|$ ，每条边有非负权 $w_e$ 。保留孤立点，连通分量数记为 $c$ ；空图取 $c=0$ 。本页的圈采用简单圈：至少三条边，除首尾外不重复顶点。图可以不连通，不允许自环或平行边。

把一个边集写成 $m$ 位向量，在 $\mathbb F_2=\{0,1\}$ 上相加：相同边出现两次便抵消。因此向量加法就是边集的对称差。所有顶点度数为偶数的边集构成空间 $Z(G)$ ；两个偶度边集异或后仍偶度。简单圈在其中，但两个分离的圈的并也在其中，不能把空间里的每个非零向量都叫简单圈。

圈基是 $Z(G)$ 的一组由简单圈组成的线性无关生成族。目标为

\min_{\mathcal B}\sum_{C\in\mathcal B}w(C), \qquad w(C)=\sum_{e\in C}w_e.

一条边若出现在三个基圈中，目标便把它计算三次。它不是“所有已选圈的边集并”的权重，也不是最小生成树。

取任意生成森林 $T$ 。每条非树边 $e$ 与 $T$ 中连接其两端的唯一路径组成基本圈 $F_e$ 。每个 $F_e$ 恰含一条非树边，就是 $e$ ，所以这些向量独立。任一偶度边集 $X$ 与所有满足 $e\in X\setminus T$ 的 $F_e$ 异或后，只剩森林中的偶度边集；非空森林有叶子，故这个剩余只能为空。因此基本圈张成 $Z(G)$ ，且

r=\dim Z(G)=m-n+c.

这也证明输入总有圈基。森林的 $r=0$ ，应输出空列表和总权零；不能强求找到第一条圈。

先统一所有最短路的平局

构造要复用许多最短路。本页固定一种对所有根都一致的平局规则，使下文的等距圈证明可以直接使用。先按真实边ID排序，给边内部秩 $j=0,\ldots,m-1$ ，用二元权

\widehat w(e_j)=(w_{e_j},2^j)

逐分量相加、按字典序比较。第一分量先比较原权，仅在相等时比较第二分量。每条边的二元权严格为正，即使原权为零。简单路径没有重复边，第二分量就是其边集的二进制编码；固定端点的不同简单路径有不同边集，因而有不同二元权。

于是每对可达点都有唯一的二元最短路。它的反向仍是反向查询的唯一最短路；任一子路径也必须唯一最短，否则替换它会改进整条路。这种跨查询、跨子路径的一致性才是下面完备性证明使用的条件。原ID可以是7、19、90， $2^j$ 中的 $j$ 是排序后的内部秩，绝不是原ID本身。[1，印刷p.7]

候选与消元

对每个根 $s$ ，求其所在分量的唯一最短路树 $T_s$ ，把根到 $v$ 的树路径边向量记为 $P_s(v)$ 。对该分量中的每条边 $e=uv$ ，形成

C_{s,e}=P_s(u)\oplus P_s(v)\oplus\{e\}.

树边给出零向量，丢弃。非树边给出一条简单圈：两条根路径的共同前缀抵消，剩下的是树中 $u$ 到 $v$ 的唯一路径加 $e$ 。根不一定在这个圈上；不能把有重复前缀的闭走直接当作输出圈。

候选去重后至多 $nm$ 条。按 $\widehat w(C)=(w(C),\sum_{e\in C}2^{j(e)})$ 非减排序，依次尝试加入。以行化简的二元版本检验独立性：在当前向量的最高非零位已有主元行时，异或该行以消去它；剩余为零就拒绝，否则在新的最高位存入剩余行，并接受原圈。保留原圈用于输出，剩余行只是消元工具，未必还是一条简单圈。

算法输出 $r$ 个圈、其原边ID及原权总和。下文证明候选中包含一个全局最优基；随后拟阵贪心定理用于这些圈向量的线性拟阵，保证排序消元选出候选中的最小权基。这里的拟阵元素是一整个圈向量，不是图拟阵中的单条边。

直觉

任意森林能提供一套圈基，却可能让许多基本圈都绕同一条长树路。Horton 不把希望寄托在一棵“刚好选对”的森林上，而是从每个顶点建立最短路树。一个真正便宜的基圈，不能容许两个圈上点之间有更便宜的外部捷径；否则捷径会把它换成更便宜的材料。

没有捷径的圈可以从圈上一点沿两个方向用最短路覆盖，只剩一条边把两侧接起来。因此它会出现在某棵最短路树的候选里。候选远少于全部简单圈，可能仍有冗余；消元负责判定一条新圈究竟增加了一个自由方向，还是已能由前面的圈异或出来。

五点轮图上，森林基本圈总权20，Horton候选消元得到总权15的四个圈 — 原边身份与最小圈基

例子与边界

五点图：20怎样降到15

顶点为 $0,1,2,3,4$ ，前四点形成外框，4是中心。边表按ID排序：

边ID	两端	原权
10	0–1	1
20	1–2	1
30	2–3	1
40	3–0	1
50	0–4	2
60	1–4	1
70	2–4	1
80	3–4	2

$n=5,m=8,c=1$ ，所以需要四个独立圈。按ID扫描并跳过成圈边，得到森林 $T=\{10,20,30,50\}$ ，弦为40、60、70、80。它们的基本圈依次为

\begin{aligned} &\{10,20,30,40\}:4,\\ &\{10,50,60\}:4,\\ &\{10,20,50,70\}:5,\\ &\{10,20,30,50,80\}:7. \end{aligned}

总权为20。它们确实是基，问题出在成本。

全部Horton候选去重后有8条；按权扫描首先接受下表四条。位串按边ID10到80从左到右列出，左端是内部第0位，不采用通常整数印刷的高位在左约定。

接受顺序	原边ID	八个坐标	原权
1	20,60,70	01000110	3
2	10,20,30,40	11110000	4
3	10,50,60	10001100	4
4	30,70,80	00100011	4

四行主元位分别为6、3、5、7，互不相同，故独立；总权为15。下一候选 $\{10,20,50,70\}$ 权5，等于第一、第三个已选圈的异或，消成零。完整图共有13条简单圈，但算法只需这8条候选；这一次的13项枚举用于算例核对，不属于Horton算法。

三个容易误换的对象

圈基允许不同圈共享边。要求基圈边不相交会改变问题，也可能根本无解。反过来，四条不同的圈未必独立，例如三个向量中若 $C_3=C_1\oplus C_2$ ，即使三条都很短，第三条仍未增加维数。

输出圈的原顶点与边身份必须保留。转成整数位掩码只是内部表示，若把边ID直接当稠密下标，换成7、19、90后便会错。零权也不是删边许可：一个全零三角形仍有一维圈空间，应该输出权零的圈，不能只输出空集。

负权不在本页合同内。无向边一旦为负，在允许重复边的最短路子程序中就能来回降低成本。即使有限多个简单圈仍可比较，也不能继续使用这里的Dijkstra与非负分解证明。多重图则要另处理一边自环圈和二边平行圈；本执行器直接拒绝，不先合并它们。

推论与应用

为什么最优基圈没有外部捷径

在有限多个简单圈基中，取总二元权最小的一组 $\mathcal B$ 。其原权总和也最小，因为字典序首先最小化原权。设 $C\in\mathcal B$ ， $u,v$ 是圈上两点，圈的两条 $u$ – $v$ 弧为 $A,B$ 。若唯一最短路 $P$ 不在 $C$ 内，它不同于这两条弧，因此

\widehat w(P)<\widehat w(A),\qquad \widehat w(P)<\widehat w(B).

两个偶度边集 $X=P\oplus A$ 、 $Y=P\oplus B$ 满足 $X\oplus Y=C$ 。它们的权分别至多为 $\widehat w(P)+\widehat w(A)$ 、 $\widehat w(P)+\widehat w(B)$ ，均严格小于 $\widehat w(C)$ ；取消重复边只会减少非负二元权。

每个非空偶度边集可拆成边不交的简单圈：沿尚未使用的边走，偶度保证不能停在起点以外；截出一次最短闭段作为简单圈，删去其边后剩余仍偶度，重复即可结束。因而 $X,Y$ 都由权严格小于 $C$ 的简单圈异或而成。

令 $W$ 为其余基圈的张成。若这些更短的简单圈全部属于 $W$ ，则 $X,Y,C$ 都属于 $W$ ，与基的独立性矛盾。所以至少一条更短的简单圈不在 $W$ ，可替换 $C$ 得到更轻的基，又与最优性矛盾。因此 $C$ 包含任意两个圈上点之间的唯一最短路。[1，Theorem2]

为什么一定进入候选

固定 $C$ 上的根 $s$ 。到每个圈上顶点的唯一最短路都在 $C$ 内，并在 $T_s$ 中。它们的并是包含 $C$ 全部顶点、只使用 $C$ 边的树，因此恰为 $C$ 删去一条边 $e$ 。于是 $T_s$ 对 $e$ 产生的基本圈正是 $C$ 。对所有根、所有边生成候选，就不会漏掉这组最优基中的任何一条圈。[1，Theorem3]

这说明一致平局为何重要：若分别为不同端点挑不兼容的最短路，前缀不再组成同一棵树，上段“它们的并是一棵树”就没有依据。本页二元扰动给出了可执行的充分方法，而不是假设原权天然没有平局。

执行与成本

完整核验器只使用Python标准库，接受整数或Fraction权重。原图和双层图都调用Dijkstra；严格改进才改父边，二元权严格为正保证父链无圈。输入正规化、森林、候选、消元、原ID恢复均在文件内。

为了把位长算清，先数有理加法/比较、整数加法/比较、整段掩码异或/移位/哈希这些大数操作的次数，并不把它直接叫作位运行时间。一次原图Dijkstra使用惰性二叉堆，次数为

D=O\bigl(n+(m+1)\log(m+2)\bigr).

记去重候选数为 $q\le nm$ 。当前参考实现的一个安全总次数界为

T_H=O\bigl(1+n+nm+m\log(m+1)+nD+qm +q\log(q+1)+qr\bigr).

森林以扫描分量标签实现，需 $O(nm)$ ；每个根构造路径掩码后扫描m边；排序前逐位提取候选边并求权，最多qm次；消元每项至多r次掩码异或。r=0时程序直接跳过全部最短路，仍支付输入和森林成本。可用更高效森林或位向量实现改进，但不能把其他版本的更快界直接贴到本代码上。

若每个有理权分子、分母至多B位，简单路径或圈的权和可用 $O(nB+\log(n+1))$ 位表示；二元扰动另占 $O(m)$ 位。取 $L=O(1+(n+m)B+m+\log(n+1))$ ，这还覆盖全基总权累加时最多m个不同分母及至多r次边重复。上式每个掩码操作至多处理L位；有理运算连同约分可用朴素 $O(L^3)$ 安全上界，因而 $O(T_HL^3)$ 给出一个不追求紧致的位成本界。真实ID的比较及输出按ID编码长度另计。数值 $2^j$ 只需j+1位，不能因它数值很大就称指数时间，也不能因只写了一个Python整数就称常数空间。

保存候选和消元行需要 $O((q+r)m)$ 位向量空间，队列/邻接结构另占 $O(n+m)$ 条记录，权值另计。最终r个简单圈的显式边列表至多rn项；若像本单元JSON那样还展开全部候选及消元记录，必须另付报告生成与输出字节数。

de Pina算法用支撑向量逐轮提出奇偶约束，再求最轻满足约束的圈，避免保存整套Horton候选。两者都求同一最优值，但Horton的输出顺序按圈权非减，de Pina没有这个顺序要求。单元终点并排核对两份运行记录。

参考资料

[1] J. D. Horton，A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph，University of New Brunswick，TR84-026，1984，§§2–4，印刷pp.2–7（PDF5–10页），Theorems1–3、候选/消元及p.7平局说明。正式期刊版发表于SIAM Journal on Computing16(2)，1987，pp.358–366；这里定位所读技术报告，不混用两版页码。
[2] Telikepalli Kavitha等，Cycle Bases in Graphs: Characterization, Algorithms, Complexity, and Applications，Computer Science Review3(4)，2009，所链作者稿§5.1及§§5.7.1–5.7.2：候选法与一致最短路。本文采用明确的二元边扰动并支付位成本，不声称实现其中的快速矩阵算法。

形式陈述 ​

要优化的是一组圈 ​

先统一所有最短路的平局 ​

候选与消元 ​

五点图：20怎样降到15 ​

三个容易误换的对象 ​

为什么最优基圈没有外部捷径 ​

为什么一定进入候选 ​

执行与成本 ​

反向链接