[科普中國(guó)]-傳遞閉包

存在性和描述定義

對(duì)于任何關(guān)系 R，R 的傳遞閉包總是存在的。傳遞關(guān)系的任何家族的交集也是傳遞的。進(jìn)一步的，至少存在一個(gè)包含 R 的傳遞關(guān)系，也就是平凡的: X × X。R 傳遞閉包給出自包含 R 的所有傳遞關(guān)系的交集。1

我們可以用更具體術(shù)語(yǔ)來(lái)描述 R 的傳遞閉包如下。定義在 X 上的一個(gè)關(guān)系 T，稱 xTy 當(dāng)且僅當(dāng)存在有限的元素( )序列，使得 并且

, , …, 和

形式上寫(xiě)為容易檢查出關(guān)系 T 是傳遞的并且包含 R。進(jìn)一步的，任何包含 R 的傳遞關(guān)系也包含 T，所以 T 是 R 的傳遞閉包。

有關(guān)概念關(guān)系 R 的傳遞簡(jiǎn)約是有 R 作為它的傳遞閉包的最小關(guān)系。一般的說(shuō)它不是唯一的。

證實(shí) T 是包含 R 的最小傳遞關(guān)系證明設(shè) A 是任何元素的集合。

假定: GA 傳遞關(guān)系 RAGA TAGA。所以 (a,b)GA(a,b)TA. 所以，特定的 (a,b)RA。

現(xiàn)在通過(guò) T 的定義，我們知道了 n (a,b)RnA。接著，i, in eiA。所以，有從 a 到 b 路徑如下: aRAe1RA...RAe(n-1)RAb。

但是，通過(guò) GA 在 RA 上的傳遞性，i, in (a,ei)GA，所以，(a,e(n-1))GA (e(n-1),b)GA，所以通過(guò) GA 的傳遞性，我們得到了 (a,b)GA。矛盾于 (a,b)GA。

因此，(a,b)AA, (a,b)TA (a,b)GA。這意味著 TG，對(duì)于任何包含 R 的傳遞的 G。所以，T 是包含 R 的最小傳遞閉包。

推論如果 R 是傳遞的，則 R = T。

用途注意兩個(gè)傳遞關(guān)系的并集不必須是傳遞的。為了保持傳遞性，必須采用傳遞閉包。例如，這出現(xiàn)在取兩個(gè)等價(jià)關(guān)系或預(yù)序的并的時(shí)候。為了獲得新的等價(jià)關(guān)系或預(yù)序，必須選用傳遞閉包(自反性和對(duì)稱性 — 在等價(jià)關(guān)系的情況下 — 是自動(dòng)的)。2

有向無(wú)環(huán)圖(DAG)的傳遞閉包是 DAG 的可到達(dá)性關(guān)系和一個(gè)嚴(yán)格偏序。

與復(fù)雜性的關(guān)系在計(jì)算復(fù)雜性理論中，復(fù)雜度類 NL 嚴(yán)格對(duì)應(yīng)于可使用一階邏輯和傳遞閉包表達(dá)的邏輯句子的集合。這是因?yàn)閭鬟f閉包性質(zhì)有密切關(guān)系于 NL-完全問(wèn)題 STCON，找到在一個(gè)圖中的有向路徑。類似的，類 L 是一階邏輯帶有交換傳遞閉包。在向二階邏輯增加了傳遞閉包的時(shí)候，我們得到 PSPACE。

算法計(jì)算圖的傳遞閉包的有效算法可見(jiàn)于 here。最簡(jiǎn)單的技術(shù)是Floyd-Warshall算法。3

Floyd-Warshall算法單獨(dú)一條邊的路徑也不一定是最佳路徑。 從任意一條單邊路徑開(kāi)始。所有兩點(diǎn)之間的距離是邊的權(quán)的和，(如果兩點(diǎn)之間沒(méi)有邊相連, 則為無(wú)窮大）。 對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。 不可思議的是，只要按排適當(dāng)，就能得到結(jié)果。// dist(i,j) 為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離

For i←1to n do

For j←1to n do

dist(i,j) = weight(i,j)

For k←1to n do// k為“媒介節(jié)點(diǎn)”{一定要先枚舉媒介節(jié)點(diǎn)}

For i←1to n do

For j←1to n do

if(dist(i,k) + dist(k,j)

dist(i,j) = dist(i,k) + dist(k,j)

這個(gè)算法的效率是O(V^3)。它需要鄰接矩陣來(lái)儲(chǔ)存圖。

這個(gè)算法很容易實(shí)現(xiàn)，只要幾行。

即使問(wèn)題是求單源最短路徑，還是推薦使用這個(gè)算法，如果時(shí)間和空間允許(只要有放的下鄰接矩陣的空間，時(shí)間上就沒(méi)問(wèn)題)。

計(jì)算每一對(duì)頂點(diǎn)間的最短路徑（floyd算法）

核心代碼for(k=0;k