chordal graph

cycle / chord / hole / triangle

「環」是串成一圈的路線,沒有重複的點。

「弦」是環上不相鄰兩點之間的邊。

「洞」是一種特別的環,沒有弦。

「三角形」是三條邊的環,沒有弦。

ICPC 7661

chordal graph(monotone transitive graph)

「弦圖」。多於三條邊的環,必有弦。

換句話說,多於三條邊的洞,必不存在。

弦圖的定義,隱含著遞迴。一個環,從弦切開,形成兩個環,仍需要遞迴切開。所有環切碎成三角形。一個環可以同時切開多處。

弦圖的外觀,宛如許多三角形交錯疊合,附帶許多樹、許多鏈。

學過「三角剖分」的讀者要特別當心,三角剖分通常不是弦圖。

弦圖隨便刪除幾個點(以及連帶的邊),仍是弦圖。換句話說,弦圖的導出子圖是弦圖。

森林、有向無環圖、二分圖、弦圖,都具有這種遞歸性質。

perfect elimination ordering

楔子

「有向無環圖」擁有「拓樸順序」。反之亦然。
「弦圖」擁有「完美消除順序」。反之亦然。

simplicial vertex【註:古代名稱,今日看來詞不達意。】

「單體點」。該點的所有鄰居,之間必有邊。

換句話說,該點的所有鄰居,形成團。

換句話說,該點暨所有鄰居,形成極大團。

perfect elimination ordering

「完美消除順序」。逐次刪除當下的任意一個單體點,所得到的順序。通常有許多種。

刪除單體點,擁有諸多意義:

一、單體點所屬的極大團的大小減一。

二、單體點的鄰邊們,視作弦。單體點所屬的環們,從弦切開。環被削去一角,留下弦。

三、單體點i,鄰居j,鄰居k,形成三角形ijk。邊ji暨邊ik繞遠路,邊jk抄近路。刪除遠路,保留近路。

elimination graph / elimination tree

「消除圖」。完美消除順序可以畫成有向圖。

每個單體點源自哪個團。

「消除樹」。完美消除順序可以畫成有向森林。

當前點的父親,是順序更大、順序最早的鄰居。

時間複雜度等於一次graph traversal的時間。

perfect elimination ordering testing

檢查一個順序是不是完美消除順序。

一、遞增法。時間複雜度O(V³)。

依序掃描,逐一檢查是否為單體點。檢查所有鄰居是否為團──鄰居之間所有點對,必須都有邊。

二、遞推法。時間複雜度O(V+E)。

反向掃描,逐一檢查是否為單體點。

當前點a,鄰居b,鄰居取順序更大、順序最早者。b已是單體點,b已是團。想要確認a是否形成團,只需檢查a點與b團之間的邊──「a的鄰居」必須包含於「b暨鄰居」。

簡單來說,檢查消除樹每一對父子──在消除圖上,「子的鄰居」必須包含於「父暨鄰居」。

窮舉時,子為主,父為輔。父重複出現,時間複雜度O(V²)。

窮舉時,父為主,子為輔,時間複雜度壓至O(V+E)。

數學證明:弦圖⇔完美消除順序

(⇒)弦圖必有單體點(容後證明)。弦圖隨便刪除一個點,仍是弦圖。弦圖可以遞迴刪除單體點。

(⇐)任意一個多於三條邊的環,此環之中,順序最早的點,稱之v。因為v的所有鄰居必有邊,所以此環必有弦。

數學證明:弦圖必有單體點

證明又臭又長,缺乏實際用途。讀者可以跳過。

每個連通分量都是弦圖,各自處理。方便起見,假設圖連通。

一張圖要嘛是完全圖、要嘛不是完全圖。

如果是完全圖:所有點都是單體點。得證。

如果不是完全圖:有兩點不相鄰。進一步找到「最小點分隔minimum vertex separator」:讓兩點不連通的最小點集合S。

整張圖分離成四個集合ABSR。AB顯然不是空集合。S不是空集合(假設圖連通)。R可能是空集合。

一、S是團。

根據最小點分隔,AB之間無邊,S每一點到AB都有邊。

根據弦圖,S到AB的邊形成環,而AB之間無法有弦,於是AS之間、BS之間必須有弦,於是S之間必須有弦。

二、單體點不可能位於S,只可能位於ABR。

S到AB都有邊,但是AB之間無邊,無法形成團。

接下來專心考慮單體點可能位於A的情況。

A∪S要嘛是團、要嘛不是團。

如果是團:A的所有點都是單體點。得證。

如果不是團:A∪S有兩點不相鄰。進一步重新找到最小點分隔。整張圖重新分離成四個集合A'B'S'R'。

一、A∪S有兩點不相鄰,不可能兩點皆位於S。

因為S是團。

二、新的最小點分隔S',不會用到B,不會用到R。

其中一點位於A。然而AB之間無邊,AR之間無邊。

三、如果一點在A一點在S,那麼B⊆B'。

(a'∈A、b'∈S、a'∈A'、b'∈B')

AB之間無邊,SB之間有邊,B將併入B'。

四、如果兩點都位於A,那麼B⊆R'。

(a'∈A、b'∈A、a'∈A'、b'∈B')

