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

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

## 走訪一張圖

### 行走 Walk
假設在一張圖上，我們可以隨便走，然後將走過的節點與邊都記錄下來，那應該會得到一個序列 $\langle v_0, e_1, v_1, \dots, e_k, v_k\rangle$，那麼這個序列我們就稱之為一條「行走」

下圖中，存在一行走 $\langle v_1, e_2, v_2, e_5, v_3, e_6, v_1, e_1, v_2, e_2, v_1\rangle$。由例子會發現，行走是允許重複的

<center>
<img src="https://hackmd.io/_uploads/H1oyc7B8xl.png" style="margin: 0 auto; display: block; width: 300px">
</center>

行走分成兩種:
- 開行走 (open walk) : 頭與尾的節點不相同
- 閉行走 (closed walk) : 頭與尾的節點相同

### 道路 Trail
如果一個行走並沒有重複的邊 (但可能有重複的節點)，則稱其為「道路」。如下圖，$\langle v_1, ~v_3, ~v_8, ~v_6, ~v_3, ~v_2, ~v_1\rangle$ 是一條道路。由於此圖是一張簡單圖，故可以不寫邊，因為對於任兩節點的邊都是固定的

<center>
<img src="https://hackmd.io/_uploads/HkTs2mr8el.png" style="margin: 0 auto; display: block; width: 300px">
</center>

如果一條道路經過所有邊，則稱為**歐拉道路 (Eulerian trail)**
道路分成兩種:
- 開道路 (open trail) : 頭與尾的節點不相同
- 閉道路 (closed trail) : 頭與尾的節點相同

### 迴路 Circuit
如果一條道路為閉道路，則稱其為「迴路」。一個迴路的邊不可重複，但是點可以重複。 如下圖中 $\langle v_1, v_2, v_3, v_4, v_5, v_3, v_1\rangle$ 為一條迴路

<center>
<img src="https://hackmd.io/_uploads/SJ8IR7BIgl.png" style="margin: 0 auto; display: block; width: 300px">
</center>

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

### 路徑 Path
一條道路節點不重複，則稱為「路徑」。如下圖中 $\langle v_5, v_4, v_3, v_1, v_2\rangle$ 為一條路徑

<center>
<img src="https://hackmd.io/_uploads/Skhg1VB8lx.png" style="margin: 0 auto; display: block; width: 300px">
</center>

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

### 環 Cycle
當遍歷一條路徑時，最後又走一條邊回到起點，則稱此為環。如下圖中 $\langle v_1, v_2, v_4, v_5, v_3, v_1\rangle$ 為一環

<center>
<img src="https://hackmd.io/_uploads/BkSsJ4rIxg.png" style="margin: 0 auto; display: block; width: 300px">
</center>

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

### 簡單整理

|分類|邊 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)

<center>
<img src="https://hackmd.io/_uploads/H1xavehVyg.png" style="margin: 0 auto; display: block; width: 300px">
</center>

以上圖為例，$a$ 與 $c$ 連通，但 $b$ 與 $e$ 不連通；$a$ 與 $c$ 連通，因此存在至少一條路徑

## 割 Cuts
前面討論連通，這篇來把圖切開來。這在[連通性與 Menger 定理](https://hackmd.io/@ShanC/Menger-Theorem)會討論到一點他們的性質
### 割點 Cut-vertex (Articulation vertex)
若移除一個節點可以把一個連通塊分成多個連通塊，則稱此節點為割點 (關節點)

### 點割 Vertex-cut
在一張圖 $G$ 中，若存在集合 $S\subseteq V(G)$ 使 $G-S$ 有多於一個連通塊，則 $S$ 是一個**點割 (vertex cut)**

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

### 邊割 Edge Cut
**邊割 (edge cut)** 是一個邊集，寫作 $[S, \bar{S}]$。其中， $S\subset V(G)$ 且 $\bar{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\}$ 為顯然連通塊

<center>
<img src="https://hackmd.io/_uploads/r1MdoWiQkg.png" style="margin: 0 auto; display: block; width: 300px">
</center>

### 性質: 連通塊的數量關係
#### 引理
假設 $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}$

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

<center>
<img src="https://hackmd.io/_uploads/HyjqKEBUgx.png" style="margin: 0 auto; display: block; width: 300px">
</center>

