Try   HackMD

連通性與 Menger 定理

雖然這篇被歸類在網路流量問題之中,但是為了銜接下一篇最大流量-最小割定理,我會暫時離題並討論一下什麼是「割 (cut)」。一般討論割的目的是為了瞭解一張圖 (graph) 是否足夠穩固,或至少要移除多少節點或邊才能使整張圖分為兩個連通塊 (component)。可以想像要是在一個公路的路網,被摧毀幾條公路就會使兩地之間無法溝通。顯然這是一個很重要的問題

本篇會來介紹點割 (vertex cut)、邊割 (edge cut) 與連通性 (connectivity)。最後會來介紹 Menger 定理,說明點割、邊割與路徑乃至於整張圖的關係。Menger 定理在圖論是個極為重要的存在,因為它的效力與許多不同的定理等價,像是 Hall 定理Kőnig 定理等都能使用 Menger 定理互相推出來

點割 Vertex Cut

定義

  • 在一張圖
    G
    中,若存在集合
    SV(G)
    使
    GS
    有多於一個連通塊,則
    S
    是一個點割 (vertex cut)
  • 給定
    x,yV(G)
    ,若存在集合
    SV(G){x,y}
    使
    GS
    沒有從
    x
    y
    的路徑,則
    S
    被稱為
    x,y
    點割 (
    x,y
    -cut)
  • κ(x,y)
    為最小
    S
    的元素個數,即最小
    x,y
    -cut 的大小

舉例

如下圖

G 可以找到一個最小的
x,y
-cut
S={b,c,d}
,使
κ(x,y)=3

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

定義

一張圖

G 的點連通性寫作
κ(G)
,為一張圖中最小
S
的元素個數,使
GS
不連通或只剩一個節點。若一張圖是的點連通性最少為
k
,則稱圖是
k
-connected

可以將點連通性寫作

κ(G)=minx,yV(G) κ(x,y)

舉例

Kn
的點連通性

不難看出,因為所有節點都彼此相鄰,完全圖

Kn 的點連通性
κ(Kn)=n1
,且
GS
只會剩下一個節點。可以推出,若一張圖
G=(V,E)
不是完全圖,則
κ(G)|V|2
。可以自己比較看看以下兩張圖的點連通性分別為何

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

定義

  • 在一張圖
    G
    中,若存在集合
    FE(G)
    使
    GF
    有多於一個連通塊,則
    F
    是一個分割集 (disconnecting set)
  • 給定
    S,TV(G)
    [S,T]
    為一個兩終點分別在
    S
    T
    的邊集合
  • 邊割 (edge cut) 是一個邊集,寫作
    [S,S¯]
    。其中,
    SV(G)
    S¯=V(G)S
  • F
    為邊集合,
    κ(x,y)
    為最小
    F
    的元素個數,使
    GF
    沒有路徑可以從
    x
    y

舉例

如下左圖紅邊為分割集,右圖為邊割

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

定義

一張圖

G 的邊連通性寫作
κ(G)
,為最小分割集的元素個數。若一張圖是
k
-邊連通,則每個分割集都需要至少有
k
條邊

可以將邊連通性寫作

κ(G)=minx,yV(G) κ(x,y)

κκδ

定理 (Whitney[1932])

G=(V,E) 是一個 simple graph,則
κ(G)κ(G)δ(G)
。其中,
δ(G)
G
中度數 (degree) 最少的節點度數

證明

κ(G)δ(G) : 我們可以刪去度數最小的節點相連的所有邊來找到
κ(G)
的上限
κ(G)κ(G)
: 根據點連通性的例子,可以得到
κ(G)|V|1
。考慮一個邊割
[S,S¯]
,若所有
S
中的節點都與所有
S¯
中的節點都相鄰,則
|[S,S¯]|=|S||S¯||V|1κ(G)
滿足度等式。若所有
S
中的節點並沒有與所有
S¯
中的節點都相鄰,我們可以來找找看不相鄰的兩點
xS
yS¯
。令
T
裡裝著所有
x
S¯
的鄰居以及所有
Sx
且在
S¯
有鄰居的節點。可以觀察出
T
是一個點割。我們可以再挑從
x
TS¯
的邊與每個
TS
中的節點任選一條到
S¯
,如此一來就會有
|T|
條不同的邊在
[S,S¯]
中。因此
κ(G)=|[S,S¯]||T|κ(G)

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 特例

G 是 3-regular,即
G
中所有節點
v
的度數皆為
3
,則
κ(G)=κ(G)
。這是一個顯然的例子,也很好證。這裡就交給讀者自己找找看是否有反例存在

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 →

 
如上圖,若是要把
x,y
切開來,可以選擇刪除
3
個點
a,b,c
,也可以選擇刪除
3
條邊
xa,xb,xc
,使
x
孤立。當然也有其他選擇,但刪去的邊數與點數皆會保持相同

Menger 定理

Menger 定理主要可以拆成兩部分,在此以定理

1 與定理
2
來分別說明

內部不相交路徑 Internally Disjoint Paths

  • 若兩條從
    x
    y
    的路徑裡面並沒有共用的節點,則稱為內部不相交路徑
  • x,y
    的最大內部不相交路徑數量寫作
    λ(x,y)
  • 若兩條從
    x
    y
    的路徑裡面並沒有共用邊,則稱為內部不相交邊路徑
  • x,y
    的最大內部不相交邊路徑數量寫作
    λ(x,y)

定理 1 (Menger[1927])

x,yV(G)
xyE(G)
,則
κ(x,y)=λ(x,y)

證明定理 1

透過觀察,我們不難發現,由於內部不相交路徑中彼此節點不共用,因此

