Cactus Graph

Directed Cactus Graph

有向圖上，每條邊隸屬於恰好一個有向環。另一種說法：許多有向環，相互銜接成樹狀，接縫恰好是一點。

要判斷一張有向圖是不是仙人掌，原理就跟判斷關節點的方法相同。

使用 DFS ，會遇到三種情形：

一、 (i, j) 是 cross edge 或 forward edge：

    tree edge 和 back edge 剛好構成仙人掌全部的邊，
    不會有 cross edge 與 forward edge。
    如果有，就表示不是仙人掌。

    實作時，可利用 DFS stack 判斷，
    如果 j 不在 stack 又已經拜訪過（也就是 j 已經從 stack 彈出），
    則表示 (i, j) 一定是 cross edge 或 forward edge。

二、 (i, j) 是 back edge：

    如果從 i 就已經有路可以走回到 i 的祖先（也是會經過其他的back edge），
    此時 j 又走回到 i 的祖先，表示環重疊，不是仙人掌。

    範例一：12 23 34 45 56 62 53!       // i = 5 and j = 3
    範例二：12 23 34 45 51! 53!         // 怎麼好像在寫棋譜...

    實作時，累加 i 回到祖先的路有幾條，只能是恰好一條。
    可利用關節點演算法的原理，記錄 i 可到達的最高祖先。

三、 (i, j) 是 tree edge：

    與 2. 的概念很像，不過要在 DFS 的回溯階段才能判斷。
    如果從 i 就已經有路可以走回到 i 的祖先，
    此時 j 又有路走回到 i 的祖先，表示環重疊，不是仙人掌。

    範例一：12 23 34 45 56! 67! 72! 58! 89! 91!     // i = 5 and j = 8
    範例二：12 23 34 45 51! 58! 89! 91!             // 同上

    實作時，累加 i 回到祖先的路有幾條，只能是恰好一條。和（二）一起累加。
    可利用關節點演算法的原理，記錄 i 可到達的最高祖先。

DFS 結束之後，
最後要判斷 DFS 是否能順利走到圖上所有點。

附註：樹根不必走到祖先，要當作例外處理。可以選定任何一點作為樹根。

int adj[9][9]; int visit[9], low[9], t = 0; bool leave[9]; // 已經結束拜訪的節點 bool DFS(int p, int i) { visit[i] = low[i] = ++t; int c = 0; for (int j=0; j<9; ++j) if (!visit[j]) // tree edge { // 一旦發現不是仙人掌就可以馬上結束 if (!DFS(i, j)) return false; // 找到一條走回到i點祖先的路 if (low[j] < visit[i]) if (++c > 1) return false; // 更新i點可走到的最高祖先 low[i] = min(low[i], low[j]); } else // back edge { // 排除 forward edge 與 cross edge 的情況 if (leave[j]) return false; // 找到一條走回到i點祖先的路 if (visit[j] < low[i]) if (++c > 1) return false; // 更新i點可走到的最高祖先 low[i] = min(low[i], visit[j]); } leave[i] = true; return p == -1 ? true : c == 1; } bool directed_cactus() { memset(visit, 0, sizeof(visit)); memset(leave, 0, sizeof(leave)); t = 0; // 也要確認DFS是否有走到圖上所有點 return DFS(-1, 0) && t == 9; }

UVa 10510 ICPC 3514 4045

Ear Decomposition

ear decomposition
一、一個環。（也有人拆成一條邊和一條路徑。）
二、一條路徑。端點是先前的點，其餘點不是先前的點（無向圖）。
　　端點是先前的點，邊不是先前的邊（有向圖）。
三、重複二。

open ear decomposition
所有路徑端點皆異。

undirected grpah
2-vertex-connected iff open ear decomposition. (|E| > 1)
2-edge-connected iff ear decomposition.

directed graph
strongly connected iff ear decomposition. (?)

ear decomposition of an undirected graph G can be
obtained as a collection of appropriate subpaths of
fundamental cycles of a spanning tree of G.

Corollary 7.2.3
Every ear decomposition of a strong digraph on
n vertices and m arcs has m - n + 1 ears.

無向圖演算法（Schmidt's Algorithm）

《A Simple Test on 2-Vertex- and 2-Edge-Connectivity》

DFS Tree所有邊顛倒方向。按照遍歷順序找耳。

https://codeforces.com/blog/entry/80932

有向圖演算法

《Digraphs: Theory, Algorithms and Applications》

https://www.cs.rhul.ac.uk/books/dbook/main.pdf   pp350

Width

https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)
https://math.stackexchange.com/questions/2403257/
http://mathsci.kaist.ac.kr/~jisujeong/jisu_grow2015.pdf

Tree Decomposition

http://www.cs.uu.nl/docs/vakken/an/an-treewidth.pdf
http://www.mi.fu-berlin.de/en/inf/groups/abi/teaching/lectures_past/WS0910/V____Discrete_Mathematics_for_Bioinformatics__P1/material/scripts/treedecomposition1.pdf
http://web.engr.illinois.edu/~jeffe/teaching/comptop/2009/notes/treewidth.pdf
https://kam.mff.cuni.cz/~fiala/tw.pdf

一、樹分解的點，是原圖的點集合。
二、圖上的邊的兩端點，位於樹分解的同一點。
三、圖上的點，位於樹分解的某棵連通子樹的每一點。
四、樹分解最小的點，大小減一，就是寬度。

Partial k-Tree

https://code.google.com/codejam/contest/801485/dashboard#s=a&a=1

UVa 12615

Clique Tree

chordal = clique tree exist

clique tree只是其中一種tree decomposition。其treewidth是maximal clique的大小減一。

http://www.liafa.jussieu.fr/~habib/Documents/coursII-2.pdf
chordal 是 subtree intersection on a tree   可以形成 clique tree
interval 是 path intersection on a tree   可以形成 clique path

clique tree T:
(1) maximal clique => vertice of T
(2) minimal separator => edge of T
(3) all cliques containing vertex x => subtree of T

  the set of clique trees T of a chordal graph
= the set of maximum weight spanning trees of the clique-intersection graph
  (edge weight = |intersection of two maximal cliques|)

ICPC 7458