# 基礎圖論 (一): 圖的簡介與種類
圖論是一門專門研究圖的數學領域，不管在路網規劃、網路流的運算或是作業研究等等的問題上都有非常多應用。在電腦科學上，圖論不管在什麼子領域幾乎都會出現。當然，圖論問題在競賽型程式上也是常客，有時常搭配其他的概念一起出題，說實話還挺討厭的。但是，如果從數學的角度出發的話，就會發現有很多概念很值得深入研究

本篇主要是要從偏理論的角度出發，帶大家認識圖論的種種基本知識，所以不會有任何程式碼

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

## 什麼是一張圖?
這問題還得從一個 18 世紀的問題說起 - 「柯尼斯堡七橋問題」。柯尼斯堡位於現今的俄羅斯境內，但是在 18 世紀時，還算是在東普魯士的領土。這座城市很神奇，有一條普列戈利亞河將土地切成好幾塊，有七座橋 (現今有些被毀掉了，但那不是重點) 連接各土地，長以下這副德行:

<center>
<img src="https://hackmd.io/_uploads/SJLIjv-6A.png" style="margin: 0 auto; display: block">
</center>

<a href="https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg">
<p class="text-center">圖源: 維基百科</p>
</a>

那時的一個知名數學家歐拉 (其他翻譯: 尤拉) 就在想一個問題: 「是否可以每個橋梁都走遍，但是每座橋只能走一遍?」藉由著個問題，歐拉畫出了數學史上第一張圖(graph)，並且透過這個模型證明了這問是不可能的，因此就誕生了圖的定義

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

## 圖的定義 The Definition of Graphs
一張圖 (graph) 寫作 $G$，是一種三種數學物件所構成的集合，分別為節點(vertex) 集合 $V(G)$、邊 (edge) 集合 $E(G)$ 和節點與邊的**關係 (relation)** 所構成。一條邊的兩個節點被稱為終點 (endpoints)

ex: 在上面七橋問題的圖中
- 節點集合: $\left\{ v_1, v_2, v_3, v_4 \right\}$
- 邊集合: $\left\{ e_1, e_2, e_3, e_4, e_5, e_6, e_7 \right\}$
藉由觀察可發現 $e_1, e_2$ 有相同終點， $e_3, e_4$ 亦有相同終點

## 名詞解釋
### 有關節點的名詞
給定一個節點 $u$，則
- 相鄰 (adjacent): 若 $u$ 有與另一個節點 $v$ 用一條邊連起來，則稱 $u$ 與 $v$ 相鄰
- $u$ 的鄰居 (neighbors): 與 $u$ 有一條邊直接相連的節點 (有時是很多個)
- 度數 (degree): 一個節點所連出去的邊數。節點 $v$ 的度數可以寫作 $deg(v)$

### 有關邊的名詞
- 自環 (loop): 一條有相同終點的邊
- 多重邊 (multiple edge): 兩條或以上的邊有相同終點
如圖，$e_1$ 就是自環，終點$v_2, v_2$ 有多重邊$e_2$ 與 $e_3$

我們在圖論通常會想避免以上這兩個性質出現

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

## 圖的專有名詞

### 簡單圖 Simple Graph
如果一張圖沒有自環，也沒有多重邊則稱為簡單圖
在簡單圖上，有時為了方便會寫上邊的兩終點來代指此邊

如下圖 $G_1$ 就是一張簡單圖，其中 $e_1=v_1v_2$

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

### 補圖 Complement Graph
一張圖的補圖，就是指在原本的圖中沒有連接的邊，連起來所形成的一張圖，寫作 $\overline{G}$

上圖 $G_1$ 的補圖 $\overline{G_1}$ 長這樣

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

### 完全圖(Complete Graph)
在一張圖中選任兩節點 $v_i, v_j$ 都能找到一條邊連接，則稱完全圖。若此完全圖有 $n$ 個節點，則稱為 $K_n$

藉由上圖的 $G_1$ 與 $\overline{G_1}$，不難發現其實一張圖結合他的補圖，就會形成一張完全圖，也被稱為 $K_5$

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

