L4 連通度與路徑

符號定義

符號 意義
δ(G)\delta(G) 最小度 (minimum degree)
NG(v)N_G(v) vv 的鄰居集合 (neighborhood)
κ(G)\kappa(G) 圖 GG 的頂點連通度 (connectivity)
λ(G)\lambda(G) 圖 GG 的邊連通度 (edge-connectivity)
κ(x,y)\kappa(x,y) 分開 x,yx,y 所需移除的最少頂點數
λ(x,y)\lambda(x,y) 講義此處用來表示 x,yx,y 間最大兩兩頂點不相交路徑數
[X,Y][X,Y] X,YX,Y 兩頂點集合之間的邊集合

Vertex Cut 與 Connectivity

  • Vertex Cut (點割)

    • 對連通圖 GG，若頂點集合 S⊆V(G)S\subseteq V(G) 滿足 G−SG-S 有超過一個 connected component，則稱 SS 為 vertex cut (點割)。

  • kk-connected (kk-連通)

    • 若從圖 GG 中移除任意少於 kk 個頂點後仍然連通，則稱 GG 是 kk-connected。
    • $ G\text{ 是 }k\text{-connected}\iff\forall S\subseteq V(G),\ |S|<k,\ G-S\text{ 仍連通}$
    • kk-connected ⇒(k−1)\Rightarrow (k-1)-connected。反之不一定成立。

  • Connectivity (連通度): κ(G)\kappa(G)

    • 使 G−SG-S 不連通或只剩一個頂點的頂點集合 SS 的最小大小。
    • κ(G)=min⁡∣S∣\kappa(G)=\min |S|
    • 其中 SS 使得 G−SG-S 不連通，或 G−SG-S 僅剩一個頂點。
圖 κ(G)\kappa(G)
KnK_n n−1n-1
Km,nK_{m,n} min⁡(m,n)\min(m,n)
CnC_n 22
K1,nK_{1,n} 11
Pn (n≥2)P_n\ (n\ge2) 11
Petersen graph 33

對任意頂點數 >1>1 的連通圖: 1≤κ(G)≤δ(G)1\le\kappa(G)\le\delta(G)

  • 取最小度頂點 xx，d(x)=δ(G)d(x)=\delta(G)，若 GG 不是完全圖，移除 N(x)N(x) 後，xx 會和其他頂點分開。因此 N(x)N(x) 可作為一個 vertex cut，大小為 δ(G)\delta(G)。

如何證明 κ(G)=k\kappa(G)=k？

  • κ(G)≥k\kappa(G)\ge k:移除任意少於 kk 個頂點仍連通，也就是 GG 是 kk-connected。
  • κ(G)≤k\kappa(G)\le k:找到某一個大小為 kk 的 vertex cut。

Minimum degree 與 kk-connected:

若 ∣V(G)∣=n|V(G)|=n，且 δ(G)≥k+n−22\delta(G)\ge\frac{k+n-2}{2}

則 GG 是 kk-connected，也就是 κ(G)≥k\kappa(G)\ge k

這是一個充分條件，不是必要條件。 (講義 P20–23)

Edge Cut 與 Edge-connectivity

  • Edge Cut (邊割)
    • 對連通圖 GG，若邊集合 S⊆E(G)S\subseteq E(G) 滿足 G−SG-S 不連通，則稱 SS 為 edge cut(邊割)。
  • kk-edge-connected(kk-邊連通)
    • 若從 GG 中移除任意少於 kk 條邊後仍然連通，則稱 GG 是 kk-edge-connected。
    • kk-edge-connected ⇒(k−1)\Rightarrow(k-1)-edge-connected。反之不一定。
  • Edge-connectivity (邊連通度)
    • λ(G)=min⁡{∣S∣:S⊆E(G), G−S 不連通}\lambda(G)=\min\{|S|:S\subseteq E(G),\ G-S\text{ 不連通}\}

若 X,Y⊆V(G)X,Y\subseteq V(G) 且 X∩Y=∅X\cap Y=\varnothing，則 [X,Y]={xy∈E(G):x∈X, y∈Y}[X,Y]=\{xy\in E(G):x\in X,\ y\in Y\} 表示 XX 與 YY 之間所有的邊。

最小邊割的性質

若 SS 是 GG 的最小 edge cut，則 G−S 恰有兩個 connected componentsG-S\text{ 恰有兩個 connected components}

若切成三個以上 components，通常可以只保留其中一部分割邊就把圖切開，得到更小的 edge cut，與「最小」矛盾。 (講義 P29–30)

對簡單圖 GG: κ(G)≤λ(G)≤δ(G)\kappa(G)\le\lambda(G)\le\delta(G)

點連通度≤邊連通度≤最小度\text{點連通度}\le\text{邊連通度}\le\text{最小度}

常用圖形:

  • Tree TT(∣V(T)∣≥2|V(T)|\ge2):κ(T)=λ(T)=δ(T)=1\kappa(T)=\lambda(T)=\delta(T)=1
  • Km,nK_{m,n}:κ=λ=δ=min⁡(m,n)\kappa=\lambda=\delta=\min(m,n)
  • CnC_n:κ=λ=δ=2\kappa=\lambda=\delta=2
  • PnP_n:κ=λ=δ=1\kappa=\lambda=\delta=1

若 GG 為 3-regular graph，則 κ(G)=λ(G)\kappa(G)=\lambda(G)
已知 κ(G)≤λ(G)≤δ(G)=3\kappa(G)\le\lambda(G)\le\delta(G)=3，再依 κ(G)=1,2,3\kappa(G)=1,2,3 分類即可證明。 (講義 P38)

Blocks

Block(塊): 沒有 cut vertex 的極大連通子圖 (maximal connected subgraph with no cut vertex)。

