Graph Isomorphism

【待補文字】

Tree Isomorphism

UVa 10729

Planar Graph

Euler characteristic

UVa 10178

最小生成樹           O(n)
st最短路徑(無負邊)   O(n * sqrt(log(n)))
st最短路徑(負邊)     O(n^1.5)
st最大割             O(n^1.5 * log(n))
st最小割             = st最短路徑
st最大流             = st最短路徑
最小割               = ∅-join
完美匹配計數         FKT algorithm

平面圖是disk graph
平面圖是平面上一堆線段的intersection graph

Chordal Graph

ICPC 2424 2841

只要是長度大於三的迴圈，必定有一條弦。

照這樣的定義看來，一個把邊增加到極限的Chordal Graph會成為Complete Graph（如果兩點間最多只有一條邊）？一個把邊減少到極簡的Chordal Graph會成為平面圖，當所有兩點之間都是雙連通，還會是計算幾何中所說的三角化？

還有另外一種工程上的觀點，想像有一個二維的結構，由節點和極硬的竿子所組成，柱子可以連結兩個節點。以正方形為例，他是一個長度為四的迴圈，但是沒有弦（對角線），如果上方有一個力量施加下來，那這正方形就扁了（假設竿子很硬且長度固定，連接處可以旋轉，節點不會壞掉）。但是如果結構是一個正方形加上一個對角線，他就屬於Chordal Graph，而當上方有力量施加下來，結構不會垮掉，因為有對角線在穩定結構。

Perfect Graph

完美圖就是一張圖的每一個導出子圖，最小著色數皆等於最大clique的點數。

定理一：原圖與補圖要嘛同時是完美圖，要嘛都不是完美圖。
　　　　換句話說，若原圖是完美圖，則補圖亦如是。反之亦然。(1972)

定理二：完美圖不含奇環(n>=5)，也不含奇環(n>=5)的補圖。反之亦然。 (2002)

判斷一張圖是否是完美圖，有多項式時間演算法。Chudnovsky et al. 2005

http://www.math.sinica.edu.tw/math_media/d174/17403.pdf

Cactus Graph

UVa 10510 ICPC 3514

Circular-arc Graph

ICPC 4274

Cograph

ICPC 3666

Line Graph

UVa 10988