Question

Cycle

一条路径的起点和终点相同，就是一只“环”。

有向图的环，可以特地称作“有向环”；无向图的环，可以特地称作“无向环”。环上每个点都恰好连著两条边。

无向环以另一种角度来看，就是两条路径，两条路径的起点相同、终点也相同。

习惯规定一个环至少三个点。

Loop

一个点连向自己的边，称作“自环”，有时候可以归类为环。

Distance

eccentricity：偏心距，从一个点出发的最长距离。
diameter：直径，一张图（每个点）最大的偏心距。一张图最长的距离。
radius：半径，一张图（每个点）最小的偏心距。
circumference：外周，一张图最长的最短环。
girth：内周，一张图最短的最短环。

Negative Weight Cycle

Negative Weight Cycle（Negative Cycle）

权重为负值的环称作“负环”。Label Correcting Algortihm、Bellman-Ford Algorithm 可以找出其中一只负环。

Minimum Weight Cycle

Minimum Weight Cycle（Shortest Cycle）（Girth）

“最小环”是一张图上权重最小的环，可能有许多只。

当图上无负环时，得以多项式时间找出其中一个最小环，此时最小环是简单环。当图上有负环时，无法快速找出最小环，为 NP-complete 问题。

求最小环如同求最短路径；求最大环如同求最长路径。

演算法

穷举图上每一个点：
　甲、以该点为起点，以边的连接关係进行 backtracking。
　乙、途中若形成环，则随时记录最小环。
　丙、可以 bound。

时间複杂度是 O(V!)，不过实际效率尚可接受。

演算法

穷举所有图上的边 ij：
　甲、把边 ij 暂时拿掉，权重改成无限大。
　乙、求出 i 点到 j 点的最短路径。
　丙、放回边 ij，形成一只环，即是强制经过边 ij 的最小环。
　丁、过程中权重最小者即是最小环。

时间複杂度等同于求 O(E) 次两点之间最短路径的时间。

演算法

藉由 Floyd-Warshall Algorithm 的过程，顺手穷举所有可能的最小环。有使用限制。

时间複杂度为 O(V^3)，空间複杂度为 O(V^3)。

有向图，正边　　O(VVV)
有向图，无负环　O(VVV)
有向图，有负环　不行算

无向图，正边　　O(VVV)
无向图，无负环　不行算
无向图，有负环　不行算

计算最小环的权重

Minimum Ratio Cycle

Minimum Ratio Cycle

“最小比率环”。一张图每条边有两组权重，第一组权重可为任意值，第二组权重不可为负值；于是一只环也有两组权重。最小比率环是“第一组权重除以第二组权重”最小的环，可能有许多只。

已被证明是 NP-hard 问题。

第一个想法：搜寻答案

找出图上所有的环，比较各个环的比率之后，就得到最小比率环了。然而，要找出图上所有的环，是不容易的事情。

逆向思考，直接搜寻比率，再来看图上有哪些环符合比率吧！

第二个想法：除法化作减法

令边的两组权重标记为 w1 和 w2，环的两组权重标记为∑w1 和∑w2，环的比率标记为 r = ∑w1÷∑w2。

我们想知道一只环的比率 r 是多少，也就是说我们想知道∑w1÷∑w2 是多少，也就是说我们想知道∑w1 会等于多少的 r×∑w2──要是直接把∑w1 与 r×∑w2 相减，亦可表示∑w1 与 r×∑w2 的多寡关係：r 太小就表示差值是正数，r 刚刚好就表示差值是零，r 太大就表示差值是负数。利用这种方式，原本难以分析的除法式子，就成了容易分析的减法式子了。

为了凑出这道减法式子，把原来权重为 w1 和 w2 的一条边，改为权重为 w1 - r×w2 的一条边。如此一来，环的权重就变成了∑(w1 - r×w2) = ∑w1 - r×∑w2，这就成了我们所要的减法式子。

现在只要设定好 r，然后看看图上有没有零环，如果有零环就表示这个 r 是合理的比率值。新图上的零环，就是原图上比例为 r 的环。

新图的权重 v.s. 原图的比率

设定好 r 之后，新图上究竟有哪些环？

一、如果新图上有负环：这个负环的权重∑(w1 - r×w2) = ∑w1 - r×∑w2 < 0，可推得∑w1÷∑w2 < r。也就是说找到了一个负环，比率比 r 还小。

二、如果新图上没有负环，但有零环：可推得∑w1÷∑w2 = r。由于图上没有负环，没有比率比 r 小的环，所以这个零环就是最小比率环，r 就是最小比率环的比率。

三、新图上没有负环、没有零环，但有正环：可推得∑w1÷∑w2 > r。也就是说图上所有的环，比率都比 r 还大。

四、新图上没有环：没有环就不会有最小比率环。

至此，这个问题已变成搜寻最小比率环的比率，并判断图上有没有负环的问题了。要判断图上有没有负环，可以利用各种侦测负环的演算法，例如 Label Correcting Algorithm。

