Try   HackMD

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

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

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

什麼是一張圖?

這問題還得從一個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)寫作

G,是一種三種集合所構成的集合,分別為節點(vertex)集合
V(G)
、邊(edge)集合
E(G)
和節點與線的關係(relation)所構成。一條邊的兩個節點被稱為終點(endpoints)。

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

  • 節點集合:
    {v1,v2,v3,v4}
  • 邊集合:
    {e1,e2,e3,e4,e5,e6,e7}

    藉由觀察可發現
    e1,e2
    有相同終點,
    e3,e4
    亦有相同終點

圖的種類

  • 自環(loop): 一條有相同終點的邊
  • 多重邊(multiple edge): 兩條或以上的邊有相同終點
    如圖,
    e1
    就是自環,終點
    v2,v2
    有多重邊
    e2
    e3

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

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)

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

G1 就是一張簡單圖,其中
e1=v1v2

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)

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

G¯
舉例: 上圖
G1
的補圖
G1¯
長這樣

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)

在一張圖中選任兩節點

vi,vj 都能找到一條邊連接,則稱完全圖
藉由上圖的
G1
G1¯
,不難發現其實一張圖結合他的補圖,就會形成一張完全圖

  • 一張
    n
    節點的完全圖會被寫作
    Kn
    ,因此下圖也被稱為
    K5
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

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

{v3,v4} 為一個獨立集、集合
{v2,v3}
亦為獨立集
反例: 在下圖中,集合
{v1,v2,v5}
不唯獨立集,因為存在邊
v2v5
v1v5

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

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

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

舉例: 像是下圖就是一個

K2,3

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. 在柯尼斯堡的七橋問題中,為什麼不能「在每座橋梁都只能走一遍的情況下,把每座橋梁都走遍」?

  2. 假設在一家公司有四位員工(編號 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 →


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

參考資料


下一篇: 基礎圖論(二)

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