Question

Clique

“团”。

Maximal Clique / Maximum Clique

Minimal、Maximal 是区域极值，Minimum、Maximum 是全域极值。遣词用字请特别小心！

“极大团 Maximal Clique”是无法直接增加顶点数目的团，可能有许多个。

“最大团 Maximum Clique”是顶点数目最多的团，可能有许多个。最大团是所有极大团当中最大的；最大团也是极大团。

列举 Maximal Clique（Bron-Kerbosch Algorithm）

寻找最大团是 NP-complete 问题，没有快速的演算法。因此，列举所有的 Maximal Clique，从中找到 Maximum Clique，不失为一个务实的方法。

http://en.wikipedia.org/wiki/Bron–Kerbosch_algorithm

R: 目前的 clique。
P: 可以增大目前 clique 的点集合。接下来要列举的点。
　（与目前 clique 上所有点皆相邻的点，构成的集合）
X: 可以增大目前 clique 的点集合，但是先前已经列举过。用来避免重複列举。

此演算法採用 backtracking。改变列举顺序、调整 pruning 方式，就会得到不同的时间複杂度。

阳春版本的时间複杂度是 O(n*3^(n/3))。

选择适当的 pivot，让各阶段列举的点都是最少，时间複杂度加速为 O(3^(n/3))。

点的列举顺序採用 degeneracy order，时间複杂度加速为 O(d*n*3^(d/3))，其中 d 是原图的 degeneracy。

下面提供的实作是随意选择 pivot，稍微减少列举的点。

Chordal Graph（Under Construction!）

Hole

“环”是串成一圈的路线，没有重複的点。

“洞”是一种特别的“环”，没有“弦”。

“弦”可以想成是环上的捷径，用来找到长度更小的环。“洞”可以想成是区域极小值、区域极小环。

ICPC 7661

Chordal Graph

“弦图”。多于三条边的环，必有一条弦。换句话说，没有多于三条边的洞。

弦图的外观是由很多三角形交错叠合而成。顺带一提，学过“ 三角剖分 ”的读者要特别当心，三角剖分通常不是弦图。

弦图随便删除几个点（以及连带的边），仍是弦图。换句话说，弦图的生成子图是弦图。

森林、有向无环图、二分图、弦图，都具有这种递归性质。

“森林”和“有向无环图”没有环，“二分图”没有奇环，“弦图”没有多于三条边的洞。弦图也是十分重要的特例，往往存在速度极快的演算法。至于现实生活中有哪些弦图，没人研究。

Perfect Elimination Ordering（Under Construction!）

Perfect Elimination Ordering

有向无环图拥有“拓朴顺序”。弦图拥有“最佳消除顺序”。

弦图边数很多、密度很高。弦图至少有一个点，此点暨所有邻居，形成“极大团 Maximal Clique”。【待补证明】

举例来说，连接零条边、一条边的点，一定是这样一个点。关节点，一定不是这样一个点。

删除这样一个点，即是令其所属的极大团的大小减一。

弦图删除任何一点之后仍是弦图，可以递迴下去。“最佳消除顺序”就是逐次删除这样一个点，所得到的顺序，通常有许多种。

有向无环图必有拓朴顺序，反之亦然。弦图必有最佳消除顺序，反之亦然。

chordal <=> 存在随便一个 PEO （其实是一大堆 PEO，通常不只一个 PEO）

 (=>) 前面提到的。
 (<=) 假设有个环="">=4  然后 PEO 最早出现在环上的点是 v。
      因为 N(v) 是 clique，所以 N(v) 都有边，所以这环必有弦。

“拓朴顺序”可以想成先后次序。“最佳消除顺序”意义不明，尚待各位赋予意义。说实在话，这个名称，词不达意。

ICPC 2424 6308

找出一个最佳消除顺序

有向无环图，特殊 BFS 顺序、DFS 逆序，都是其中一种拓朴顺序。

弦图，MCS 逆序、LexBFS 逆序、LexDFS 逆序，都是其中一种最佳消除顺序。证明分为两步骤：

一、遍历过程当中，凡是遇到团、必是连续拜访。因此，最后拜访的点，必是极大团的点，该点暨所有邻居必是极大团。

二、遍历过程当中，不受未拜访点的影响。换句话说，一张图删除最后一个拜访的点，重新实施遍历演算法，遍历顺序依然相同。删除最后一个拜访的点，递迴下去，证明完毕。

Chordal Graph Recognition
= Perfect Elimination Ordering Verification

检查一张图是不是弦图，方法很简单：弦图必有最佳消除顺序！

更进一步来说，弦图的 MCS 逆序、LexBFS 逆序、LexDFS 逆序必是最佳消除顺序。挑其中一个检查即可。【待补证明】。时间複杂度 O(V+E)。

