基礎圖論 (二): 連通結構、路徑與環

藉由基礎圖論 (一)，我們基礎的認識了圖的結構與一些有趣的圖。本章來聊聊圖的一些連通與環的一些專有名詞，最後會來講講各種在不同地方會看到的圖

注意 : 在我的筆記中，如果沒特別說明是有向圖還是無向圖，那應該就是指無向圖

走訪一張圖

行走 Walk

假設在一張圖上，我們可以隨便走，然後將走過的節點與邊都記錄下來，那應該會得到一個序列

$⟨v_0,e_1,v_1,\dots ,e_k,v_k⟩$，那麼這個序列我們就稱之為一條「行走」

下圖中，存在一行走

$⟨v_1,e_2,v_2,e_5,v_3,e_6,v_1,e_1,v_2,e_2,v_1⟩$。由例子會發現，行走是允許重複的

行走分成兩種:

• 開行走 (open walk) : 頭與尾的節點不相同
• 閉行走 (closed walk) : 頭與尾的節點相同

道路 Trail

如果一個行走並沒有重複的邊 (但可能有重複的節點)，則稱其為「道路」。如下圖，

$⟨v_1,v_3,v_8,v_6,v_3,v_2,v_1⟩$ 是一條道路。由於此圖是一張簡單圖，故可以不寫邊，因為對於任兩節點的邊都是固定的

如果一條道路經過所有邊，則稱為歐拉道路 (Eulerian trail)
道路分成兩種:

• 開道路 (open trail) : 頭與尾的節點不相同
• 閉道路 (closed trail) : 頭與尾的節點相同

迴路 Circuit

如果一條道路為閉道路，則稱其為「迴路」。一個迴路的邊不可重複，但是點可以重複。 如下圖中

$⟨v_1,v_2,v_3,v_4,v_5,v_3,v_1⟩$ 為一條迴路

若一迴路經過所有邊，則稱為歐拉迴路 (Eulerian circuit)

路徑 Path

一條道路節點不重複，則稱為「路徑」。如下圖中

$⟨v_5,v_4,v_3,v_1,v_2⟩$ 為一條路徑

在一簡單圖中，可能存在一條最長路徑經過所有節點

環 Cycle

當遍歷一條路徑時，最後又走一條邊回到起點，則稱此為環。如下圖中

$⟨v_1,v_2,v_4,v_5,v_3,v_1⟩$ 為一環

在一環中，只有起點與終點可以重複，其他節點及邊皆不可重複

簡單整理

分類	邊 edge	節點 vertex	開 open	閉 closed
行走 walk	可重複	可重複	開行走	閉行走
道路 trail	不可重複	可重複	開道路	閉道路 (迴路)
路徑 path	不可重複	不可重複	開路徑	閉路徑 (環)

連通 Connect

設有一張圖

$G$

• 若
  $G$ 是連通的 (connected)，那
  $G$ 就必存在一條
  $(u,v)$ 路徑，否則就是不連通的 (disconnected)
• 若
  $G$ 有一條
  $(u,v)$ 路徑，則
  $u$ 與
  $v$ 連通
• 若有一條
  $(u,v)$ 邊，則
  $u$ 與
  $v$ 相鄰 (adjacent)

以上圖為例，

$a$ 與

$c$ 連通，但

$b$ 與

$e$ 不連通；

$a$ 與

$c$ 連通，因此存在至少一條路徑

割 Cuts

前面討論連通，這篇來把圖切開來。這在連通性與 Menger 定理會討論到一點他們的性質

割點 Cut-vertex (Articulation vertex)

若移除一個節點可以把一個連通塊分成多個連通塊，則稱此節點為割點 (關節點)

點割 Vertex-cut

在一張圖

$G$ 中，若存在集合

$S\subseteq V(G)$ 使

$G-S$ 有多於一個連通塊，則

$S$ 是一個點割 (vertex cut)

割邊 Cut-edge (Bridge)

若移除一條邊可以將一個連通塊分成兩個連通塊，則此邊稱為割邊 (橋)

邊割 Edge Cut

邊割 (edge cut) 是一個邊集，寫作

$[S,\overline{S}]$。其中，

$S\subset V(G)$ 且

$\overline{S}=V(G)-S$。若給定