Block 不一定是 2-connected，因為 K1K_1、K2K_2 也可能是 block。

若 B1,B2B_1,B_2 是不同 blocks，則 ∣V(B1)∩V(B2)∣≤1|V(B_1)\cap V(B_2)|\le1，兩個不同 blocks 最多共用一個頂點。

  • 若共用兩個不同頂點，可以證明 B1∪B2B_1\cup B_2 仍沒有 cut vertex，與 block 的 maximal 性質矛盾。 (講義 P41)

尋找 blocks，使用 DFS:

  1. 建立 DFS tree。
  2. 追蹤目前 subtree 是否有 back edge 連到父節點以上的 ancestor。
  3. 若某 subtree 無法透過 back edge 回到 parent 以上，則該 subtree 與 parent 形成一個 block。
  4. 記錄後將該部分從目前 DFS tree 中移除。

頂點/邊不相交路徑與 kk-connected

  • Vertex-disjoint Paths (頂點不相交路徑)
    • 兩條 u−vu-v path 若除了起點 uu、終點 vv 外沒有任何共同頂點，稱為頂點不相交。

2-connected 的等價條件:

對至少 3 個頂點的圖 GG，下列條件等價:

  • GG 連通且沒有 cut vertex。
  • 任意兩頂點 x,yx,y 間有兩條 vertex-disjoint x−yx-y paths。
  • 任意兩頂點 x,yx,y 都在同一個 cycle 上。
  • δ(G)≥1\delta(G)\ge1，且任意一對 edges 都包含在某一個 cycle 中。

證明在講義 P60–63

擴張引理:

若 GG 是 kk-connected，加入新頂點 yy，並讓 yy 與 GG 中任意 kk 個頂點相鄰，則所得新圖仍為 kk-connected。

G 是 k-connected, d(y)≥k⟹G+y 仍為 k-connectedG\text{ 是 }k\text{-connected},\ d(y)\ge k\Longrightarrow G+y\text{ 仍為 }k\text{-connected}

證明依 被刪除的集合 SS 是否包含 yy 分兩種 case。 (講義 P58–59)

連接兩個 kk-connected graphs

若 G,HG,H 是頂點不相交的 kk-connected graphs:

  • 要保證將 G,HG,H 接起來後仍是 kk-connected，至少需要在兩圖之間加入 kk 條 matching edges。
  • 若 ∣V(G)∣=∣V(H)∣|V(G)|=|V(H)| 且兩圖之間加入一組 perfect matching，講義指出所得圖為 (k+1)(k+1)-connected。 (講義 P64–69)
  • Edge-disjoint Paths (邊不相交路徑)
    • 兩條 u−vu-v paths 沒有共同 edge，就稱為邊不相交。
    • vertex-disjoint⇒edge-disjoint\text{vertex-disjoint}\Rightarrow\text{edge-disjoint}，反之不一定成立。

對任意 e∈E(G)e\in E(G): κ(G)−1≤κ(G−e)≤κ(G)\kappa(G)-1\le\kappa(G-e)\le\kappa(G)
也就是刪除一條 edge，頂點連通度最多下降 1。 (講義: 72–74)

Menger’s Theorem

  • x,yx,y-separator
    • 給定 x,y∈V(G)x,y\in V(G)，若 S⊆V(G)−{x,y}S\subseteq V(G)-\{x,y\}，且 G−SG-S 中不存在 x−yx-y path，則稱 SS 為 x,yx,y-cut / x,yx,y-separator。
  • κ(x,y)\kappa(x,y): x,yx,y-separator 的最小大小。
  • λ(x,y)\lambda(x,y): x,yx,y 之間最大數量的兩兩 vertex-disjoint paths。

Menger Theorem (Vertex Version):

若 x,yx,y 是圖 GG 中兩個不相鄰頂點，則 κ(x,y)=λ(x,y)\kappa(x,y)=\lambda(x,y)

分開 x,yx,y 所需要移除的最少頂點數 = x,yx,y 之間最大數量的兩兩頂點不相交路徑。

應用:

G 是 k-connected  ⟺  G 的任意兩頂點間都有 k 條兩兩 vertex-disjoint pathsG\text{ 是 }k\text{-connected}\iff G\text{ 的任意兩頂點間都有 }k\text{ 條兩兩 vertex-disjoint paths}

因此，若 GG 為連通圖，任意兩頂點至少存在 κ(G)\kappa(G) 條兩兩 vertex-disjoint paths。

Menger Theorem (Edge Version):

對任意頂點 x,yx,y: 分開 x,y 所需移除的最少 edge 數=最大兩兩 edge-disjoint x−y paths 數\text{分開 }x,y\text{ 所需移除的最少 edge 數}=\text{最大兩兩 edge-disjoint }x-y\text{ paths 數}

應用:

G 是 k-edge-connected  ⟺  任意兩頂點間有 k 條兩兩 edge-disjoint pathsG\text{ 是 }k\text{-edge-connected}\iff\text{任意兩頂點間有 }k\text{ 條兩兩 edge-disjoint paths}

若 GG 是 kk-connected，則 ∣V(G)∣≥k(diam⁡(G)−1)+2|V(G)|\ge k(\operatorname{diam}(G)-1)+2

取距離等於 diameter 的 x,yx,y，Menger 保證至少有 kk 條兩兩 vertex-disjoint x−yx-y paths；每條 path 除 x,yx,y 外至少有 diam⁡(G)−1\operatorname{diam}(G)-1 個頂點。

edge 版本:

若 GG 是 kk-edge-connected，則 ∣E(G)∣≥kdiam⁡(G)\boxed{|E(G)|\ge k\operatorname{diam}(G)}。

證明在講義 P84–85