逆跑 PEO ，当前点 v 的上一点 w。
在已拜访点之中，检查 w 的邻点是否连到所有 v 的邻点。
如此一来 N(v) 可以形成 clique。
递推，数学归纳法。

检查过程可以併入 MCS、LexBFS、LexDFS 当中，一边遍历一边检查。

Graph Traversal（Under Construction!）

Graph Traversal

除了 BFS、DFS，再补充三个遍历演算法 MCS、LexBFS、LexDFS。这三个遍历演算法，目前只用来找到团，尚未发掘其他功效。

Maximum Cardinality Search（MCS）

每回合找到一个点，连往已拜访点的边数最多。如果很多点同时符合条件，则任选一点。

时间複杂度 O(V^2)。运用 Binary Heap 得压至 O(V+ElogV)。运用 Fibonacci Heap 得压至 O(E+VlogV)。

边数总是加一。藉由特殊的资料结构，迅速找到最大值。时间複杂度可以压至 O(V+E)。

Lexicographic Breadth-first Search（LexBFS）

i from v-1 to 0
取字串最大的点。
所有未拜访邻居，字串尾端添加 i。

新版 BFS，仔细安排小孩的拜访顺序：凡是小孩形成团、必是连续拜访。

时间複杂度 O(V^2)。运用前述特殊资料结构得压至 O(V+E)。

LexBFS-：当字串一样大，优先拜访索引值较小的点。

Lexicographic Depth-first Search（LexDFS）

i from 0 to v-1
取字串最大的点。
所有未拜访邻居，字串开头添加 i。

新版 DFS，仔细安排子孙的拜访顺序：凡是子孙形成团、必是连续拜访。

时间複杂度 O(V^2)。运用 Binary Heap 得压至 O(V+ElogV)。运用 vEB Tree 得压至 O(V+EloglogV)。

LexDFS+：当字串一样大，优先拜访索引值较大的点。

各种遍历演算法的关联

http://www.lix.polytechnique.fr/~liberti/pretty_structures/pdf/habib-ps11.pdf

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

MNS 系统可以找出一个最佳消除顺序。

Comparability Graph（Under Construction!）

Comparability Graph

“可比图”，DAG 的 Transitive Closure 的 Oriented Graph，概念源自集合论的 Poset。

可比图边数很多、密度很高。数学家常常用团的思维去看待可比图。检查一张图是不是可比图，LexDFS+，时间複杂度 O(V+E)。

《Linear Time LexDFS on Cocomparability Graphs》

延伸阅读：Total Order / Partial Order

集合论有两个常见的概念“全序”和“偏序”。

一个集合，拥有“全序”：所有元素，都可以两两互相比较。

一个集合，拥有“偏序”：只有部分元素，可以两两互相比较，而且必须满足一些性质：

1. a ≤ a                         (reflexivity)     [自己可以和自己比]
2. if a ≤ b and b ≤ a then a = b (antisymmetry)
3. if a ≤ b and b ≤ c then a ≤ c (transitivity)    [前三点建构出偏序]
4. either a ≤ b or b ≤ a         (comparability)   [前四点建构出全序]

集合论的建构方式，图论的建构方式，两者思路完全不同，名词意义也有衝突。图论的观点，全序是 Complete Graph 添上 Loop，偏序是 Comparability Graph 添上 Loop。

偏序可以精简地画成 Hasse Diagram，一个 DAG。

延伸阅读：Dominance

所谓的“比较”可以是：是否大于（元素是数字）、是否覆盖（元素是区间）、是否包含（元素是集合）。

数学的名词，经常是一个泛称（抽象，抽取大致的模样），实际内容可以抽换（具现，呈现具体的事物）。

既然可以比较，就可以分高下、定优劣。宏观望去，就是“序 order”。

order 和 ordering 意义不太一样。order 是两两关係，是一个 graph。ordering 是一条龙顺序，是一个 permutation，或者简单想成一个数列。一个 order 通常可以撷取很多种 ordering。

LIS/LCS/凸包/maximal layer/interval coverage/排序/poset
dominating point -> dominating inteval -> segment tree

(x1,y1) dominates (x2,y2) iff x1 >= x2 and y1 >= y2

variable change: let a = -x, b = y
(a1,b1) covers    (a2,b2) iff a1 <= a2="" and="" b1="">= b2

variable change: let idx1 = a1, idx2 = b1, v1 = a2, v2 = b2
(idx1,idx2) (v1,v2) are inversion pairs iff idx1 < idx2 and v1 > v2

UVa 11020 Timus 1078

Dilworth's Theorem