我們在 [Kosaraju 演算法](https://hackmd.io/@ShanC/Kosaraju)會再深度討論該如何找出強連通塊

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

<center>
<img src="https://hackmd.io/_uploads/B1uT4P8Ulg.png" style="margin: 0 auto; display: block; width: 300px">
</center>

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

<center>
<img src="https://hackmd.io/_uploads/BktRBD8Ugg.png" style="margin: 0 auto; display: block; width: 300px">
</center>

## 二分圖的連通性質
二分圖的定義在之前已經提過了，可以回去複習一下。之後在[這篇](https://hackmd.io/@ShanC/Bipartite-Graph-Recog)會有更深的探討

複習 : 一張二分圖 $G$ 可以被分為兩個獨立集 $X, Y$

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

### 定理 (Kőnig [1936]) : 判斷一張圖是否為二分圖
一張圖是二分圖若且為若不存在奇數環

#### 證明
$\rightarrow$ : 令 $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')$ 會造出一條 $u$ 到 $v$ 的閉奇數行走，分別由邊 $(u,v)$、$(v,v')$ 與 $(v', u)$ 構成。但這違背了引理，因為奇數閉行走會產生奇數環。因此 $G$ 有奇數環的假設並不成立，換句話說， $G$ 沒有奇數環

## 歐拉道路/迴路 Eulerian Trail/Circuit
若一張圖 (不見得是 simple) 存在一條閉道路**能走過所有邊**，則稱這一張圖是歐拉圖
- 一個歐拉道路為一條包含所有圖上的邊的道路
- 一個歐拉迴路為一條包含所有圖上的邊的迴路

### 引理
若 $G$ 中每個節點都有最少為 $2$ 的度數，則 $G$ 存在環

### 定理 : 判斷歐拉迴路的條件
一張圖 $G$ 存在歐拉迴路若且唯若只存在最多一個非顯然連通塊，且所有節點的度數皆為偶數

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

$\leftarrow$ : 假設 $G$ 存在最多一個非顯然連通塊，且所有節點的度數皆為偶數。我們對邊數 $m$ 做歸納法
Basis step : $m=0$，僅有一節點必成立
Intuction step : $m > 0$。根據假設，非顯然連通塊的節點必為偶數。根據引理，非顯然連通塊存在環 $C$。令 $G'=G - E(C)$。由於 $C$ 對 $G$ 中每個節點的度數貢獻都是 $0$ 或是 $2$，$G'$ 的每個節點度數依然為偶數。因 $G'$ 中每個連通塊都是連通且少於 $m$ 條邊，我們套用歸納假設，所以 $G'$ 的每個連通塊也存在歐拉迴路

## 漢米爾頓路徑/環 Hamiltonian Path/Cycle
- 一個漢米爾頓路徑為一條包含所有圖上的節點的路徑
- 一個漢米爾頓迴路為一條包含所有圖上的節點的迴路

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

<center>
<img src="https://hackmd.io/_uploads/HJSSuwI8lg.png" style="margin: 0 auto; display: block; width: 300px">
</center>

## 樹 Tree
連通無環圖。對，定義就這麼短，我們會在[這篇](https://hackmd.io/@ShanC/Trees-Basic-Properties)討論

<center>
<img src="https://hackmd.io/_uploads/rkUYmvlVxl.png" style="margin: 0 auto; display: block; width: 500px">
</center>

## 有向無環圖 Directed Acyclic Graph
基本上把樹的定義從無向改成無向，就是有向無環圖，簡稱 dag。與樹不同，這裡沒有根與葉，取而代之的是源點 (source) 及匯點 (sink)
- 源點 : 入度為 $0$ 的節點
- 匯點 : 出度為 $0$ 的節點

有向無環圖在很多地方都見的到，像是[動態規劃法](https://hackmd.io/@ShanC/Intro-to-DP)本質上也是 dag，還有像是[拓樸排序](https://hackmd.io/@ShanC/topological_sort)

## Functional Graph (Successor Graph)
若一張有向圖的每個節點都只有一條出邊，則此圖稱為 functional graph

<center>
<img src="https://hackmd.io/_uploads/ryLLHN48R.png" style="margin: 0 auto; display: block; width: 300px">

<p>擷取自海大競程講義</p>
</center>

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

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

<center>
<img src="https://hackmd.io/_uploads/rJiRyF88gx.png" style="margin: 0 auto; display: block; width: 300px">
</center>

### 定理 : 判斷是不是毛毛蟲
一棵樹是毛毛蟲若且唯若不存在 $Y$ (如下圖)

<center>
<img src="https://hackmd.io/_uploads/rkcYxK8Lxe.png" style="margin: 0 auto; display: block; width: 300px">
</center>

#### 證明
給一棵樹 $G$，我們刪去所有葉節點得到 $G'$。因 $G'$ 不存在所有 $G$ 的葉節點，因此 $G'$ 的每個節點度數為 $3$ 若且唯若 $Y$ 存在於 $G$。因此，$G'$ 是一條路徑若且唯若 $G$ 是一張毛毛蟲圖。故得到一棵樹是毛毛蟲若且唯若不存在 $Y$

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

----

## 參考資料

- D.B.West - Introduction to Graph Theory 2/e
- [geeksforgeeks - Walks, Trails, Paths, Cycles and Circuits in Graph](https://www.geeksforgeeks.org/walks-trails-paths-cycles-and-circuits-in-graph/)
- [維基百科 - Graph theory](https://en.wikipedia.org/wiki/Graph_theory)
- [geeksforgeeks - Successor Graph](https://www.geeksforgeeks.org/dsa/successor-graph/)
- [海大競程 - Special Graph & 0-1 BFS & 差分約束](https://hackmd.io/@LeeShoWhaodian/summer-advanced-graph#/)

----

> 上一篇: [基礎圖論 (一)](https://hackmd.io/@ShanC/basic-graph-theory-1)
> 下一篇: [基礎圖論 (三)](https://hackmd.io/@ShanC/basic-graph-theory-3)

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2024/12/15