κ(x,y)λ(x,y)。為了證明等式,我們對
n(G)
使用歸納法

  • Basis step :
    n(G)=2
    ,因
    xyE(G)
    κ(x,y)=λ(x,y)=0
  • Induction step :
    n(G)>2
    。令
    k=κG(x,y)
    。我們可以建構出
    k
    條內部不相交路徑,以下將拆成兩個狀況來討論

Case 1 : 最小
x,y
-cut 的節點至少有一個不是
N(x)
N(y)
的節點

為了建出

k 條路徑 (根據歸納假設),我們可以建構出下圖,其中
V1
x,S
-路徑上的節點,
V2
S,y
路徑上的節點

我們可以證明

S=V1V2,因為
S
上的節點都會在路徑上,所以
SV1V2
。若存在
v(V1V2)S
,則存在一條路徑包含
v
的同時又迴避
S
,顯然這是不可能的,因此
S=V1V2
得證。相同地,
V1
忽略
N(y)S
,且
V2
忽略
N(x)S

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 →

 
接下來我們把圖拆成
H1,H2
兩張圖,使
V1
的所有節點放入
H1
,使
V2
的所有節點放入
H2
,並在
H1
S
連上
y
H2
S
連上
x
。因
y
S
直接相連,
κH1(x,y)=k
。相同地在
H2
中,
κH2(x,y)=k

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 →

 
V1
忽略
N(y)S
,且
V2
忽略
N(x)S
H1
H2
與相似於
G
。因此歸納假設可以推出
κH1(x,y)=k=κH2(x,y)
。我們將
x,y
刪除之後接起來變成原來的圖
G
,就可以知道
G
k
條內部不相交路徑

Case 2 : 最小
x,y
-cut 的節點都是
N(x)
N(y)
的節點

我們一樣使用建構法建出

k 條路徑。由於並非所有圖都是類似二分圖的樣子,因此以下的 1. 與 2. 可以將圖處理成 3. 的狀況,也就是類似二分圖的模樣

  1. 若有一節點
    v{x}N(x)N(y){y}
    ,則
    κGv(x,y)=k
    ,如此一來就可以得到歸納假設中的
    x,y
    -路徑
  2. 若存在
    uN(x)N(y)
    ,則
    u
    必會出現在每條
    x,y
    -路徑中,將其刪掉會得到
    κGu(x,y)=k1
    。如此一來就可以得到歸納假設中對於
    Gv
    k1
    x,y
    -路徑
  3. N(x)
    N(y)
    會把
    G{x,y}
    切成兩份,令
    G
    N(x),N(y)
    的二分圖,其中邊集合就是邊割
    [N(x),N(y)]
    。如此一來,
    G
    中的
    x,y
    點割就是
    G
    的點覆蓋。根據 Kőnig 定理,最大匹配數等於最小點覆蓋數,因此我們可以得到
    k
    條長度為
    3
    的內部不相交路徑,符合歸納假設
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

一張圖

G 的線圖寫作
L(G)
,其中在
G
中的所有邊都是
L(G)
中的節點
如下圖,
e,fE(G)
e,fV(L(G))

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])

x,y
G
中不同的節點,則
κ(x,y)=λ(x,y)

證明定理 2

將圖

G 加上兩節點
s,t
與邊
sx,yt
形成新的圖
G
,這樣不影響
κ(x,y)
λ(x,y)
的答案。接下來我們變個魔法把
G
轉化為線圖
L(G)
,則
κG(x,y)=κL(G)(sx,ty)
,且
λG(x,y)=λL(G)(sx,yt)
。根據 Menger 定理的定理 1,可得
κG(x,y)=κL(G)(sx,ty)=λL(G)(sx,yt)=λG(x,y)

Hall 定理轉換成 Menger 定理

其實 Menger 定理與 Hall 定理邏輯等價,兩者可以互相推出來。這邊就示範如何使用 Hall 定理轉換成 Menger 定理

Hall 定理

X,Y-二分圖中有一匹配使
X
的節點都能被匹配,若且為若對於所有
SX
|N(S)||S|

定理 : Hall 定理轉換成 Menger 定理

X,Y-二分圖
G
。我們可以再加上兩個特別的節點
a,b
,並將
a
X
的所有節點建邊,
b
Y
的所有節點建邊,如此一來就形成了另一張圖
G

k=|X|,我們可以宣稱,所有
a,b
-cut 都最少有
k
個節點。設
S=AB
是一個
a,b
-cut,
AX
BY
。因
S
是一個點割,沒有有一條邊能連接
XA
的節點與
YB
的節點,且
N(XA)B
。根據 Hall 定理,可以得到
|XA||N(XA)||B|
。所以推得
|S|=|A|+|B||A|+|XA|=|X|=k
,而所得到的
G
就是 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 →

 
註 :
N(XA)
是指
XA
的鄰居集合

為什麼 Menger 定理很重要 ?

  1. Menger 定理的效力等價於 Hall 定理,因此 Menger 定理也可以證出 Kőnig-Egerváry 定理
  2. Menger 定理可以證出最大流-最小割定理,最大流-最小割定理也可以證出 Menger 定理
  3. 最大流-最小割定理可以證出 Kőnig-Egerváry 定理

以上三點意味著,二分圖中最大匹配問題、最小點覆蓋問題、最大獨立集問題、最小邊覆蓋問題、最小邊/點割問題、最大互斥邊/點路徑問題與最大流量問題都可以互相轉換。除此之外,許多相關的問題也都是可以互相轉換的,這或許也是為什麼競程中的 flow 題會那麼難看出來的原因

備註

  • Menger 定理的證明有超過
    15
    個版本
  • Menger 定理的最初版本其實有些瑕疵,最後是被 Kőnig 修正

參考資料


ShanC 程式競賽筆記
作者: ShanC
更新: 2025/3/23