planar graph

planar graph

一張圖,畫在平面上,點不重疊、邊不交叉,稱作「平面圖」。

先前在「graph」提及了同構的概念:一張圖可以挪動點與邊。一張平面圖,就算挪動點與邊,使得點重疊、邊交叉,也還是平面圖。反過來說,一張圖,畫在平面上,挪動點與邊,使得點不重疊、邊不交叉,也算是平面圖。

那有沒有立體不打結圖呢?應該有吧。

Euler characteristic

凡是點、邊、面這些基本元件之間的數量關係,就稱作Euler characteristic。歐拉是第一位想到這件事情的數學家。

平面圖當中,則有V+F=E+2這個數量關係,其中V代表點數、E代表邊數、F代表面數。統計數量之前,需要挪動點與邊,使得點不重疊、邊不交叉。

進階版本是V+F=E+C+1,其中C代表連通分量數目。

你會證明嗎?:-)

UVa 10178

dual graph

設計平面圖演算法時,「對偶圖」是相當重要的工具。

一張平面圖當中,面與面的相鄰關係表示成一張圖,就得到對偶圖。對偶圖當中,面與面的相鄰關係表示成一張圖,就得到原來的平面圖。

原圖和對偶圖可以互相轉換成為對方。原圖和對偶圖擁有相等的資訊量,只是以不同形態呈現。

有向圖的情況比較特別:對偶圖從右往左穿越邊;橋與自環無法判斷左右,對偶圖以逆時針方向穿越邊。此定義亦可改成從左往右、順時針。

運用同構的概念,挪動原圖的點與邊,就會得到另外一種對偶圖。對偶圖可能有許多種,而且不見得同構!

由於缺乏優美規律,因此談論對偶圖時,習慣忽略同構。

最特別的對偶圖例子,就是橋(bridge)與自環(loop)。舉例來說,原圖是一棵樹,對偶圖是一個點以及一大堆自環;各種樹對應各種自環包覆方式。

由於缺乏優美規律,因此談論對偶圖時,習慣忽略橋與自環。原圖凡是無橋、無自環,對偶圖即是無橋、無自環。

圖論當中,有許多對偶方式。最名聞遐邇的對偶方式,就是平面對偶。於是dual graph這個名詞,就留給了平面對偶所得到的圖;其他對偶方式則有其他名稱。

UVa 11706

planar graph資料結構

平面圖當中,點不重疊、邊不交叉。鄰邊與鄰面交錯排列。

adjacency lists當中,各點的鄰邊,可以依照時針順序排序!

如何判斷鄰邊次序?我沒有學會。如果你知道,麻煩告訴我。

planar graph recognition(planarity testing)

運用depth-first search,時間複雜度O(V+E):

動態圖的情況下,均攤時間複雜度O(log³V):

UVa 10768

mininum spanning tree(Matsui, 1994)

原圖的最小生成森林以外的邊,就是對偶圖的最大生成樹。

原圖的每一種最小生成森林、對偶圖的每一種最大生成樹,一一對應。

證明:一、視樹為牆。樹無環,故面有出口、面皆連通。二、生成樹須連通,故任兩面僅能有一條通路,否則兩條以上通路將切斷生成樹連通。三、生成森林無須連通,但是兩生成子樹的任兩面,其通路必經最外面(可想成樹根),故任兩面仍僅有一條通路。四、承一二三,所有面連通、任兩面只有一條通路,即是面的生成樹!五、牆最小,非牆最大,故得面的最大生成樹。

演算法原理類似「Borůvka's algorithm」,同時考慮原圖和對偶圖,同時計算原圖的最小生成樹、對偶圖的最大生成樹。

一、隨時刪除所有自己連向自己的邊,也就是刪除所有自環。
二、重複以下步驟V次:
 口、原圖以及對偶圖,一定找得到一個度數小於4的點,稱作a點。
 口、如果a點在原圖上:
  甲、原圖a點所屬的生成子樹,找權重最小的聯外邊ab。
  乙、原圖的最小生成樹有邊ab。
  丙、原圖收縮邊ab、對偶圖刪除邊ab。兩圖隨時保持對偶。
 口、如果a點在對偶圖上:
  甲、對偶圖a點所屬的生成子樹,找權重最大的聯外邊ab。
  乙、對偶圖的最大生成樹有邊ab。
  丙、對偶圖收縮邊ab、原圖刪除邊ab。兩圖隨時保持對偶。

因為度數小於4,找最小鄰邊的時間複雜度降為O(1),總時間複雜度降為O(V+E),到達了下限。

平面圖:V+F=E+C+1
原圖以及對偶圖的總度數:2E + 2E' = 4E
原圖以及對偶圖的總點數:V + V' = V + F = E+C+1
原圖以及對偶圖,一個點的平均度數:4E / (E+C+1) < 4
原圖以及對偶圖,一定至少有一個點,其度數小於等於平均度數,也就是小於4。

由於要維護原圖和對偶圖的資料結構,還要隨時找到度數小於4的點,所以此演算法的實際運行速度,遠比一般圖的最小生成樹演算法來得慢。

儘管此演算法並不實用,但是此演算法開啟了一條道路,讓我們知道各種圖論問題一旦搬到平面圖上,只要運用對偶圖、度數等等性質,時間複雜度就會有很大的改進。

至於有向圖的版本,我不知道有沒有人研究。

shortest path

已經有詳細的課程教材,不再重複整理。

ICPC 6438

minimum s-t cut / maximum s-t flow

原圖的最小st割=對偶圖的最小分隔環。

Multiple-source shortest paths in planar graphs
build O(nlogn)  query O(logn)

Multiple-Source Single-Sink Maximum Flow in
Directed Planar Graphs in O(diameter ⋅ nlogn) Time
http://arxiv.org/pdf/1104.4728.pdf

Multiple-Source Multiple-Sink Maximum Flow in
Directed Planar Graphs in Near-Linear Time
https://arxiv.org/pdf/1105.2228
O(n log³ n)

Maximum Integer Flows in Directed Planar Graphs with
Multiple Sources and Sinks and Vertex Capacities
https://arxiv.org/pdf/1804.08683
O(n log³ n + kn)

ICPC 3661

maximum clique

最大團頂多4點。窮舉所有子團,時間複雜度O(V+E)。

備忘

平面圖判定     	Kuratowski's theorem  	O(N)
存在歐拉回路    	對偶圖存在二分圖    	O(N)
最小生成樹     	對偶圖最大生成樹的補圖 	O(N)
st最短路徑(無負邊)	            	O(N sqrtlogN)
st最短路徑(有負邊)	            	O(N sqrtN)
st最小割=st最大流 	對偶圖最小分隔環    	O(N logN)
最小割       	對偶圖最小環      	O(N logN logN)
最小割樹      	對偶圖最小環基底    	O(N sqrtN logN)
最大割       	對偶圖中國郵差問題   	O(N sqrtN logN)
²⁄₃點分隔      	planar separator theorem	O(N)
完美匹配計數    	FKT algorithm
degeneracy = 5    存在某一點,邊數小於等於5
arboricity = 3    分解成生成森林,數量大於等於3

outerplanar graph

All vertices belong to the outer face.

triangulated plane graph

Every triangulated plane graph has a canonical ordering. O(N).