基礎圖論: 圖的簡介與種類
圖論是一門專門研究圖的數學領域,不管在路網規劃、網路流的運算或是作業研究等等的問題上都有非常多應用。在電腦科學上,圖論不管在什麼子領域幾乎都會出現。當然,圖論問題在競賽型程式上也是常客,有時常搭配其他的概念一起出題,說實話還挺討厭的。但是,如果從數學的角度出發的話,就會發現有很多概念很值得深入研究。
本篇主要是要從偏理論的角度出發,帶同學認識圖論的種種基本知識。
什麼是一張圖?
這問題還得從一個18世紀的問題說起-柯尼斯堡七橋問題。柯尼斯堡位於現今的俄羅斯境內,但是在18世紀時,還算是在東普魯士的領土。這座城市很神奇,有一條普列戈利亞河將土地切成好幾塊,有七座橋(現今有些被毀掉了,但那不是重點)連接各土地,長以下這副德行:
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
圖源: 維基百科
那時的一個知名數學家歐拉(其他翻譯: 尤拉)就在想一個問題: 「是否可以每個橋梁都走遍,但是每座橋只能走一遍?」藉由著個問題,歐拉畫出了數學史上第一張圖(graph),並且透過這個模型證明了這問是不可能的,因此就誕生了圖的定義。
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
↓
↓
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
圖的定義
一張圖(graph)寫作 ,是一種三種集合所構成的集合,分別為節點(vertex)集合 、邊(edge)集合 和節點與線的關係(relation)所構成。一條邊的兩個節點被稱為終點(endpoints)。
舉例: 在上面七橋問題的圖中
- 節點集合:
- 邊集合:
藉由觀察可發現 有相同終點, 亦有相同終點
圖的種類
- 自環(loop): 一條有相同終點的邊
- 多重邊(multiple edge): 兩條或以上的邊有相同終點
如圖, 就是自環,終點 有多重邊 與
我們在圖論通常會想避免以上這兩個性質出現
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
簡單圖(Simple Graph)
如果一張圖沒有自環,也沒有多重邊則稱為簡單圖
在簡單圖上,有時為了方便會寫上邊的兩終點來代指此邊
舉例: 如下圖 就是一張簡單圖,其中
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
補圖(Complement Graph)
一張圖的補圖,就是指在原本的圖中沒有連接的邊,連起來所形成的一張圖,寫作
舉例: 上圖 的補圖 長這樣
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
完全圖(Complete Graph)
在一張圖中選任兩節點 都能找到一條邊連接,則稱完全圖
藉由上圖的 與 ,不難發現其實一張圖結合他的補圖,就會形成一張完全圖
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
空圖 Null Graph
一張圖節點集合與邊集合都是空的,則稱其為空圖(就是什麼都沒有XD)
通常我們在討論圖論的時候,不會討論這個東東,但不知道為什麼這名詞偶爾會出現
獨立集 Independent Set / Stable Set
一張圖之中,任選兩點都沒有邊連接的節點集合,亦指圖的子集合中結點兩兩不相鄰
舉例: 在下圖中,集合 為一個獨立集、集合 亦為獨立集
反例: 在下圖中,集合 不唯獨立集,因為存在邊 與
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
二分圖 Bipartite Graph
一張圖為兩相互獨立的獨立集之聯集,則稱二分圖
舉例: 下圖之中,藍色與紅色節點們明顯為兩個不同的獨立集
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
完全二分圖 Complete Bipartite Graph
一張簡單二分圖,構成圖的兩個獨立集彼此互相連通,則稱為完全二分圖
- 一張完全二分圖也被寫作 ,其中 為兩獨立集各自的節點數量
舉例: 像是下圖就是一個
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
以上是一些基礎且常在電腦科學領域看到的圖
圖論的子領域
- 圖論演算法 Graph Algorithms : 資工愛玩的東西
- 代數圖論 Algebratic graph theory : 會用到線性代數、群論的一個東西
- 極致圖論 Extermal graph theory
- 機率圖論 Probabilistic graph theory
- 拓樸圖論 Topological graph theory
想一想
-
在柯尼斯堡的七橋問題中,為什麼不能「在每座橋梁都只能走一遍的情況下,把每座橋梁都走遍」?
-
假設在一家公司有四位員工(編號 1~4)與四份待完成的工作(編號 1~4),每位員工有各自的專長。下圖顯示每位員工會的工作,像是員工 1 號會工作 1 號、員工 2 號會工作 1 號與工作 2 號…
公司規定每位員工最多只能作一份工作,如果今天老闆想要依照各自專長,分配這四份工作給四位員工,請問工作可以被分配完嗎?
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
- 有哪些圖既是完全圖也是完全二分圖呢?
參考資料
下一篇: 基礎圖論(二)
ShanC 程式競賽筆記
作者: ShanC
更新: 2024/9/17