de Pina 支撑向量圈基算法

已选圈张成一个子空间。若S与这个子空间正交，那么子空间内所有向量都通过偶数次S；找到一次奇数的圈，就明确发现了一个不在旧空间中的新方向。

仅有新方向还不能保证成本最小。每轮必须求满足本轮这条奇偶条件的最轻圈。证明会把当前输出接进某个最优基：最优基中必有一条参与表达当前圈、又在S上为奇的圈，它不会比当前输出更轻，可以交换掉。支撑更新让下一轮再次与全部已选方向正交。

双层图给奇偶条件一份很小的记忆。状态的第二位只记“到目前为止经过标记边的次数模2”，不保存整条路径。因此回到同一原顶点却换了层，正好见证一个奇闭走。

同一五点图，先选4再选3 ​

使用Horton页的五点八边图。森林为 $\{10,20,30,50\}$，非树边为40、60、70、80，初始支撑各是这四个单边集。

第二圈虽然只重3，但第一轮它不经过40，因此不满足第一轮约束。这不是“贪心排序出错”：算法根本没有要求全局权序。四圈总权仍为15。

第二轮从状态 $(1,0)$可走

只有60被标记，最后一步翻层；原图投影是 $1,2,4,1$，权3。此时旧的第三支撑{70}也与该圈内积1，所以更新为{60,70}；该圈现在经过两条标记边，内积变0。第三轮的圈{10,50,60}只经过其中60，重新提供内积1的新方向。

为了核查三角形结构，把各轮被使用时的支撑保存下来，得到 $\{40\},\{60\},\{60,70\},\{80\}$。前面已选的圈与后面支撑都正交，各轮本圈内积为1，所以配对矩阵为下三角且对角为1。不能拿被后续覆盖过的某个共享数组当作历史支撑记录。

投影闭走为何还要提取 ​

取三角形 $0,1,2$，三边权均为1，边ID依次为7（0–1）、19（1–2）、31（2–0）。再用权2、ID90的桥连接2与3。标记S={7}。

从原顶点3出发，双层路径可投影为

经过边90、31、7、19、90，总权7。它确实是奇闭走，却重复原顶点2和边90，不能直接输出为简单圈。截出 $2,0,1,2$，得到权3的奇圈。

一般提取使用顶点栈、边栈及顶点在栈中的位置。读到一个已在栈中的顶点，就得到内部无重复顶点的闭段；若该段奇，返回它；若为偶，删去这段并继续。删偶段不改整个闭走的奇偶，过程最后必遇到奇段。简单图中一条边的立即往返长度为2、标记出现两次，必为偶，不会误当成圈。每条栈边至多加入、删除一次，提取对输入走长是线性的，字典操作按期望常数时间计。

非负边权保证返回的奇段不比整个闭走贵。主oracle对所有原顶点求路；只从3求路再把距离7当作最轻奇圈权，会错过权3。完成提取也不是对最短性的替代：必须先证明全顶点最短路径比较没有漏掉最优奇圈。

非零支撑也可能无解 ​

若在上述图中改标记S={90}，双层图中的 $(v,0),(v,1)$对每个v都不连通。任意简单圈不含桥；任意闭走经过桥的次数为偶。因此oracle返回NONE。

更一般地，一个割的边集与每个偶度边集的模2内积都是0：对割一侧的所有顶点度数求和，内部边计算两次，剩下的跨割边数只能为偶。主算法只从非树边的单位向量出发，并保持这些支撑独立；这会排除这种“看上去非零却对所有圈都为零”的支撑。

零权圈必须保留，不能把“最轻”为零当作失败。图不连通时，各分量的圈共享同一个全局边坐标；桥、孤点和树分量不增加r。负边以及自环/平行边不属于本页实现的输入合同。

支撑为何一直存在 ​

令U为只在非树边坐标上可能非零的空间，维数r。生成森林基本圈在非树边上的坐标恰是标准基，因此任意非零 $S\in U$都与某个基本圈内积1。

第i轮开始时，$S_i,\dots ,S_r$是U中与 $C_1,\dots ,C_{i-1}$全正交的子空间的一组基。初始化显然成立。取最轻奇圈 $C_i$后，更新向量都与旧圈正交；对新圈则有

它们仍独立：若更新后的向量有一条零线性组合，代入更新式，便得到旧 $S_i,\dots ,S_r$之间的关系。旧基独立迫使每个 $j>i$的系数为零。新增加的非零线性条件使子空间维数下降一，这些r−i个独立向量恰是新的基。尤其每轮 $S_i$非零且属于U，保证存在奇圈。[2，Lemmas5.4–5.5]