Binary Search

比率太小就有负环，比率太大就没有负环。所以可以用 Binary Search 找答案。

演算法

1. 搜寻最小比率环的比率 r。
2. 把图上的边的两组权重 w1 和 w2，改为只有一组权重 w1-r×w2，

X. 可使用 Binary Search 找出正确的比率 r：
   图上有负环表示 r 太小，图上没负环表示 r 太大，
   没有负环只有零环表示 r 是正解。

时间複杂度等同于侦测负环 O(logR) 次的时间，R 是可能的比率范围。

计算最小比率环的比率

【待补程式码】

找出一只最小比率环

【待补程式码】

Minimum Mean Cycle

Minimum Mean Cycle

尚无中译，暂译“最小平均值环”。一张图上每条边都有权重，最小平均值环是“权重除以边数”最小的环，可能有许多只。

最小平均值环也可以视作是最小比率环的特例，当每条边的第二组权重都等于 1 的时候。

有向图演算法（Karp's Algorithm）

请参考 CLRS 在 Bellman-Ford Algorithm 章节的练习题，事实上也能求出最大平均值环。用到了两个概念：

一、图上所有边的权重，同时增减一数值，不影响最小平均值环的位置（但是会影响最小环的位置）。

二、单源最短路径往外延伸，一旦碰触到最小平均值环（或者最小环），就会不断绕行之，让路径长度增加最少。此演算法採用穷举法，求出单源最短路径进入最小平均值环的起点。

令 V 为图上的所有点构成的集合，n 为图上的点数。
图上任意取一个点作为起点，d(k, i) 为起点走 k 条边到达 i 点的最短路径。

                      d(n, i) - d(k, i)
平均权重 = min  max   ———————————————————
          i∊V 0≤k≤n-1       n - k

如果图不连通，可以使用 Johnson's Algorithm 提到的技巧，新增一个起点，新增起点到图上各点的边，权重皆设为相同数值（例如零）。如此一来，图上每一点都可以由起点走到，而且不影响最小平均值环的位置。

图的资料结构为 adjacency matrix，时间複杂度是 O(V^3)；图的资料结构为 adjacency lists，时间複杂度是 O(VE)。

计算最小平均值环的平均权重（adjacency matrix）

Feedback Edge Set

Feedback Edge Set

删除图上的边，使得图上无环。所有删除的边称作 Feedback Edge Set。

无向图：无环即是树，Minimum Feedback Edge Set 即是 Maximum Spanning Tree 以外的所有边，P 问题。

有向图：无环即是有向无环图 DAG。Minimum Feedback Edge Set 是 NP-hard 问题。

Feedback Vertex Set

无论无向图还是有向图，都是 NP-hard 问题。

Cycle Basis

Cycle Basis

一张图的子图，可以表示成长度为 E 的 bitset，或者说 01 字串，0 代表有此边，1 代表无此边。

把一只环变成一个 bitset。现在从一张图上找出一大堆环，作为基底，让这些环的 linear combination 可以得到图上所有环。（xor 运算，Galois Field order E。）

cycle basis 的大小为定值 E-(V-1)。问题在于如何让 cycle basis 总权重最小，这是 P 问题。

演算法目前有两大类型，但是时间複杂度都很高。

Fundamental Cycle Basis

Fundamental Cycle Basis

先从一张图上找出一棵 spanning tree，然后每一条剩下的边，各自对应一个独一无二的环。这些剩下的边所形成的环，恰好构成 cycle basis，大小是 E-(V-1)。

让 fundamental cycle basis 总权重最小，这是 NP-hard 问题。

Transmuter

用来记录一棵生成树的 fundamental cycle
是个类似二分图的东西。
X 侧的每个点各自对应树边(tree edge)
Y 侧的每个点各自对应非树边(cross edge)
当某个非树边与树边形成 fundamental cycle
那麽二分图上，该树边到该非树边就有一条路径。
也就是说一个 fundemantal cycle 中，在二分图上所有树边都会连往对应的那条非树边。
然后二分图有设立中继点，以节省连接边数（遇到完全二分图的时候就很好用）
此伪二分图的大小与建立时间皆为 O(E*alpha(E,V))。

无向图最小生成树：                                          (次小生成树)
Y 侧（非树边) 标记，数值为 X 侧邻点(  树边) 最小值，加入非树边时的 best swap edge。
X 侧(  树边) 标记，数值为 Y 侧邻点（非树边) 最小值，删除  树边时的 best swap edge。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(致命边)
无向图最短路径树：
非树边(x,y) 的数值定义为 d(s,x) + w(x,y) + d(y,t)
X 侧(  树边) 标记，数值为 Y 侧邻点（非树边) 最小值，删除  树边时的 best swap edge。
（但是要小心 d(s,x) 不能包含到删除的树边！也就是说要注意(x,y) 的方向。）