Graph

Graph

Graph中文翻做「圖」。此處談及的「圖」並不是指圖片或者圖形。「圖」是一種用來記錄關聯、關係的東西。

一張圖由數個點(vertex)以及數條邊(edge)所構成。點與點之間,得以邊相連接,表示這兩點有關聯、關係。

點的大小形狀和線的粗細長短是無所謂的,我們只在乎它們如何連接。只要連接的關係對了,要怎麼畫都行,簡約、雅觀、平易近人即可!

兩點之間也可以有很多條邊,甚至有自己連到自己的邊。兩點之間有很多條邊,代表這兩點有很多項關聯。一個點有自己連到自己的邊,表示自己和自己有項關聯。

Isomorphism / Isomorphic

Isomorphism中文譯作「同構」,Isomorphic中文譯作「同構的」。如果兩張圖的連接方式一模一樣時,則稱作「同構」。

圖上的邊可以是直的,也可以是彎彎曲曲的,也可以是交錯的。不論邊的形狀如何,都不會改變點與點之間的關聯、關係,終究都會是同構的圖。

圖上的點可以任意移動位置。不論點的位置如何,都不會改變點與點之間的關聯、關係,終究都會是同構的圖。

同構的圖擁有相同的資訊,所以不管選擇哪一張圖都是可以的,只要清楚易懂就可以了!

Directed Graph(Digraph)

邊甚至可以擁有方向性,用來表示兩點間的關係是單向的,並非雙向的。無向邊代表雙向關係,有向邊代表單向關係。

一張圖若都是沒有方向性的邊,稱作「無向圖」;一張圖若都是有方向性的邊,則稱作「有向圖」。如果圖上有一些邊是單向的,有一些邊是雙向的,那我就不知道那該叫做什麼圖了。

替點和邊加上權重

圖上的點可以擁有權重,可做其他用途。

圖上的邊可以擁有權重,可做其他用途。

替點和邊取名字、代號

點和邊上面可以取名字、代號,方便辨認。名字、代號可以寫在點和邊的旁邊,也可以寫在點的裡面、邊的上面,只要能表達清楚就好。

名字可以隨便取,簡單明瞭就好。書上通常是用英文字母及數字居多。

Graph資料結構

Edge List

來談談如何利用程式語言來儲存一張圖吧!

最簡單的方式,就是用個陣列,記錄所有點與點之間的邊。這種方式相當直觀,也非常節省空間,但是卻不適合用於計算(請各位讀過圖論其他主題後,再來思考看看)。所以這裡要介紹其他類型的方法。

儲存一張圖的方式有許多種,這裡介紹其中兩種最常見的方法:adjacency matrix、adjacency lists。adjacency為「相鄰」之意,以邊相連接的兩個點,則稱這兩個點「相鄰」。

Adjacency Matrix

把一張圖上的點依序標示編號,然後建立一個方陣,來記錄連接資訊。方陣中的每一個元素都代表著某兩點的連接資訊。例如元素(0,1)記錄著第0點到第1點的連接資訊、元素(4, 2)記錄著第4點到第2點的連接資訊。如此一來,任意兩個點之間的資訊,都有對應的地方可用於記錄,纖悉無遺。

連接資訊可以是邊的數目,也可以是邊的權重,也可以儲存其他的資訊。

值得一提的是,adjacency matrix可以用來記錄邊的權重。但是它卻沒辦法記錄點的權重,它也沒辦法同時記錄點和邊的權重。不過,要記錄點的權重,其實只要另外開一條陣列就行了,也不是什麼難事。

另外,當兩點之間的邊超過一條的時候,adjacency matrix沒辦法記錄權重,因為adjacency matrix的一個格子只能存入一個數字,沒辦法同時間存入多個數字。我們可以修改adjacency matrix的構造以存入更多數字,只是這不在討論範圍之內,各位可自行研究。

程式碼可以寫成這樣:

Adjacency Lists

把一張圖上的點依序標示編號。每一個點,後方串連所有相鄰的點。例如第4列之中所列的數字,即是與第4點相鄰的點。

第一種,是古板的實作方式,自行實作list:

第二種,是輕鬆的實作方式,利用程式語言內建的list或vector:

第三種,是簡約的實作方式,適用於邊數不多時:

第四種,是奇妙的實作方式,把邊依序放入陣列:

如果還要記錄邊的權重,就變成這樣:

如果還要記錄點的權重,那就另外再開一條陣列吧。

Graph Traversal

Graph Traversal

給你一張圖,要怎麼讀出它的資訊呢?

用人眼來觀察一張圖,很快的就能看出點和線,一點一點釐清關係。要是一張圖能夠畫得漂亮一點,上個鮮明的顏色,那就更好了。

電腦則不然。要以電腦來讀取一張圖的資訊(這資訊想必會以圖的資料結構來妥善儲存),唯一的方法就是透過程式語言,以及良好的演算法囉!