同一条件也证明已选圈独立：$C_i$与 $S_i$内积1，而任何旧圈线性组合与 $S_i$内积0，所以 $C_i$不在旧张成内。r轮后恰好得到一组圈基。

最优基怎样逐轮交换 ​

归纳假设存在一个最优圈基 $\mathcal{B}$包含已输出前缀。把本轮 $C_i$用它唯一展开：

两侧与 $S_i$取内积，左侧为1。因此至少有一个D同时满足 ${\alpha }_D=1$和 $⟨D,S_i⟩=1$。它不是已输出前缀中的圈，因为前缀与 $S_i$正交。

${\alpha }_D=1$保证用 $C_i$替换D仍为基：上式可以反解D，新的r个向量仍张成原空间。D满足本轮奇偶约束，而 $C_i$是该约束下最轻者，故 $w(C_i)\le w(D)$。交换后总权不增，只能仍为最优基，并包含更长的输出前缀。归纳到r轮即证最终最优。[1，Theorem7.1]

这里必须选展开系数为1且内积为1的D。随意从最优基中找一条与 $S_i$非正交的圈，未必能被 $C_i$替换；内积说明存在新方向，展开系数才说明具体哪个旧方向可换。

双层oracle为何恰好求最轻奇圈 ​

任意奇支撑简单圈从它的任一顶点v开始，都提升为 $(v,0)$到 $(v,1)$的路径，权不变。因而所有根最短距离的最小值不大于最优奇圈权。

反向取一个有限的最小距离路径，投影是奇闭走。前述栈过程抽出一个不更贵的奇简单圈。因此最优奇圈权也不大于这个最小距离，两边相等。若所有根都不可达，第一方向说明不存在奇圈。这个证明完整包含了闭走提取，不能以“跨层了”就省略简单性与权界。[2，§5.4，Lemma5.7]

参考执行器以二元权 $(w_e,2^{j(e)})$运行Dijkstra理路Dijkstra 算法Dijkstra's algorithm在非负边权图中逐次确定最短距离的单源最短路算法。，在原权平局时得到确定输出并让所有边二元权严格正。双层中不同路径可能因同一原边使用次数不同而有相同第二分量，算法不依赖双层路径唯一；严格改进更新父边以及固定邻接顺序已经足以恢复一条最短路。第二分量不会改变第一分量的最优值。

实际成本和能核验的内容 ​

完整核验器与Horton共享边表、精确有理权、原ID恢复和公共输入检查。记一次原图或双层图Dijkstra的大数操作次数为 $D=O(n+(m+1)\log (m+2))$；双层只把顶点和边数乘常数。每轮调用n次Dijkstra，至多更新r个支撑。把整段位掩码内积和异或各计一次大数操作，总次数的安全界为

前面的nm来自当前参考森林的分量标签扫描，r=0时仍要支付这项入口工作。每次最短路恢复至多2n−1条边，遍历所有根的恢复和奇段提取已由nD项覆盖。没有保存Horton候选，不表示没有代价：它用更多最短路调用换掉了候选存储。

大数操作次数不是位时间。非负B位有理权在双层简单路径上最多相加2n−1次，配合m位扰动，可继续取 $L=O(1+(n+m)B+m+\log (n+1))$，同时覆盖全基总权的累加。朴素精确运算及约分给出 $O(T_P{L}^3)$安全位上界；支撑内积会遍历真实位数，不能把Python的bit_count当作与m无关的硬件指令。原ID和JSON字节另计。

核心状态为r个m位支撑、r个圈向量和单次最短路工作区。参考返回值还保留每轮所有根的目标距离、获选路径及实际支撑更新前后值，至多 $O(rn+r^2)$个大数或索引记录；这些教学日志的时间、空间和序列化都须另计，不把它们算成免费证书。生成森林、r个独立简单圈和三角配对能证明输出是基；要确认总权最优，仍需复验奇圈最短路oracle或调用已经证明的正确算法，不能只检查秩。

Horton算法理路Horton 最小权圈基算法Horton minimum cycle basis algorithm · Horton algorithm for minimum cycle basis · Horton 最小环基算法从一致最短路树构造多项式大小的圈候选，证明候选完备性，再用二元消元选出总权最小的圈基。先保证候选完备，再按权消元；本页逐次改变支撑，选出的权序可下降。单元终点要求交付两份不同轨迹、相同总权及反例处理，不能用“输出都是四条圈”代替对照。