$S,T\subseteq V(G)$，

$[S,T]$ 為一個兩終點分別在

$S$ 與

$T$ 的邊集合

分割集 Disconnecting Set

在一張圖

$G$ 中，若存在集合

$F\subseteq E(G)$ 使

$G-F$ 有多於一個連通塊，則

$F$ 是一個分割集 (disconnecting set)

連通塊 Connected Components

連通塊定義 The Definition of Connected Component

連通塊又稱連通分量、連通單元、連通成分，定義如下:

• 設一張圖
  $G$，其連通塊為
  $G$ 的極大 (maximal) 連通子圖 (subgraph)
• 若有一連通塊無邊 (即只有
  $1$ 節點)，則稱為顯然的 (trivial) 連通塊
• 若有一連通塊有邊，則稱為非顯然的 (nontrivial) 連通塊
• 若
  $G$ 只有一個連通塊，則稱
  $G$ 為連通圖

以下圖來說，有兩個連通塊

$\{a,b,c,d,e\}$ 與

$\{f\}$，其中

$\{f\}$ 為顯然連通塊

性質: 連通塊的數量關係

引理

假設

$G$ 有多個連通塊，每增加一條邊，則會減少

$0$ 或

$1$ 個連通塊；每減少一條邊則有可能增加

$0$ 或

$1$ 個連通塊

定理

設一張圖

$G$ 有

$n$ 個節點與

$k$ 條邊，則

$G$ 最少有

$n-k$ 個連通塊

證明

令

$G$ 有

$n$ 個節點與

$0$ 條邊，則

$G$ 有

$n$ 個連通塊。根據引理，每次加一條邊，最多可能減少

$1$ 個連通塊。因此設有

$k$ 條邊，則最少會有

$n-k$ 個連通塊

備註

當

$k=n-1$ 時，

$G$ 最少會有

$1$ 個連通塊。又根據連通性，

$G$ 只有

$1$ 連通塊時，

$G$ 為一張連通圖。因此如果

$G$ 是一張連通圖，則至少有

$n-1$ 條邊

強連通 Strongly Connected

• 在一張有向圖
  $D$ 中，若所有節點序對
  $(u,v)$ 都存在從
  $u$ 到
  $v$ 的路徑，則稱
  $D$ 是強連通圖
• 一張有向圖
  $D$ 的強連通塊，就是
  $D$ 的極大 (maximal) 強連通子圖，簡稱
  $\text{SCC}$

如下圖，任兩節點都有一條存在路徑可以走到彼此，因此這是強連通圖

我們在 Kosaraju 演算法會再深度討論該如何找出強連通塊

雙連通塊 Biconnected Component

雙連通塊是指一張圖中無關節點的極大子圖，又稱作 block

橋連通塊 Bridge-Connected Component

一張無向圖上，不會產生橋的極大連通塊，稱作橋連通塊

二分圖的連通性質

二分圖的定義在之前已經提過了，可以回去複習一下。之後在這篇會有更深的探討

複習 : 一張二分圖

$G$ 可以被分為兩個獨立集

$X,Y$

引理

任何奇數邊的閉行走都包含奇數環

定理 (Kőnig [1936]) : 判斷一張圖是否為二分圖

一張圖是二分圖若且為若不存在奇數環

證明

$\to$ : 令

$G$ 是二分圖。考慮每次在兩個獨立集之間交替行走，如果果要走回原來的獨立集就必須走偶數次才能走回來，因此

$G$ 沒有奇數環

$\leftarrow$ : 令

$G$ 是一張沒有奇數環的圖。我們可以把圖分成兩個獨立集。令

$u$ 為非顯然連通塊

$H$ 的節點，對於所有

$v\in V(H)$，令

$f(v)$ 為

$u,v$-路徑的最短長度。令

$X=\{v\in V(H):f(v)\text{ 是偶數}\}$、

$Y=\{v\in V(H):f(v)\text{ 是奇數}\}$。有一條在

$X$ 或

$Y$ 的邊

$(u,u^{\prime })$ 會造出一條

$u$ 到

$v$ 的閉奇數行走，分別由邊

$(u,v)$、

$(v,v^{\prime })$ 與

$(v^{\prime },u)$ 構成。但這違背了引理，因為奇數閉行走會產生奇數環。因此