Traversal中文稱作「遍歷」。圖的遍歷,也就是指通盤地讀取圖的資訊:決定好從哪裡開始讀,依照什麼順序讀,要讀到哪裡為止。詳細地設計好流程,始能通盤地讀取圖的資訊;如果設計得漂亮,在解決圖的問題時,還可以一邊讀取圖的資訊,一邊順手解決問題呢!

利用最簡單的資料結構queue和stack,就能製造不同的遍歷順序,得到兩種遍歷演算法:Breadth-first Search和Depth-first Search。這兩個演算法充分了利用程式語言的特性,簡約而美麗,成為資訊領域不可不知的演算法。

Graph Traversal: Breadth-first Search

Breadth-first Search(BFS)

(依照編號順序)不斷找出尚未遍歷的點當作起點,進行下述行為:
 一、把起點放入queue。
 二、重複下述兩步驟,直到queue裡面沒有東西為止:
  甲、從queue當中取出一點。
  乙、找出跟此點相鄰的點,並且尚未遍歷的點,
    通通(依照編號順序)放入queue。

教科書都有一步一步的示意圖,這裡不再重畫,只做額外補充。

運用BFS遍歷整張圖,最後得到許多棵樹。單一的樹稱作BFS Tree,所有的樹稱作BFS Forest。

不同的起點,形成不同的BFS Forest。我們習慣按照編號順序選擇下一個要拜訪的點,得到唯一一種BFS Forest。

遍歷順序示意圖:每個點進入與離開queue的時刻

每個點進入queue的時刻以左上深色數字表示,每個點離開queue的時刻以右下淺色數字表示。每個點都會進入queue一次、離開queue一次,不會再有第二次。

遍歷順序示意圖:每個點離開queue的時刻

只觀察離開queue的時刻,可以發現BFS優先走遍距離起點最近之處,優先讓BFS Tree變得寬廣,因而得名Breadth-first Search。這個遍歷順序能夠解決許多圖論問題!

時間複雜度

使用的資料結構為adjacency matrix的話,可以以O(V^2)時間遍歷整張圖;使用adjacency lists的話,可以以O(V+E)時間遍歷整張圖。V是圖上的點數,E是圖上的邊數。

程式碼(adjacency matrix)

Graph Traversal: Depth-first Search

Depth-first Search(DFS)

DFS與BFS大同小異,只是把queue換成了stack而已。

遍歷順序示意圖:每個點進入與離開stack的時刻

每個點進入stack的時刻以左上深色數字表示,每個點離開stack的時刻以右下淺色數字表示。每個點都會進入stack一次、離開stack一次,不會再有第二次。

遍歷順序示意圖:每個點離開stack的時刻

只觀察離開stack的時刻,可以發現DFS優先走遍距離起點最遠之處,優先讓DFS Tree變得深遠,因而得名Depth-first Search。這個遍歷順序能夠解決許多圖論問題!

遞迴版本程式碼(adjacency matrix)

DFS的程式碼也可以寫成遞迴形式。程式語言中的遞迴,其實就是利用stack來實作的。

遍歷順序示意圖:每個點進入遞迴與離開遞迴的時刻

進入遞迴的時刻以左上深色數字表示,離開遞迴的時刻以右下淺色數字表示。這個順序用於解決一些特別的圖論問題。

製圖時,DFS Tree高度至少是三、分枝數目至少是三,比較容易觀察出遍歷順序。建議讀者也自己畫個圖、寫段程式研究一下。

邊的分類

藉由一叢DFS Forest,一張有向圖的邊可以分成四類:

Tree Edge:樹上的邊。
Back Edge:連向祖先的邊。(形成環)
Forward Edge:連向子孫的邊。
Cross Edge:枝葉之間的邊、樹之間的邊。(可能形成環)

藉由一叢DFS Forest,一張無向圖的邊可以分成兩類:

Tree Edge:樹上的邊。
Back Edge:連向祖先的邊。(形成環)

這些邊的分類,可以協助我們解決複雜的圖論問題。

d[x] : 節點 x 進入遞迴的時刻
f[x] : 節點 x 離開遞迴的時刻
(i, j) is a tree edge or a froward edge : d[i] < d[j] < f[j] < f[i]
(i, j) is a back edge : d[j] < d[i] < f[i] < f[j]
(i, j) is a cross edge : d[j] < f[j] < d[i] < f[i]

Graph Property

先看個圖片

圖片中省略了點的編號。

degree

一個點的「度」:一個點的邊數量。

有向圖,細分成入邊數量in-degree、出邊數量out-degree。

neighbor

一個點的「鄰居」:一個點連往的點。可能有許多個、零個。

無向圖,鄰居數量是邊數量。有向圖,鄰居數量是出邊數量。

順便補充幾個常見形容詞。

adjacent:相鄰、鄰接。只走一步,可以抵達。
connected:相連、連通。不限步數,可以抵達。

distance

兩個點的「距離」:從起點走到終點的邊數量,數量必須最低。

如果兩點之間不連通,距離是無限大。約定成俗。

