# 基本圖論I (正在寫)

## 圖

## 名詞解析
1. 圖 (Graph)：圖是由點的集合和邊的集合組成的，可以表⽰為 G = (V, E)，其中 G 是圖，V 是點的集合，E 是邊的集合。
2. 頂點 (節點、Vertex、Node)：點，組成圖的元素集合，圖 G 的點集合⽤ V (G) 表⽰，點的數量稱為階 (order)。
3. 邊 (Edge)：點之間的關係，圖 G 的邊集合⽤ E(G) 表⽰。⽤ e($v_1$, $v_2$) 代表⼀條連接 $v_1$ 和 $v_2$ 的邊，若關係是雙向的，則稱作無向邊 (Undirected edge, Edge)，即e($v_1$, $v_2$) = e($v_2$, $v_1$)；若關係是單向的則稱為有向邊 (Directed edge)，或是弧 (Arc)，此時 e($v_1$, $v_2$) 代表⼀條連接 $v_1$ 和 $v_2$ 的單向邊。沒有特別限制的情況下，$v_1$ 可以等於 $v_2$，$v_1$ 到 $v_2$ 也不⼀定只有⼀條邊。
4. 相鄰 (Adjacent)：表達點之間的關係，$v_1$ 和 $v_2$ 相鄰若且為若存在 e($v_1$, $v_2$) 或 e($v_2$, $v_1$)。
8. 路徑 (Path)：點邊交錯的序列，$v_1$, $e_1$, $v_2$, ..., $e_{n-1}$ , $v_n$，可以當作從 $v_1$ ⾛到 $v_n$ 的⼀條路，其中所有的 $v_i$ ∈ V (G), $e_i$ ∈ E(G), $e_i$ = e($v_i$, $v_{i+1}$)。
9. 簡單路徑 (Simple Path)：點跟邊都不重複的⼀條路徑。
10. 環 (Cycle)：⼀條路徑，⾄少有⼀條邊，⽽且 $v_1$ = $v_n$。
11. 簡單環 (Simple Cycle)：除了起點 (終點) 之外點邊都不重複的環。
12. 度數 (Degree)：⼀個點 v 的度數代表該點點連接著多少邊，記做 deg(v)。
13. ⼊度 (In-Degree)：從其他點指向點 v 的有向邊數量，記做 $deg^+(v)$。
14. 出度 (Out-Degree)：從點 v 指向其他點的有向邊數量，記做 $deg^−(v)$

## 圖的名稱

### 基本三種
1. ⼦圖 Subgraph：如果兩個圖 G = (V, E), G′ = (V′, E′) 且 V′ ⊆ V, E′ ⊆ E，則 G′ 為 G的⼦圖。
2. 補圖 Compilment Graph：圖 G 的補圖 $G^c$，滿⾜ V ($G^c$) = V ($G^c) 且 e ∈ E(G) ↔ e ∈/E($G^c$)。
3. ⽣成樹 Spanning tree：若圖 T 是⼀棵樹，且 V (G) = V (T)，我們就稱 T 為圖 G 的⽣成樹。

