Cactus Graph

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 是否能順利走到圖上所有點。

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

UVa 10510 ICPC 3514 4045

Ear Decomposition(Under Construction!)

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

Tree Decomposition(Under Construction!)

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

Modular Decomposition(Under Construction!)