圖與圖模型

---

---

上一部分介紹了推理、證明和解決問題的不同工具。在本部分中，我們將學習構成許多現實生活問題基礎的離散結構。

我們將介紹的兩種離散結構是圖和樹。圖是由稱為節點或頂點的點集以及由稱為邊的線集相互連線而成的。圖的研究，或圖論，是數學、工程和計算機科學領域許多學科的重要組成部分。

什麼是圖？

定義 − 圖（表示為$G = (V, E)$）由非空頂點集或節點集 V 和邊集 E 組成。

示例 − 讓我們考慮一個圖$G = (V, E)$，其中$V = \lbrace a, b, c, d \rbrace$，而$E = \lbrace \lbrace a, b \rbrace, \lbrace a, c \rbrace, \lbrace b, c \rbrace, \lbrace c, d \rbrace \rbrace$

頂點的度 − 圖 G 的頂點 V 的度（用 deg (V) 表示）是與頂點 V 相連的邊的數量。

偶數頂點和奇數頂點 − 如果頂點的度為偶數，則該頂點稱為偶數頂點；如果頂點的度為奇數，則該頂點稱為奇數頂點。

圖的度 − 圖的度是該圖中最大的頂點度。對於上述圖，圖的度為 3。

握手引理 − 在一個圖中，所有頂點的度之和等於邊數的兩倍。

圖的型別

在下一節中，我們將學習不同型別的圖。

空圖

空圖沒有邊。n 個頂點的空圖用 $N_n$ 表示。

簡單圖

如果圖是無向的並且不包含任何環或多重邊，則該圖稱為簡單圖/嚴格圖。

多重圖

如果允許圖中同一組頂點之間存在多條邊，則稱其為多重圖。換句話說，它是一個至少包含一個環或多重邊的圖。

有向圖和無向圖

如果邊集由有序頂點對組成，則圖 $G = (V, E)$ 稱為有向圖；如果邊集由無序頂點對組成，則圖稱為無向圖。

連通圖和非連通圖

如果圖的任意兩個頂點都由一條路徑連線，則該圖是連通的；如果圖中至少有兩個頂點不能由路徑連線，則該圖是非連通的。如果圖 G 是非連通的，則 G 的每個最大連通子圖都稱為圖 G 的連通分量。

正則圖

如果圖的所有頂點都具有相同的度，則該圖是正則圖。在度為 r 的正則圖 G 中，G 的每個頂點的度都為 r。

完全圖

如果每對頂點都恰好由一條邊連線，則該圖稱為完全圖。具有 n 個頂點的完全圖用 $K_n$ 表示。

環圖

如果一個圖由一個單一的環組成，則它被稱為環圖。具有 n 個頂點的環圖用 $C_n$ 表示。

二分圖

如果圖 G 的頂點集可以分成兩個不相交的集合 $V_1$ 和 $V_2$，以使圖中的每條邊都連線 $V_1$ 中的一個頂點和 $V_2$ 中的一個頂點，並且 G 中沒有邊連線 $V_1$ 中的兩個頂點或 $V_2$ 中的兩個頂點，則圖 G 稱為二分圖。

完全二分圖

完全二分圖是一個二分圖，其中第一組中的每個頂點都與第二組中的每個頂點連線。完全二分圖用 $K_{x,y}$ 表示，其中圖 G 在第一組中有 x 個頂點，在第二組中有 y 個頂點。

圖的表示

主要有兩種表示圖的方法：

• 鄰接矩陣
• 鄰接表

鄰接矩陣

鄰接矩陣 $A[V][V]$ 是一個大小為 $V \times V$ 的二維陣列，其中 V 是無向圖中頂點的數量。如果 $V_x$ 和 $V_y$ 之間存在一條邊，則 $A[V_x][V_y]=1$ 且 $A[V_y][V_x]=1$，否則值為零。對於有向圖，如果 $V_x$ 和 $V_y$ 之間存在一條邊，則 $A[V_x][V_y]=1$，否則值為零。

無向圖的鄰接矩陣

讓我們考慮以下無向圖並構造其鄰接矩陣：

上述無向圖的鄰接矩陣將是：

有向圖的鄰接矩陣

讓我們考慮以下有向圖並構造其鄰接矩陣：

上述有向圖的鄰接矩陣將是：

鄰接表

在鄰接表中，一個連結列表陣列 $(A[V])$ 用於表示具有 V 個頂點的圖 G。條目 $A[V_x]$ 表示與第 Vx 個頂點相鄰的頂點的連結列表。無向圖的鄰接表如下圖所示：

平面圖與非平面圖

平面圖 − 如果圖 $G$ 可以繪製在平面上而不出現任何邊交叉，則稱其為平面圖。如果我們在平面上繪製圖而不出現邊交叉，則稱為將圖嵌入平面。

非平面圖 − 如果圖不能在平面上繪製而沒有圖邊交叉，則該圖是非平面圖。

同構

如果兩個圖 G 和 H 包含相同數量的以相同方式連線的頂點，則它們稱為同構圖（用 $G \cong H$ 表示）。

檢查非同構比檢查同構更容易。如果出現以下任何條件，則兩個圖是非同構的：

• 連通分量的數量不同
• 頂點集基數不同
• 邊集基數不同
• 度數序列不同

示例

以下圖是同構的：

同態

從圖 $G$ 到圖 $H$ 的同態是一個對映（可能不是雙射對映）$h: G \rightarrow H$，使得 − $(x, y) \in E(G) \rightarrow (h(x), h(y)) \in E(H)$。它將圖 $G$ 的相鄰頂點對映到圖 $H$ 的相鄰頂點。

同態的性質

• 如果同態是雙射對映，則它是同構。

• 同態總是保持圖的邊和連通性。

• 同態的組合也是同態。

• 確定是否存在另一個圖的任何同態圖是一個 NP 完全問題。

尤拉圖

如果存在一個包含圖 G 的每條邊的閉合軌跡，則連通圖 $G$ 稱為尤拉圖。尤拉路徑是一條恰好使用圖的每條邊一次的路徑。尤拉路徑的起點和終點不同。

歐拉回路是一個恰好使用圖的每條邊一次的迴路。歐拉回路總是從同一個頂點開始和結束。連通圖 $G$ 是尤拉圖當且僅當 $G$ 的所有頂點都是偶數度，並且連通圖 $G$ 是尤拉圖當且僅當它的邊集可以分解成環。

上圖是一個尤拉圖，因為“a 1 b 2 c 3 d 4 e 5 c 6 f 7 g”包含了圖的所有邊。

哈密頓圖

如果存在一個包含 G 的每個頂點的環，則連通圖 $G$ 稱為哈密頓圖，並且該環稱為哈密頓環。圖 G 中的哈密頓行走是一條恰好經過每個頂點一次的行走。

如果 G 是一個具有 n 個頂點的簡單圖，其中 $n \geq 3$，如果對於每個頂點 v，$deg(v) \geq \frac{n}{2}$，則圖 G 是哈密頓圖。這稱為狄拉克定理。

如果 G 是一個具有 n 個頂點的簡單圖，其中 $n \geq 2$，如果對於每對不相鄰的頂點 x 和 y，$deg(x) + deg(y) \geq n$，則圖 G 是哈密頓圖。這稱為奧爾定理。