### 空圖 Null Graph
一張圖節點集合與邊集合都是空的，則稱其為空圖 (就是什麼都沒有XD)。通常我們在討論圖論的時候，不會討論這個東東，但不知道為什麼這名詞偶爾會出現

### 子圖 Subgraph
給定一張圖，刪除一些節點、邊之後所得到的圖，就稱為子圖。如上圖 $G_1$ 就是 $K_5$ 的子圖，可以刪去一些邊得出來

### 團 Clique
給定一張圖，團就是指完全子圖 (complete subgraph)，就是一個圖的子圖是完全圖，稱為團。有時我們會加上一些形容詞去討論團
- 極大團 (maximal clique) ：無法再添加點的團
- 最大團 (maximum clique) ：點最多的團

如下圖，$\{v_6, v_7, v_8\}$ 所形成的就是一個極大團，$\{v_1, v_2, v_3\}$ 也是一個極大團，因為再加上其他的點也不會形成更大的團。此外，不難發現此圖的最大團是 $\{v_2, v_3, v_4, v_5\}$，沒有團比這再更大

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

註 : 尋找一張圖的最大團是 NP-complete 問題

### 同構 Isomorphism
給定兩張圖 $A$ 與 $B$，若我們可以找出一個 bijection $f: V(A)\rightarrow V(B)$ 使得 $u, v\in E(A)$ 若且唯若 $f(u), f(v)\in E(B)$，則稱為同構

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

## 圖論第一定理 The First Theorem of Graph Theory
### 定理
一張圖的度數總和等於兩倍的邊數，即 $\sum_{v\in V(G)} deg(v)=2|E|$

### 證明
每一條邊會對兩終點各貢獻一次度數，因此度數總和就是 $2|E|$

## 不同種類的圖

### 獨立集 Independent Set / Stable Set
一張圖之中，任選兩節點都沒有邊連接的節點集合，亦指圖的子集合中節點兩兩不相鄰

ex: 在下圖中，集合 $\{v_3, v_4\}$ 為一個獨立集、集合 $\{v_2, v_3\}$ 亦為獨立集；集合 $\{v_1, v_2, v_5\}$ 不為獨立集，因為存在邊 $v_2v_5$ 與 $v_1v_5$

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

### 二分圖 Bipartite Graph
一張圖為兩相互獨立的獨立集之聯集，則稱二分圖

下圖之中，藍色與紅色節點們明顯為兩個不同的獨立集

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

### 完全二分圖 Complete Bipartite Graph
一張簡單二分圖，構成圖的兩個獨立集彼此互相連通，則稱為完全二分圖
- 一張完全二分圖也被寫作 $K_{r, s}$，其中 $r, s$ 為兩獨立集各自的節點數量

下圖就是一個 $K_{2,3}$

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

### 有向圖 Directed Graph / Digraph
一張圖 (graph) 寫作 $G$，是一種三種數學物件所構成的集合，分別為節點(vertex) 集合 $V(G)$、邊 (edge) 集合 $E(G)$ 和節點與邊的**函數 (function)** 所構成。一條邊的兩個節點被稱為終點 (endpoints)，其中每條邊是一個有序點對，通常以箭頭表示如下圖

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

基本上就是改一下原本的定義而已，但有意思的是當把定義從 relation 改成 function 之後，你會 (也應該要) 發現這個定義會使我們方便去將許多概念或問題轉化成圖。也因此，圖是一個很棒的數學物件!!

此外，在無向圖有的性質，大多在有向圖也有，只是要修改一下定義，像是 :
- 每個節點掉的邊有出邊 (out-edge) 或入邊 (in-edge)
- 每個節點的度數分為出度 (out-degree) 與入度 (out-degree)

注 : 這邊說的函數是指對於任兩節點 $u, v$，可以對應到一條唯一的有向邊。也就是 $(u, v)\rightarrow e$

### 帶權圖 Weighted Graph
帶權圖就是在每條邊上賦予一個數字 (看狀況來定是哪種數)，無論有向圖或無向圖都可以加上這個性質。通常是來代表一張圖兩點間的距離，但是當然也會有例外