指定起點,實施Breadth-first Search,就可以算出起點走到圖上各點的距離。利用這種方式,可以算出兩點之間的距離。大家可以試試看!

額外補充一下。當數量必須最低,改成了數量必須最高,則無法透過遍歷演算法求得答案,只能透過backtracking窮舉所有路線,一一判斷答案。數量必須最高,已被證明是NP-complete問題,目前沒有(以後大概也不會有)快速的演算法。

Graph Manipulation

Intersection Graph

圖用來表達兩兩之間的關係。例如一群人,我們可以建立「朋友關係」的圖,兩個人是朋友就連一條邊,兩個人不是朋友就沒有邊。只要是兩兩之間的關係,就得以轉化成圖,運用圖論知識來分析問題。

其中有個值得一提的關係是「交集關係」,是聯集交集的那個交集。兩個東西有交集就連一條邊(交集不是空集合)、沒交集就沒有邊(交集是空集合),最後得到的圖叫做「交集圖」。

例如一堆線段,把互相接觸的線段,表示成圖:

例如一堆集合,把有交集的集合,表示成圖:

比較特別的交集圖,數學家會特地取名。例如一堆硬幣,平鋪在桌上,把互相接觸的硬幣,表示成圖,稱作Coin Graph。數學家發現硬幣圖和平面圖兩者完全等價,每一種平面圖都可以利用硬幣接觸兜出來。

例如行程表,把撞期的行程,表示成圖,稱作Interval Graph,有著很特別的數學性質。

例如一張圖論的圖,把共用端點的邊,表示成圖,就是先前提到的Line Graph。

為什麼數學家特別重視交集圖呢?我也不知道。

很多人把交集圖看做是一個物品。但是交集圖其實是一種變換的概念,可以看做是一個函數。

Dependency Graph【尚無正式名稱】

除了「交集關係」之外,數學家也很重視「依賴關係」。把各個東西的仰賴對象表示成圖,最後得到的圖叫做「依賴圖」。

例如一堆不等式,把變數大小關係,表示成圖:

比較特別的依賴圖,數學家會特地取名。例如專案管理領域,把工作先後次序,表示成圖,稱作「Activity Network」。

例如2-SAT問題,把各個clause裡面的兩個變數的取捨關係,表示成圖,稱作「Implication Graph」。

交集圖是無向圖、依賴圖是有向圖,剛好一對。

Subgraph / Supergraph

一張圖,刪除一些點、一些邊,得到的圖稱作「子圖」。

原圖(沒有刪除)、空圖(完全刪除),也算是「子圖」。

一張圖,增加一些點、一些邊,得到的圖稱作「父圖」。

原圖(沒有增加)也算是「父圖」。

subgraph和supergraph是相對的。如果A是B的子圖,那麼B就是A的父圖。我們習慣只講子圖,講一個就等於兩個都講了。

Induced Subgraph / Induced Supergraph

一張圖,保留一些點、以及這些點之間的所有邊,得到的圖稱作「導出子圖」。

一張圖,增加一些點、一些邊,但是不在原本的點之間增加邊,使得原本的圖是導出子圖,得到的圖稱作「導出父圖」。

induced subgraph和induced supergraph是相對的。如果A是B的導出子圖,那麼B就是A的導出父圖。我們習慣只講導出子圖,講一個就等於兩個都講了。

Minor / Subdivision

一張圖,收縮一些邊、合併一些點,得到的圖稱作minor。

收縮的邊,有人視情況刪除,也有人視情況不刪除、而變成連向自己的邊。

一張圖,在邊上植入點,得到的圖稱作subdivision。

minor和subdivision是相對的。一般只討論minor。

ICPC 4023

Oriented Graph / Underlying Graph

一張無向圖,無向邊改成有向邊,稱做「定向圖」。

一張有向圖,有向邊改成無向邊,稱作「底圖」。

定向圖和底圖是相對的。一般只討論定向圖。

Complement Graph(Complement)

一張圖,兩點之間沒邊變有邊、有邊變沒邊,稱作「補圖」。

原圖暨補圖的所有邊,合起來是完全圖。

朋友變仇人、有關變無關,整個相反顛倒,就是補圖的用處。

Reverse Graph(Transpose)

一張有向圖,邊的方向顛倒,稱作「反向圖」。

主動變被動、前進變後退,整個相反顛倒,就是反向圖的用處。

Line Graph

一張圖當中,觀察邊與邊關係,相鄰的邊表示成一張圖,稱作「線圖」。

UVa 10988 11175

Dual Graph

一張平面圖當中,觀察面與面關係,共邊的面表示成一張圖,稱作「對偶圖」。詳情請參考「Planar Graph」。

Hypergraph

Hypergraph

「圖」是談兩個東西之間的關係,「超圖」則是談多個東西之間的關係,例如三個東西之間的關係。

超圖的資料結構,不適合採用adjacency matrix,因為矩陣必須變成多個維度,浪費記憶體空間。比較好的方式是採用incidence matrix。

一般的圖就很夠用了,通常不會用到超圖。