連通性與 Menger 定理
雖然這篇被歸類在網路流量問題之中,但是為了銜接下一篇最大流量-最小割定理,我會暫時離題並討論一下什麼是「割 (cut)」。一般討論割的目的是為了瞭解一張圖 (graph) 是否足夠穩固,或至少要移除多少節點或邊才能使整張圖分為兩個連通塊 (component)。可以想像要是在一個公路的路網,被摧毀幾條公路就會使兩地之間無法溝通。顯然這是一個很重要的問題
本篇會來介紹點割 (vertex cut)、邊割 (edge cut) 與連通性 (connectivity)。最後會來介紹 Menger 定理,說明點割、邊割與路徑乃至於整張圖的關係。Menger 定理在圖論是個極為重要的存在,因為它的效力與許多不同的定理等價,像是 Hall 定理、 Kőnig 定理等都能使用 Menger 定理互相推出來
點割 Vertex Cut
定義
- 在一張圖 中,若存在集合 使 有多於一個連通塊,則 是一個點割 (vertex cut)
- 給定 ,若存在集合 使 沒有從 到 的路徑,則 被稱為 點割 (-cut)
- 為最小 的元素個數,即最小 -cut 的大小
舉例
如下圖 可以找到一個最小的 -cut ,使
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
點連通性 Vertex Connectivity
定義
一張圖 的點連通性寫作 ,為一張圖中最小 的元素個數,使 不連通或只剩一個節點。若一張圖是的點連通性最少為 ,則稱圖是 -connected
可以將點連通性寫作
舉例
的點連通性
不難看出,因為所有節點都彼此相鄰,完全圖 的點連通性 ,且 只會剩下一個節點。可以推出,若一張圖 不是完全圖,則 。可以自己比較看看以下兩張圖的點連通性分別為何
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
邊割與分割集 Edge Cut and Disconnecting Set
定義
- 在一張圖 中,若存在集合 使 有多於一個連通塊,則 是一個分割集 (disconnecting set)
- 給定 , 為一個兩終點分別在 與 的邊集合
- 邊割 (edge cut) 是一個邊集,寫作 。其中, 且
- 若 為邊集合, 為最小 的元素個數,使 沒有路徑可以從 到
舉例
如下左圖紅邊為分割集,右圖為邊割
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
分割集 vs 邊割
所有邊割必為分割集,但分割集不必然是邊割。僅極小 (minimal) 的分割集是割邊
邊連通性 Edge Connectivity
定義
一張圖 的邊連通性寫作 ,為最小分割集的元素個數。若一張圖是 -邊連通,則每個分割集都需要至少有 條邊
可以將邊連通性寫作
定理 (Whitney[1932])
若 是一個 simple graph,則 。其中, 為 中度數 (degree) 最少的節點度數
證明
: 我們可以刪去度數最小的節點相連的所有邊來找到 的上限
: 根據點連通性的例子,可以得到 。考慮一個邊割 ,若所有 中的節點都與所有 中的節點都相鄰,則 滿足度等式。若所有 中的節點並沒有與所有 中的節點都相鄰,我們可以來找找看不相鄰的兩點 與 。令 裡裝著所有 在 的鄰居以及所有 且在 有鄰居的節點。可以觀察出 是一個點割。我們可以再挑從 到 的邊與每個 中的節點任選一條到 ,如此一來就會有 條不同的邊在 中。因此
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
3-regular 特例
若 是 3-regular,即 中所有節點 的度數皆為 ,則 。這是一個顯然的例子,也很好證。這裡就交給讀者自己找找看是否有反例存在
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
如上圖,若是要把 切開來,可以選擇刪除 個點 ,也可以選擇刪除 條邊 ,使 孤立。當然也有其他選擇,但刪去的邊數與點數皆會保持相同
Menger 定理
Menger 定理主要可以拆成兩部分,在此以定理 與定理 來分別說明
內部不相交路徑 Internally Disjoint Paths
- 若兩條從 到 的路徑裡面並沒有共用的節點,則稱為內部不相交路徑
- 的最大內部不相交路徑數量寫作
- 若兩條從 到 的路徑裡面並沒有共用邊,則稱為內部不相交邊路徑
- 的最大內部不相交邊路徑數量寫作
定理 1 (Menger[1927])
若 且 ,則
證明定理 1
透過觀察,我們不難發現,由於內部不相交路徑中彼此節點不共用,因此 。為了證明等式,我們對 使用歸納法
- Basis step : ,因 ,
- Induction step : 。令 。我們可以建構出 條內部不相交路徑,以下將拆成兩個狀況來討論
Case 1 : 最小 -cut 的節點至少有一個不是 或 的節點
為了建出 條路徑 (根據歸納假設),我們可以建構出下圖,其中 是 -路徑上的節點, 是 路徑上的節點
我們可以證明 ,因為 上的節點都會在路徑上,所以 。若存在 ,則存在一條路徑包含 的同時又迴避 ,顯然這是不可能的,因此 得證。相同地, 忽略 ,且 忽略
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
接下來我們把圖拆成 兩張圖,使 的所有節點放入 ,使 的所有節點放入 ,並在 的 連上 、 的 連上 。因 與 直接相連,。相同地在 中,
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
因 忽略 ,且 忽略 , 跟 與相似於 。因此歸納假設可以推出 。我們將 刪除之後接起來變成原來的圖 ,就可以知道 有 條內部不相交路徑
Case 2 : 最小 -cut 的節點都是 或 的節點
我們一樣使用建構法建出 條路徑。由於並非所有圖都是類似二分圖的樣子,因此以下的 1. 與 2. 可以將圖處理成 3. 的狀況,也就是類似二分圖的模樣
- 若有一節點 ,則 ,如此一來就可以得到歸納假設中的 -路徑
- 若存在 ,則 必會出現在每條 -路徑中,將其刪掉會得到 。如此一來就可以得到歸納假設中對於 有 條 -路徑
- 若 與 會把 切成兩份,令 為 的二分圖,其中邊集合就是邊割 。如此一來, 中的 點割就是 的點覆蓋。根據 Kőnig 定理,最大匹配數等於最小點覆蓋數,因此我們可以得到 條長度為 的內部不相交路徑,符合歸納假設
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
註 : 以上圖的實線皆為內部不相交路徑
線圖 Line Graph
一張圖 的線圖寫作 ,其中在 中的所有邊都是 中的節點
如下圖,,
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
註 : 此定義在有向圖也適用
定理 2 (Ford and Fulkerson[1956])
若 為 中不同的節點,則
證明定理 2
將圖 加上兩節點 與邊 形成新的圖 ,這樣不影響 與 的答案。接下來我們變個魔法把 轉化為線圖 ,則 ,且 。根據 Menger 定理的定理 1,可得
Hall 定理轉換成 Menger 定理
其實 Menger 定理與 Hall 定理邏輯等價,兩者可以互相推出來。這邊就示範如何使用 Hall 定理轉換成 Menger 定理
Hall 定理
-二分圖中有一匹配使 的節點都能被匹配,若且為若對於所有 ,
定理 : Hall 定理轉換成 Menger 定理
設 -二分圖 。我們可以再加上兩個特別的節點 ,並將 與 的所有節點建邊, 與 的所有節點建邊,如此一來就形成了另一張圖
令 ,我們可以宣稱,所有 -cut 都最少有 個節點。設 是一個 -cut,,。因 是一個點割,沒有有一條邊能連接 的節點與 的節點,且 。根據 Hall 定理,可以得到 。所以推得 ,而所得到的 就是 Menger 定理的圖
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
註 : 是指 的鄰居集合
為什麼 Menger 定理很重要 ?
- Menger 定理的效力等價於 Hall 定理,因此 Menger 定理也可以證出 Kőnig-Egerváry 定理
- Menger 定理可以證出最大流-最小割定理,最大流-最小割定理也可以證出 Menger 定理
- 最大流-最小割定理可以證出 Kőnig-Egerváry 定理
以上三點意味著,二分圖中最大匹配問題、最小點覆蓋問題、最大獨立集問題、最小邊覆蓋問題、最小邊/點割問題、最大互斥邊/點路徑問題與最大流量問題都可以互相轉換。除此之外,許多相關的問題也都是可以互相轉換的,這或許也是為什麼競程中的 flow 題會那麼難看出來的原因
備註
- Menger 定理的證明有超過 個版本
- Menger 定理的最初版本其實有些瑕疵,最後是被 Kőnig 修正
參考資料
ShanC 程式競賽筆記
作者: ShanC
更新: 2025/3/23