### 常見圖
1. 簡單圖 (Simple Graph)⼀張不包含重邊 ($e_i$ = $e_j$ ) 或⾃環 (e($v_i$, $v_i$)) 的圖就稱為簡單圖。
2. 無向圖 (Undirected Graph)：所有的邊皆為無向邊的圖。
6. 有向圖 (Directed Graph)：所有的邊皆為有向邊的圖。
7. 混和圖 (Mixed Graph)：有有向邊也有無向邊的圖。
3. 連通圖 (Connected Graph)若⼀張圖 G 滿⾜任兩點 $v_i$, $v_j$ 都有⼀條路徑連接，則 G 為聯通圖。
4. 有向無環圖 (DAG)：有向無環圖，也就是⼀張沒有環的有向圖，DP 的狀態轉移關係構成的圖其實就是⼀張DAG。所以任何的 DP 都可以當成在⼀張 DAG 上找出 A 到 B 的最短 (⻑) 路⾛法。
5. ⼆分圖 (Bipartite Graph)如果⼀張無向圖 G 滿⾜，把點分成兩個集合 $V_1$, $V_2$，使得所有 e($v_i$, $v_j$ ) ∈ E(G) 且 $v_i$, $v_j$ 不在同⼀個集合，我們就稱 G 是⼆分圖。另外⼀種說法是，無向圖 G 是⼆分圖若且為若 G 可以進⾏⿊⽩染⾊ (把所有點染成⿊⽩並使得⿊⽩點不相鄰)。
6. 完全圖 (Complete Graph)如果無向圖 G 滿⾜任兩個點之間有邊，則稱 G 為完全圖。
7. 平⾯圖 (Plannar Graph)若⼀張圖 G 上可以畫在平⾯上且邊都不會相交，則稱 G 為平⾯圖。⼀個平⾯圖的邊會把平⾯切成數個不同的區塊，記做 F。
8. 樹 (Tree)如果⼀個無向的簡單圖 G 滿⾜ G 是沒有環的聯通圖，那我們就稱 G 為⼀顆樹 (Tree)。
9. 有向樹 (Directed Tree)在有向圖 G 中，如果存在⼀點 v 使得 $deg^+(v)$ = 0，且任何其他點 u 滿⾜ $deg^+(u)$ = 1 並且從 v 到 u 有且僅有⼀條簡單有向路徑連接，我們就稱 G 是⼀個以 v 為根的有向樹。

## 存圖的⽅法
存圖的⽅法會直接影響圖論演算法的複雜度，所以我們必須要思考怎麼樣有效率的存⼀張圖，而主要有下列方式(但其實大部分實作都只用到其中一種)。
### 邊陣列
- 就是用陣列把圖G每一條邊的$v_i$ , $e_i$記下來
- 搜尋兩點的時間複雜度就需要O(n)了
- 很少用
### 鄰接矩陣(Adjacent Matrix)
- n×n的矩陣，其中$A_{ij}$代表$v_i$是否指向$v_j$
- 空間複雜度$O(n^2)$，遍歷時間複雜度也為$O(n^2)$
- 由於時間複雜度太高，也不常用

### 鄰接串列(Adjacent List)
- n個串列，第i個串列存$v_i$所指向的邊(點)
- 可以用vector存取，也就是vector陣列或二維vector
- 空間複雜度O(V)，遍歷時間複雜度O(V)
- 最常使用的儲存方式
- 缺點是實作稍微複雜⼀點，插⼊或刪除邊的⽅式取決於所使⽤的資料結構。(PS用link list就會很麻煩)

# <a style = "color:#00DB00;"> 圖的遍歷 </a>
圖的遍歷問題分為四類：

- 遍歷完所有的邊而不能有重複，即所謂「歐拉路徑問題」（又名一筆畫問題）；
- 遍歷完所有的頂點而沒有重複，即所謂「哈密頓路徑問題」。
- 遍歷完所有的邊而可以有重複，即所謂「中國郵遞員問題」；
- 遍歷完所有的頂點而可以重複，即所謂「旅行推銷員問題」。

對於第一和第三類問題已經得到了完滿的解決，而第二和第四類問題則只得到了部分解決。第一類問題就是研究所謂的歐拉圖的性質，而第二類問題則是研究所謂的哈密頓圖的性質。

而在演算法的部分主要就兩種DFS以及BFS。

## DFS

## BFS

# <a style = "color:#00DB00;"> 經典例子 </a>

## Topological sort 拓樸排序

## 最短路徑

## MST最小生成樹

## 雙連通

## 強連通

## 歐拉回路

###### tags: `演算法`
{%hackmd aPqG0f7uS3CSdeXvHSYQKQ %}