有向无环图 DAG 有两个特殊性质，在偏序集、可比图才有显著功用，因而挪到此处介绍。

max length of chain = min cover of anti-chain
[DFS depth]           [each BFS level is anti-chain]

(=>) 一条 DFS path，每一个点至少需要一条 anti-chain。
     一条 anti-chain 没办法同时穿过两个点以上。
(<=) 每一个 level 至少一条 anti-chain。="" <="" pre="">

实际应用，例如可比图的 Minimum Vertex Coloring：简图的一条路径，经由 Transitive Closure，其实是原图的一个团──所有点互相连通，每一点颜色必须不同。因此简图的最长路径长度，就是原图的最小点著色的大小。

min cover of chain = max length of anti-chain
[# of DFS path]      [cross all path]

实际应用，例如可比图的 Maximum Independent Set：简图的一条路径，经由 Transitive Closure，其实是原图的一个团──只够塞入一点，塞入两点就相邻。因此简图的相异路径数目，就是原图的最大独立集的大小。

Sphere DIVREL

Greene-Kleitman Theorem

Dilworth's Theorem 推广版本，跟数论的“ Partition ”有关。我没有研究。

https://www.math.ku.edu/~jmartin/courses/math796-S08/notes0402.pdf

Permutation Graph

if (G == comparability && ~G == comparability) then (G == permutation)
if (G == permutation) then (~G == permutation)

ICPC 6508

Interval Graph（Under Construction!）

Interval Graph

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

[old-fashioned algorithm]
for each vertex,
find all maximal cliques containing the vertex,
see if their id are consecutive.
use PQ tree.

[simple algorithm]
http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf
determine comparability -> O(V + ElogV)
determine interval -> O(V + E)

[newest algorithm]
three special LexBFS
http://math.sjtu.edu.cn/faculty/ykwu/data/Talk/20101030.pdf

ICPC 2326

Circular-arc Graph

ICPC 4274

Chain Graph（Under Construction!）

Chain Graph

二分图，X 群（Y 群）的一个节点顺序，其中任何一点的邻点，包含之后所有点的邻点。

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

A bipartite graph is a chain graph if and only if
it does not contain a pair of independent edges.

Let G be a bipartite graph.
C(G) is chordal if and only if G is a chain graph.
C(G): make X and Y cliques

Cograph

http://en.wikipedia.org/wiki/Cograph

《A Simple Linear Time LexBFS Cograph Recognition Algorithm》

ICPC 3666 7462

Probe Graph

Definition 2
Let V be a vertex set of undirected graph, and P be a subset of V.
Then G(V,P,E) denotes a probe graph if its edge set E ⊂ (P × V).
The elements of P are called probes.

P 自由连  P 到 V-P 自由连  V-P 无边  全部连满有点像王冠

Perfect Graph

Perfect Graph

树、森林、有向无环图（不含环），二分图（不含奇环），弦图（不含长度大于 3 的洞），完美图（不含长度大于 3 的奇洞）。这一路上的变化，就是尽量没有环。

每一个导出子图，最小著色数皆等于最大团点数，就是完美图。 (1961)
原图和补图要嘛同时是完美图，要嘛同时不是完美图。 (1972)
原图暨补图都不含长度大于 3 的奇洞，就是完美图。 (2002)

完美图的补图是完美图。完美图随意删去一些点（以及所有邻边），仍是完美图，具有递归的性质。

Perfect Graph Recognition

判断一张图是否是完美图，2003 年首次出现了多项式时间演算法，时间複杂度 O(V^9)。尚在进化当中！

Minimum Vextex Coloring in Perfect Graph

原图的 Vertex Coloring、补图的 Clique Cover，一一对应。

原图的 Clique、补图的 Independent Set，一一对应。顺带一提 Independent Set 和 Vertex Cover 互补。

一般图的情况下，上述两组东西没有直接关联。完美图的情况下，这两组东西被绑在一起了──但是只有极值而已：

  |Minimum Vertex Coloring in G| = |Minimum Clique Cover in G|
= |Maximum Clique in G| = |Maximum Independent Set in G|

我只知道极值是相等的，但是不知道是如何相互对应的。

要求出这五个东西，有著 O(V+E) 线性规划演算法。目前还没有纯粹的图论解法。

Perfectly Ordered Graph

可以用 greedy 演算法进行点著色的图。时间複杂度 O(V+E)。

弦图本身也有线性时间演算法可以求出  最小点著色/最小图覆盖/最大团/最大独立集
首先找出一个 PEO
[Maffray 2003] 弦图的任何一个 PEO 颠倒过来  用 greedy 著色  必定得到最小点著色

Skew Partition

http://en.wikipedia.org/wiki/Skew_partition