離散數學/圖論

簡介

圖是一種數學方式，用於表示“網路”的概念。

網路具有由線連線的點。在圖中，我們為這些點和線賦予了特殊的名稱。我們稱這些點為頂點（有時也稱為節點），線為邊。

這是一個示例圖。邊為紅色，頂點為黑色。

在該圖中，$v_{1},v_{2},v_{3},v_{4}$ 是頂點，$e_{1},e_{2},e_{3},e_{4},e_{5}$ 是邊。

圖的定義

關於圖，有幾種大致等效的定義。集合論常被用來定義圖。最常見的是，圖 $G$ 被定義為一個有序對 $G=(V,E)$，其中 $V=\{v_{1},\ldots ,v_{n}\}$ 被稱為圖的頂點集，$E=\{e_{1},\ldots ,e_{m}\}\subset \{\{x,y\}|x,y\in V\}$ 被稱為圖的邊集。給定一個圖 $G$，我們通常用 $V(G)$ 表示頂點集，用 $E(G)$ 表示邊集。為了視覺化上述定義的圖，我們畫出 $n$ 個點，對應頂點 $v_{1},\ldots ,v_{n}$。然後，對於所有 $i,j\in \{1,\ldots ,n\}$，我們將在對應頂點 $v_{i},v_{j}$ 的點之間畫一條線，當且僅當存在一條邊 $\{v_{i},v_{j}\}\in E$。請注意，點的放置通常並不重要；許多不同的圖片可以表示同一個圖。

或者，以上面的圖為例，我們可以將圖定義為一個有序三元組 $G=(V,E,f)$

• 一組頂點，通常稱為 V
• 一組邊，通常稱為 E
• 一個關係 $f:E\rightarrow \{\{x,y\}|x,y\in V\}$，它將每條邊對映到一組端點，稱為邊端點關係。我們說一條邊 $e\in E$ 與一個頂點 $v\in V$ 相鄰，當且僅當 $v\in f(e)$。

在上面的例子中，

• V={v₁, v₂, v₃, v₄}
• E={e₁, e₂, e₃, e₄, e₅}
• f 使得 e₁ 對映到 {v₁, v₂}，e₂ 對映到 {v₁, v₃}，e₃ 對映到 {v₁, v₄}，e₄ 對映到 {v₂, v₄}，e₅ 對映到 {v₃, v₄}。