### 流量網路 Flow Network
一張路網圖 $N$ 是一張有向圖，其中 :
- 存在一個源點 (source vertex) $s$
- 存在一個與原點不同的匯點 (sink vertex) $t$
- 每條邊 $e$ 都有非負的容量 (capacity) $cap(e) \geq 0$
- 每條邊 $e$ 都有一個流量 (flow) $f(e)$

有關這種圖的討論，我們會在[最大流量-最小割定理](https://hackmd.io/@ShanC/maxflow-mincut-theorem)中詳細說明

**注意 : 有向帶權圖不是網路流量圖!! 兩者是不同的數學物件!! 若要轉換需要透過[一些定理](https://hackmd.io/@ShanC/bipartite-and-flow)才能達成**

### 平面圖 Planar Graph
一個無向圖的邊都沒有與其他邊產生任何交集，則稱為平面圖

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

這種圖的特別之處在於，一種透過「畫圖」的方式定義的圖。就算是同構，只要任何畫法都沒辦法畫成平面圖，那就不是平面圖。這種圖主要是用於討論圖著色與拓樸圖論，除非你想研究些怪怪的定理，否則一般演算法圖論用不太到

#### 面 Face (Region)
一張平面圖通常會有 bounded 的面與 unbounded 的面
- bounded 的面就是被圖圍起來的範圍
- unbounded 的面就是圖以外的範圍

#### 平面圖跟拓樸學之間的關聯
通常在討論這種圖的時候，還需要考慮這是畫在哪種曲面，比如說甜甜圈 (torus)。因為畫在不同的東西上，有可能使原本無法畫成平面圖的圖畫成平面圖。如下圖就是 $K_5$，原本沒辦法被畫成平面圖，但是在甜甜圈上面就可以!!

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

虛線代表透視，藍線與紅線代表原本會交在一起的兩條邊

### 有限自動機 Finite Automata (FA)
一個有限自動機 $M$ 是由五元素組成，也就是 $M=(K, \Sigma, \sigma, s, F)$，其中 :
- $K$ : $\{q_0, q_1, ..., q_{m-1}\}$，有限狀態的集合
- $\Sigma$ : 字母 (alphabet)
- $s$ : start state
- $F$ : final state 的集合
- $\sigma$ : $K\times\Sigma\rightarrow K$，轉移函數

嚴格上來說 FA 並不是圖論中的物件，但是通常我們在表示一台 FA 時，會以有向圖表示，且邊都帶一個字母。講這個只是想展示 function 這個定義為有向圖帶來的好處，這使有向圖變成一個很好的數學物件

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

<p>擷取自海大計算理論上課講義</p>
</center>

有時候我們也會畫一個圈圈裡面寫符號，這也是節點的一種表示方法

## 想一想
1. 在柯尼斯堡的七橋問題中，為什麼不能「在每座橋梁都只能走一遍的情況下，把每座橋梁都走遍」?

2. 假設在一家公司有四位員工(編號 1\~4)與四份待完成的工作(編號 1\~4)，每位員工有各自的專長。下圖顯示每位員工會的工作，像是員工 1 號會工作 1 號、員工 2 號會工作 1 號與工作 2 號...
公司規定每位員工最多只能作一份工作，如果今天老闆想要依照各自專長，分配這四份工作給四位員工，請問工作可以被分配完嗎?

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

$~$

3. 有哪些圖既是完全圖也是完全二分圖呢?

## 備註
圖論在歐拉解掉柯尼斯堡七橋問題之後，就沒什麼發展

----

## 參考資料

- D.B.West Introduction to Graph Theory 2/e
- [維基百科 - Graph theory](https://en.wikipedia.org/wiki/Graph_theory)
- [台師大演算法筆記 - complete graph](https://web.ntnu.edu.tw/~algo/CompleteGraph.html)
- [台師大演算法筆記 - graph](https://web.ntnu.edu.tw/~algo/Graph2.html)

----

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

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