AB之間無邊,B不會併入A'B'。B跟A'B'S'皆不相交,那就只剩R'了。

五、(A'∪S') ⊂ (A∪S),尺寸變小。

B'至少佔據一點,(A'∪S')至少縮小一點。

遞迴下去,A'∪S'不斷縮小,直到形成團。最差的情況是A'變成一點。得證。

chordal graph recognition

檢查一張圖是不是弦圖。主要有兩種策略:

一、窮舉多於三條邊的環,檢查弦。總共O(V!)種。

能不能只檢查特定的環呢?事實上可以。請自行上網搜尋資料。

二、窮舉各種順序,檢查是否為完美消除順序。總共V!種。

能不能只檢查特定順序呢?事實上可以。請見下個章節。

graph traversal

楔子

有向無環圖的拓樸順序:特殊BFS順序、DFS逆序
弦圖的完美消除順序:MCS逆序、LexBFS逆序、LexDFS逆序

除了BFS、DFS,再補充三個遍歷演算法MCS、LexBFS、LexDFS,用來找到團。

maximum cardinality search(MCS)

每回合找到一個點,連往已拜訪點的邊數最多。如果很多點同時符合條件,則任選一點。

時間複雜度O(V²)。運用binary heap壓至O(V+ElogV)。運用Fibonacci heap壓至O(E+VlogV)。運用bucket sort壓至O(V+E)。

這些加速技巧,也出現在單源最短路徑演算法。請見本站文件「path」。

補充一下bucket sort的時間複雜度分析。隨時紀錄最大值放在哪個桶子。刪除最大值、尋找次大值,只需笨拙地不斷減一,直到遭遇次大值。

邊數總是加一,總共加E。尋找次大值,總共頂多減E。時間複雜度O(V+E)。

lexicographic breadth-first search(LexBFS)

BFS深入考慮細節。仔細安排小孩的拜訪順序:優先擴大團。

i from V-1 to 0
取字串最大的點。
所有未拜訪鄰居,字串尾端添加i。
BFS:優先拜訪深度最小的點。
LexBFS:深度平手時,優先拜訪字串最大的點。
LexBFS-:字串平手時,優先拜訪索引值最小的點。

時間複雜度O(V²)。運用bucket sort壓至O(V+E)。

lexicographic depth-first search(LexDFS)

DFS深入考慮細節。仔細安排子孫的拜訪順序:優先擴大團。

i from 0 to V-1
取字串最大的點。
所有未拜訪鄰居,字串開頭添加i。
DFS:優先拜訪深度最大的點。
LexDFS:深度平手時,優先拜訪字串最大的點。
LexDFS+:字串平手時,優先拜訪索引值最大的點。

時間複雜度O(V²)。運用binary heap壓至O(V+ElogV)。運用vEB tree壓至O(V+EloglogV)。

數學證明:弦圖⇔ MCS逆序是完美消除順序

(⇒)遞迴刪除單體點:

一、遍歷過程,不受未拜訪點的影響。因此,一張圖刪除最後一個拜訪的點,重新實施遍歷演算法,遍歷順序依然相同。

二、遍歷過程,優先擴大團。因此,最後一個拜訪的點,必是極大團的點,必是單體點。

(⇐)先前章節提過,完美消除順序必得弦圖。

MCS逆序、LexBFS逆序、LexDFS逆序,三者皆是如此。

chordal graph recognition

判斷弦圖,只需針對特定順序,無須窮舉各種順序。

MCS逆序、LexBFS逆序、LexDFS逆序,檢查是否為完美消除順序。挑一種檢查即可。

ICPC 2424 6308

延伸閱讀:各種遍歷演算法的關聯

       GEN
      / | \
   BFS MNS DFS
    | / | \ |
LexBFS MCS LexDFS

MNS系統可以用來找到完美消除順序。

interval graph

interval graph

(G == interval) iff (G == chordal && ~G == comparability)
if (G == interval) then (G == chordal)
if (G == interval) then (~G == comparability)

ICPC 2326

circular-arc graph

ICPC 4274

split graph

split graph

(G == split) iff (G == chordal && ~G == chordal)
(G == split and G == permutation) iff (G == interval and ~G == interval) 

延伸閱讀:弦圖推廣成有向圖

我不清楚是否有人研究。「弦」可能有兩種定義:

一、一個有向環,不相鄰兩點之間的有向邊。

二、一雙有向路徑,橫跨路徑的有向邊。

一個有向環,從弦切開,形成一個有向環、一雙有向路徑。只能遞迴其中一邊。怪怪的。

一雙有向路徑,從弦切開,形成兩雙有向路徑,但是重疊於弦。怪怪的。

延伸閱讀:完美消除順序推廣成有向圖

修改單體點的定義:該點若有入邊ji與出邊ik,則必有邊jk。

「單調遞移圖monotone transitive graph」就是擁有「完美消除順序」的圖。反之亦然?【尚待確認】

chain graph

chain graph

二分圖,X群(Y群)存在一種點順序:當前點的鄰居,包含之後所有點的鄰居。

(G == chain) iff (G == bipartite && C(G) == chordal)
C(G): make X and Y cliques

《Computing the Minimum Fill-In is NP-Complete》

strongly chordal graph

strongly chordal graph