如果 $f$ 不是單射的——也就是說，如果 $\exists e,e'\in E$ 使得 $e\neq e',f(e)=f(e')$——那麼我們說 $G$ 是一個多重圖，我們將任何這樣的邊 $e,e'\in E$ 稱為多重邊。此外，我們稱邊 $e\in E$ 使得 $|f(e)|=1$ 為環。沒有多重邊或環的圖稱為簡單圖。

理論上，圖也可以是無限的，因此我們對集合 V 和 E 沒有限制。這裡我們不會討論無限圖。

方向、權重和流量

我們將有向圖定義為一個圖，使得 $f$ 對映到有序對集合 $\{(x,y)|x,y\in V\}$ 而不是對映到二元組集合的族 $\{\{x,y\}|x,y\in V\}$。我們可以將邊 $e\in E$ 視為從 $x$ 指向 $y$，使得 $f(e)=(x,y)$。因此，可以說 $x$ 是邊 $e$ 的尾，而 $y$ 是頭。不過，這只是圖論符號中的一種怪癖。我們也可以將 $x$ 視為頭，$y$ 視為尾。為了表示有向圖，我們可以按照上述描述和圖形進行繪製，但將箭頭放在每個邊上以表示其方向。

一般來說，圖 $G$ 上的權重是某個函式 $c:E(G)\rightarrow \mathbb {R}$。

流 $(G,c)$ 是一個有向圖 $G=(V,E,f)$ 與一個權重函式配對，使得“流入”任何頂點的權重與“流出”該頂點的權重相同。為了更正式地表達這一點，定義集合

• $f^{+}(v)=\{e\in E(G)|f(e)=(v,x),x\in V(G)\},\;\forall v\in V(G)$
• $f^{-}(v)=\{e\in E(G)|f(e)=(x,v),x\in V(G)\},\;\forall v\in V(G)$

然後，正式地說，我們對權重函式的要求是 $\sum _{e\in f^{+}(v)}c(e)=\sum _{e\in f^{-}(v)}c(e),\;\forall v\in V(G).$

代數圖論

雖然在討論圖時經常使用集合論，但其他方法可以簡化某些操作。可以使用鄰接矩陣 $A$ 來定義集合，其中元素 $a_{i,j}$ 為 1，如果頂點 i 和頂點 j 之間存在邊，否則為 0。

特殊圖

6 個頂點的完全圖

在圖論中，一些圖出現的頻率很高，因此值得特別提及。其中一種圖是 n 個頂點的完全圖，通常用 K_n 表示。這個圖由 n 個頂點組成，每個頂點都與其他每個頂點相連，每對頂點之間恰好有一條邊。另一種圖是迴圈圖，它有n 個頂點（n 至少為 3）。這個圖用 C_n 表示，定義為 V := {1,2,..,n} 和 E := {{1,2},{2,3}, ..., {n-1,n},{n,1}}。更簡單的是空圖，它有n 個頂點，沒有邊！注意 N₁ = K₁ 且 C₃ = K₃。

一些術語

如果兩個頂點之間存在邊，則稱它們相鄰。“關聯”一詞有兩個含義

• 如果v 是e 的端點，則稱邊e 與頂點v 關聯。
• 如果兩條邊都與同一個頂點關聯，則稱它們也彼此關聯。

如果從G 的頂點集到H 的頂點集存在一個一對一函式（或者，如果你願意，則存在頂點集之間的一一對應），使得G 中的兩個頂點相鄰當且僅當它們在H 中的像相鄰，則稱兩個圖G 和H 是同構的。（從技術上講，邊的重數也必須保留，但我們的定義足以用於簡單圖。）

子圖

生成子圖

子圖是一個類似於子集的概念。子圖具有頂點集 V 的子集、邊集 E 的子集，並且更大圖中每條邊的端點在子圖中具有相同的邊。一個

子圖 $H$ 由頂點集合 {$a,b,c,...$}$\in H$ 生成，如果 $H$ 的邊集包含 $G$ 的邊集中的所有邊，這些邊連線 $H=${$a,b,c,...$} 中的頂點。

路徑 是邊序列 $<e_{1},...,e_{N}>$，使得對於從 1 到 N-1 的所有 i，e_i 與 e_i+1 相鄰。如果存在連線兩個頂點的路徑，則稱這兩個頂點是相連的。

樹和二部圖

樹 是一個圖，它 (i) 是連通的，並且 (ii) 沒有環。等效地，樹是一個具有恰好 $n-1$ 條邊的連通圖，其中樹中存在 $n$ 個節點。

二部圖 是一個圖，其節點可以劃分為兩個不相交的集合 U 和 W，使得圖中的每條邊都與 U 中的一個節點和 W 中的一個節點相鄰。樹是一個二部圖。

完全二部圖 是一個二部圖，其中 U 中的每個節點都與 W 中的每個節點相連；U 有 $n$ 個頂點，V 有 $m$ 個頂點的完全二部圖表示為 $K_{n,m}$。

相鄰、關聯、端點頂點

自環、平行邊、頂點度

懸掛頂點：度數為一的頂點 “懸掛頂點” 孤立頂點：度數為零的頂點 “孤立頂點”

哈密頓路徑和尤拉路徑

哈密頓迴路：哈密頓迴路得名於第一個研究旅行商問題的威廉·哈密頓爵士。哈密頓迴路是訪問每個頂點一次且僅一次的路徑，即它是一個行走，其中沒有重複邊（軌跡），因此是一個不重複頂點的軌跡（路徑）。注意它也是一個迴路，最後一個頂點連線到第一個頂點。

如果可能遍歷每條邊一次且僅一次，則稱該圖為尤拉圖，即它沒有奇數頂點，或者它有偶數個奇數頂點（半尤拉圖）。這對哥尼斯堡問題有影響。可以更容易地將其想象為是否可以用鉛筆追蹤圖的邊而不抬起鉛筆或重複任何線條。

平面圖

平面圖 是一個無向圖，它可以以這樣一種方式繪製在平面上或球面上，使得沒有兩條邊交叉，其中邊 $e=(u,v)$ 被繪製為從 u 到 v 的連續曲線（它不一定是直線）。

庫拉托夫斯基證明了關於平面圖的一個 remarkable 事實：一個圖是平面的當且僅當它不包含同胚於 $K_{5}$ 或者 $K_{3,3}$ 的子圖。(兩個圖被稱為同胚的，如果我們可以將每個圖的某些分量縮減為單個節點，並最終得到相同的圖。非正式地說，這意味著非平面性是由兩件事造成的——即具有 $K_{5}$ 或 $K_{3,3}$ 的結構）。

圖著色

一個圖被稱為平面的，如果它可以在平面上繪製，使得沒有邊相互交叉，當然除了在頂點處相遇之外。

每學期，某大學的排課辦公室必須為每場期末考試分配一個時間段。這並不容易，因為有些學生正在上幾門有期末考試的課，而且一個學生在一個特定時間段內只能參加一次考試。排課辦公室希望避免所有衝突，但要儘量縮短考試時間。

我們可以將這個排課問題改寫成關於圖頂點著色的問題。為每門有期末考試的課程建立一個頂點。如果某個學生正在上這兩門課，就在兩個頂點之間畫一條邊。例如，排課圖可能看起來像這樣：接下來，用顏色識別每個時間段。例如，星期一上午是紅色，星期一下午是藍色，星期二上午是綠色，等等。

將考試分配到時間段現在等同於對相應的頂點著色。主要約束是相鄰的頂點必須得到不同的顏色；否則，某個學生將在同一時間參加兩場考試。此外，為了縮短考試時間，我們應該嘗試使用盡可能少的不同顏色來對所有頂點著色。對於我們的示例圖，三種顏色就足夠了：紅色、綠色、藍色。

著色對應於在星期一上午（紅色）安排一場期末考試，在星期一下午（藍色）安排兩場期末考試，在星期二上午（綠色）安排兩場期末考試……

K 著色

許多其他資源分配問題都歸結為對某些圖進行著色。一般來說，一個圖 G 是 k 可著色的，如果每個頂點可以被分配 k 種顏色中的一種，使得相鄰的頂點得到不同的顏色。最小的足夠顏色數稱為 G 的色數。圖的色數通常很難計算，但下面的定理提供了一個上限。

定理 1. 最大度數不超過 k 的圖是 (k + 1) 可著色的。

---

證明。我們使用歸納法來證明圖中頂點的數量，我們用 n 來表示。令 P(n) 表示一個 n 頂點圖，其最大度數不超過 k，是 (k + 1) 可著色的。一個 1 頂點圖的最大度數為 0，並且是 1 可著色的，所以 P(1) 為真。

現在假設 P(n) 為真，並令 G 為一個 (n + 1) 頂點圖，其最大度數不超過 k。移除一個頂點 v，留下一個 n 頂點圖 G。G 的最大度數不超過 k，因此根據我們的假設 P(n)，G 是 (k + 1) 可著色的。現在添加回頂點 v。我們可以給 v 分配一個與所有相鄰頂點不同的顏色，因為 v 的度數不超過 k，並且有 k + 1 種顏色可用。因此，G 是 (k + 1) 可著色的。該定理由歸納法得出。

加權圖

一個加權圖將一個標籤（權重）與圖中的每條邊相關聯。權重通常是實數，並且通常表示與邊相關的“成本”，無論是就建模的實體而言，還是就正在解決的最佳化問題而言。