這篇文章主要是為了之後的文章做鋪墊,
原本是想說跟特殊的圖論算法文章一起發的。
元組
元組(tuple)是一種數學結構:
- 有序元組通常以小括號表示 $(a_0, a_1, a_2, …)$
- 無序元組通常以大括號表示 $\{a_0, a_1, a_2, …\}$
另外,如果一個元組有 $k$ 個元素,我們會稱為 k 元組(k-tuple),例如:$(1,2)$ 為二元組。
有序元組的元素「順序」不能改變,如果改變,則不為同樣的有序元組,例如:
$$
(1, 2) \neq (2, 1)
$$
無序元組的元素「順序」能夠改變,改變後仍為同樣的元組,例如:
$$
\{1, 2\} = \{2, 1\}
$$
元組跟集合最大的兩點不同是:
- 元組允許重複元素(這個性質跟多重集一樣),例如:$(1, 2, 2) \neq (1, 2)$
- 元組必為有限個元素,集合允許無限個元素
包含 $n$ 個有限元素的 多重集(multiset)是一個無序 n 元組
二元組又稱為對(pair),對學生來說,最常見的有序對可能是平面座標上的點 $(x, y)$
笛卡兒積
笛卡兒積(Cartesian product)也被稱為卡氏積,定義是:
$$
A \times B = \{(a, b) :|: a \in A ,; b \in B \}
$$
也就是將兩個集合的元素構成對,再包進一個集合中,例子:
$$
\{\text{a}, \text{b}\} \times \{1, 2, 3\} = \{(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)\}
$$
圖的定義
圖(graph)是由點(vertex)的集合、邊(edge)的集合構成的有序對:
$$
G = (V, E)
$$
其中:
- 圖表示為 $G$
- 點集表示為 $V$ 是構成點的集合
- 邊集表示為 $E$ 是構成邊的多重集
若邊集元素皆唯一(無重邊)則有 $E \subseteq V \times V$ 的關係
圖的例子:
$$
G = (V, E), ;\text{where}; V = \{a,b,c\},; E=\{(a,a), (a,b)\}
$$
通常會畫成:
上圖為不連通的圖。
圖若連通(connected)則沒有斷開。更精確地說,任兩點皆存在一條路徑抵達另外一點。
設置權重
可以為點或邊設置權重,數學上會使用函數處理:
- 定義「點權重」為函數 $W_v(u)$ 帶入點 $u$ 可得該點權重。
- 定義「邊權重」為函數 $W_e(u, v)$ 帶入邊 $(u, v)$ 可得該邊權重。
這邊有一個很彆扭的地方是,數學上常常將元組「直接拆開」作為函數輸入
比方說,函數 $f(x, y) = \sqrt{x^2 + y^2}$ 可以代入 $(2, 3)$ 作為參數
通常不會保留其原本的結構(但偶爾會)即寫為 $f((x, y))$ 或 $f(p)$
迴圈與環路
迴圈(loop)是指有自己到自己的邊:
環路(cycle)是圖上可以走一圈到自己:
若圖有負環路(negative cycle)即環路上的所有邊權重和為負,則最短路徑問題的正解為無限小(不存在);因為從任一點出發抵達負環路後,會持續在環路中繞,權重和會越來越小。
可是由於演算法設計的關係,有可能可以解出負環路圖的最短路徑解,但不為最佳解。
有向與無向
有向圖(directed graph)是指圖上的邊是單行道、單向通行:
無向圖(undirected graph)是指圖上的邊雙向通行:
無論有向無向,邊集 $E$ 元素皆用小括號表示。無向圖的情況下,寫 $(a, b)$ 跟 $(b, a)$ 的意義是相同的,儘管以大括號表示會更加貼近它的意義,但習慣上不太會這樣表示。
點的度數
無向圖的度數(degree)是指點有多少邊與之相聯,通常點 $u$ 的度數表示為 $deg(u)$
有向圖分成:
- 入度數(in-degree)而點 $u$ 的度數表示為 $id(u)$
- 出度數(out-degree)而點 $u$ 的出度數表示為 $od(u)$
圖的縮寫
這裡列出一些常見的圖縮寫:
名稱 | 縮寫 | 簡述 | 例子 |
---|---|---|---|
完全圖(complete graph) | $K_n$ | 每點都跟其他點恰一邊相連 | $K_5$ |
環圖(cycle graph) | $C_n$ | 點與邊數相同,且每點的度數皆為 2 | $C_5$ |
完全雙分圖(complete bipartite graph) | $K_{m,n}$ | 點分成兩組,每點都跟另一組所有點恰一邊相連 | $K_{2,3}$ |
立方圖(cubical graph) | $Q_n$ | 立方形 | $Q_3$ |
有向完全圖(complete graph) | $K^*_n$ | 同 $K_n$ 只是邊有方向 | $K^*_5$ |
輪圖(wheel graph) | $W_n$ | 同 $C_n$ 只是多放一點跟所有點相連 | $W_5$ |
圖的表示
圖在電腦中的表示大致上有兩種,一種基於陣列,另一種基於串列。
鄰接矩陣
鄰接矩陣(adjacency matrix)用點跟點的關係做標記:
有權重時,為了搭配演算法,常常會將沒有連接的邊,設為 0x7fffffff
即 4 bytes 的整數最大值,其他的邊會放入該邊權重。
1 | // 沒有連接權重無限大 |
如果沒有權重,通常會將沒有連接的邊設為 0
做標記。
1 | // 鄰接矩陣 |
還有一種比較少見的接合矩陣(incidence matrix)是以點跟邊構成的表示法。
鄰接串列
鄰接矩陣的一個問題是當 $|E| << |V|^2$ 時,稱為稀疏圖(sparse graph),很浪費空間,另外在演算法中,搜索邊還要翻找一大堆 0
會浪費時間。故此,鄰接串列(adjacency list)只記錄存在的邊,既可節省空間,也可省去一些常數時間。
1 | // 鄰接串列 |