cycle - 演算法筆記

cycle

「環」。頭尾循環的路徑。大家習慣令點與邊不可重複。

loop

「自環」。一條邊，自己連向自己。

negative weight cycle

negative weight cycle（negative cycle）

「負環」。權重為負值的環，可能有許多只。

label correcting algortihm、Bellman–Ford algorithm可以找出其中一個負環。時間複雜度O(VE)。

backtracking可以找出所有負環。時間複雜度O(V!)。

minimum weight cycle

minimum weight cycle（shortest cycle）（girth）

「最小環」。一張圖上權重最小的環，可能有許多只。

求最小環如同求最短路徑；求最大環如同求最長路徑。

圖上無負環，P問題。圖上有負環，NP-complete問題。

circumference：外周長。最大環。
girth：內周長。最小環。

演算法

窮舉圖上每一條邊ij：
　甲、暫時拿掉邊ij，權重改成無限大。
　乙、求出j點到i點的最短路徑。
　丙、放回邊ij，形成一個環，即是強制經過邊ij的最小環。
　丁、權重最小者即是最小環。

時間複雜度等同於求O(E)次兩點之間最短路徑的時間。

演算法

Floyd–Warshall algorithm，順手尋找最小環。

時間複雜度O(V³)，空間複雜度O(V³)。

有向圖，正邊　　O(V³)
有向圖，無負環　O(V³)
有向圖，有負環　不適用

無向圖，正邊　　O(V³)
無向圖，無負環　不適用
無向圖，有負環　不適用

計算最小環的權重

找出一個最小環

仿效最短路徑演算法，增廣陣列空間為O(V³)。

然而這種做法實際效率不佳。這裡提供比較簡潔、效率較佳的實作方式，時間複雜度O(V⁴)，空間複雜度O(V²)。

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的環。

新圖的權重 vs. 原圖的比率

設定好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找答案。

演算法

一、搜尋最小比率環的比率r。使用binary search。
二、把圖上的邊的兩組權重w1和w2，改為只有一組權重w1-r×w2，
　甲、圖上有負環：r太小。
　乙、圖上沒負環：r太大。
　丙、沒有負環、只有零環：r剛剛好。得到正解。

時間複雜度等同於偵測負環O(logR)次的時間，R是可能的比率範圍。

計算最小比率環的比率

【待補程式碼】

找出一個最小比率環

【待補程式碼】

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³)；圖的資料結構為adjacency lists是O(VE)。

計算最小平均數環的平均權重

找出一個最小平均數環

【待補程式碼】

UVa 11090

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

「環基底」。環集合，加權總和可以得到圖上所有環。加法只能是xor，權重只能是0和1。

一張圖的子圖，可以表示成長度為E的01向量：0無邊、1有邊。一張圖的環，也可以如此表示。

找出一些環，當作基底，讓這些環的線性組合可以得到圖上所有環。Galois field order E。

環基底的大小是固定值E-(V-1)。

mimimum cycle basis，權重最小的環基底，P問題。

演算法目前有兩大類型，但是時間複雜度都很高。

fundamental cycle basis

「基本環基底」。以生成樹得到環基底。

一張圖上找出一棵spanning tree，剩下E-(V-1)條邊。每一條剩下的邊，各自對應一個獨一無二的環。這些剩下的邊與生成樹所形成的環，可以充作環基底，稱作「基本環基底」。

mimimum fundamental cycle basis，權重最小的基本環基底，NP-hard問題。

transmuter

用來記錄一棵生成樹的 fundamental cycle
是個類似二分圖的東西。
X側的每個點各自對應樹邊(tree edge)
Y側的每個點各自對應非樹邊(cross edge)
當某個非樹邊與樹邊形成 fundamental cycle
那麼二分圖上，該樹邊到該非樹邊就有一條路徑。
也就是說一個 fundemantal cycle 中，在二分圖上所有樹邊都會連往對應的那條非樹邊。
然後二分圖有設立中繼點，以節省連接邊數（遇到完全二分圖的時候就很好用）
此偽二分圖的大小與建立時間皆為O(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)的方向。）