$G$ 有奇數環的假設並不成立，換句話說，

$G$ 沒有奇數環

歐拉道路/迴路 Eulerian Trail/Circuit

若一張圖 (不見得是 simple) 存在一條閉道路能走過所有邊，則稱這一張圖是歐拉圖

• 一個歐拉道路為一條包含所有圖上的邊的道路
• 一個歐拉迴路為一條包含所有圖上的邊的迴路

引理

若

$G$ 中每個節點都有最少為

$2$ 的度數，則

$G$ 存在環

定理 : 判斷歐拉迴路的條件

一張圖

$G$ 存在歐拉迴路若且唯若只存在最多一個非顯然連通塊，且所有節點的度數皆為偶數

證明

$\to$ : 假設

$G$ 存在歐拉迴路，則對於每個節點都有兩條邊，一進一出，因此每節點都有偶數的度數。再者，兩條邊若要在同一條道路上，則必須在同一個非顯然連通塊，因此

$G$ 只會有一個非顯然連通塊

$\leftarrow$ : 假設

$G$ 存在最多一個非顯然連通塊，且所有節點的度數皆為偶數。我們對邊數

$m$ 做歸納法
Basis step :

$m=0$，僅有一節點必成立
Intuction step :

$m>0$。根據假設，非顯然連通塊的節點必為偶數。根據引理，非顯然連通塊存在環

$C$。令

$G^{\prime }=G-E(C)$。由於

$C$ 對

$G$ 中每個節點的度數貢獻都是

$0$ 或是

$2$，

$G^{\prime }$ 的每個節點度數依然為偶數。因

$G^{\prime }$ 中每個連通塊都是連通且少於

$m$ 條邊，我們套用歸納假設，所以

$G^{\prime }$ 的每個連通塊也存在歐拉迴路

漢米爾頓路徑/環 Hamiltonian Path/Cycle

• 一個漢米爾頓路徑為一條包含所有圖上的節點的路徑
• 一個漢米爾頓迴路為一條包含所有圖上的節點的迴路

如下圖，紅色箭頭會經過所有的節點，可以形成一個漢米爾頓迴路

樹 Tree

連通無環圖。對，定義就這麼短，我們會在這篇討論

有向無環圖 Directed Acyclic Graph

基本上把樹的定義從無向改成無向，就是有向無環圖，簡稱 dag。與樹不同，這裡沒有根與葉，取而代之的是源點 (source) 及匯點 (sink)

• 源點 : 入度為
  $0$ 的節點
• 匯點 : 出度為
  $0$ 的節點

有向無環圖在很多地方都見的到，像是動態規劃法本質上也是 dag，還有像是拓樸排序

Functional Graph (Successor Graph)

若一張有向圖的每個節點都只有一條出邊，則此圖稱為 functional graph

擷取自海大競程講義

毛毛蟲圖 Caterpillar Graph

若一棵樹存在一條路徑，使所有邊都與這條路徑相連，則稱此圖為毛毛蟲圖

PS: 放這個上來只是因為好玩

定理 : 判斷是不是毛毛蟲

一棵樹是毛毛蟲若且唯若不存在

$Y$ (如下圖)

證明

給一棵樹

$G$，我們刪去所有葉節點得到

$G^{\prime }$。因

$G^{\prime }$ 不存在所有

$G$ 的葉節點，因此

$G^{\prime }$ 的每個節點度數為

$3$ 若且唯若

$Y$ 存在於

$G$。因此，

$G^{\prime }$ 是一條路徑若且唯若

$G$ 是一張毛毛蟲圖。故得到一棵樹是毛毛蟲若且唯若不存在

$Y$

備註

有些名詞可能是參考自某些書，有些是自己亂翻譯，如果覺得讀的不太順，請見笑

---

參考資料

• D.B.West - Introduction to Graph Theory 2/e
• geeksforgeeks - Walks, Trails, Paths, Cycles and Circuits in Graph
• 維基百科 - Graph theory
• geeksforgeeks - Successor Graph
• 海大競程 - Special Graph & 0-1 BFS & 差分約束

---

上一篇: 基礎圖論 (一)
下一篇: 基礎圖論 (三)

ShanC 程式競賽筆記
作者: ShanC
更新: 2024/12/15