基礎圖論: 圖的簡介與種類

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

本篇主要是要從偏理論的角度出發，帶同學認識圖論的種種基本知識。

什麼是一張圖?

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

圖源: 維基百科

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

↓
↓

圖的定義

一張圖(graph)寫作

G

，是一種三種集合所構成的集合，分別為節點(vertex)集合

V (G)

、邊(edge)集合

E (G)

和節點與線的關係(relation)所構成。一條邊的兩個節點被稱為終點(endpoints)。

舉例: 在上面七橋問題的圖中

節點集合:
${v_{1}, v_{2}, v_{3}, v_{4}}$
邊集合:
${e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}, e_{7}}$
藉由觀察可發現
$e_{1}, e_{2}$ 有相同終點，
$e_{3}, e_{4}$ 亦有相同終點

圖的種類

自環(loop): 一條有相同終點的邊
多重邊(multiple edge): 兩條或以上的邊有相同終點
如圖，
$e_{1}$ 就是自環，終點
$v_{2}, v_{2}$ 有多重邊
$e_{2}$ 與
$e_{3}$

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

簡單圖(Simple Graph)

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

G_{1}

就是一張簡單圖，其中

e_{1} = v_{1} v_{2}

補圖(Complement Graph)

一張圖的補圖，就是指在原本的圖中沒有連接的邊，連起來所形成的一張圖，寫作

\bar{G}

舉例: 上圖

G_{1}

的補圖

\bar{G_{1}}

長這樣

完全圖(Complete Graph)

在一張圖中選任兩節點

v_{i}, v_{j}

都能找到一條邊連接，則稱完全圖
藉由上圖的

G_{1}

與

\bar{G_{1}}

，不難發現其實一張圖結合他的補圖，就會形成一張完全圖

一張
$n$ 節點的完全圖會被寫作
$K_{n}$ ，因此下圖也被稱為
$K_{5}$

空圖 Null Graph

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

獨立集 Independent Set / Stable Set

一張圖之中，任選兩點都沒有邊連接的節點集合，亦指圖的子集合中結點兩兩不相鄰
舉例: 在下圖中，集合

{v_{3}, v_{4}}

為一個獨立集、集合

{v_{2}, v_{3}}

亦為獨立集
反例: 在下圖中，集合

{v_{1}, v_{2}, v_{5}}

不唯獨立集，因為存在邊

v_{2} v_{5}

與

v_{1} v_{5}

二分圖 Bipartite Graph

一張圖為兩相互獨立的獨立集之聯集，則稱二分圖
舉例: 下圖之中，藍色與紅色節點們明顯為兩個不同的獨立集

完全二分圖 Complete Bipartite Graph

一張簡單二分圖，構成圖的兩個獨立集彼此互相連通，則稱為完全二分圖

一張完全二分圖也被寫作
$K_{r, s}$ ，其中
$r, s$ 為兩獨立集各自的節點數量

舉例: 像是下圖就是一個

K_{2, 3}

以上是一些基礎且常在電腦科學領域看到的圖

圖論的子領域

圖論演算法 Graph Algorithms : 資工愛玩的東西
代數圖論 Algebratic graph theory : 會用到線性代數、群論的一個東西
極致圖論 Extermal graph theory
機率圖論 Probabilistic graph theory
拓樸圖論 Topological graph theory

想一想

在柯尼斯堡的七橋問題中，為什麼不能「在每座橋梁都只能走一遍的情況下，把每座橋梁都走遍」?
假設在一家公司有四位員工(編號 1~4)與四份待完成的工作(編號 1~4)，每位員工有各自的專長。下圖顯示每位員工會的工作，像是員工 1 號會工作 1 號、員工 2 號會工作 1 號與工作 2 號…
公司規定每位員工最多只能作一份工作，如果今天老闆想要依照各自專長，分配這四份工作給四位員工，請問工作可以被分配完嗎?

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

參考資料

D.B.West Introduction to Graph Theory 2/e
維基百科 - Graph theory

下一篇: 基礎圖論(二)

ShanC 程式競賽筆記
作者: ShanC
更新: 2024/9/17