Question

Reachability

把一张图想像成道路地图，把图上的点想像成地点，把图上的边想像成道路。现在我们在意的是：由某一个地点开始，沿著道路不断行进，可以到达哪些地点？

从起点开始，使用 Graph Traversal，就可以找出所有可以到达的地点。

Connected（Reachable）

“连通”是一个形容词，是指“有路可通”的意思。

对于一张图上的两个点来说，双向都有路可通，这两个点就“连通”。

在无向图当中，两个点之间边边相连，就形成“连通”。在有向图当中，要注意边的方向，如果两个点之间，双向都有路可通，就是“强连通”；至少单向有路可通（也可以双向都通），就是“弱连通”。

Graph Traversal 或者 Transitive Closure 都可以判断连通。

Transitive Closure

Transitive Closure

一张图的“递移闭包”也是一张图，用来记录由一点能不能走到另一点的关係，如果能走到，则两点之间以边相连。

只要对图上每一个点都做一次 Graph Traversal，就可以求出“递移闭包”了。

时间複杂度为 V 次 Graph Traversal 的时间。图的资料结构是 adjacency matrix 时，时间複杂度为 O(V^3)；图的资料结构是 adjacency lists 时，时间複杂度为 O(VE)。

UVa 10926

Transitive Closure: Matrix Multiplication

楔子

把一张图想像成道路地图，把图上的点想像成地点，把图上的边想像成道路。现在我们在意的是：由某一点开始，走过 N 条道路后，可以到达哪些点？

最简单的莫过于走过零条道路的情况了，哪裡都去不了。至于走过一条道路的情况，可以到达起点附近的点。

【注：读过 Shortest Path 章节的读者，应该很快就会联想到：由一点到另一点最少需要走过几条道路。但是这和此处所言并不相同。】

当 N 很大时，各位可能会想到用 Graph Traversal 来试试看──可是路线是环的话就没辙了。环经过同一个点很多次，而 Graph Traversal 只能拜访一个点一次。

UVa 10681

走一步是一步，Incrememtal Method

要找出一张图的 Transitive Closure，也就是要找出图上每一个点，走了一条、两条、…… 、无限多条道路之后，会到达图上哪些点。

然而，一张图上最多只有 V 个点，要从一点走到另一点，走 V-1 条道路之内一定到得了，否则不论走多少条都一定到不了。

因此，要找出一张图的 Transitive Closure，只要找出图上每一个点，走了一条、两条、…… 、V 条道路之后，会到达图上哪些点就可以了。

找出所有中继站，拉出新路线，Enumeration

如果一张图上，由 i 点可以走到某一个 j 点、这个 j 点又可以走到 k 点，那麽就可以由 i 点走到 k 点。

穷举所有可能的 j 点，就可以判断出由 i 点是否能走到 k 点了！

只要计算一下图上每一个 i 点和每一个 k 点，就可以知道图上各个点可以走到哪裡去了。不过这只能找出走了两条道路的情况。

p2(i, k) = ( p1(i, 0) AND p1(0, k) ) OR
           ( p1(i, 1) AND p1(1, k) ) OR
           ...                       OR
           ( p1(i, 9) AND p1(9, k) )

pN(i, k)：由 i 点能不能走到 k 点，恰走了 N 条道路的时候。

两条加一条就是三条，三条加一条就是四条。走了三条道路、走了四条道路等等的情况，可以以逐次加一条道路的方式，慢慢累积而得。

pN+1(i, k) = ( pN(i, 0) AND p1(0, k) ) OR
             ( pN(i, 1) AND p1(1, k) ) OR
             ...                       OR
             ( pN(i, 9) AND p1(9, k) )

pN(i, k)：由 i 点能不能走到 k 点，恰走了 N 条道路的时候。

矩阵相乘，Modeling

i 点到 j 点，j 点到 k 点，穷举所有 j 点──其实就和矩阵乘法的规则一样。如果把一张图储存成 adjacency matrix，那麽直接拿这张图的 adjacency matrix 自己乘上自己，并且把加法改成 OR 运算，乘法改成 AND 运算，相乘的结果就是走过两条道路的情况了！

同理，走了两条道路的矩阵，再乘上一次原图的 adjacency matrix，就会成为走了三条道路的情况。如此一来，若要求走了 N 条道路的情况，就是原图的 adjacency matrix 的 N 次方。

演算法，Iterative Method

现在回头谈 Transitive Closure 要怎麽求。既然一张图的 Transitive Closure 只需要找出走了一条、两条、…… 、V 条道路的情形，所以一张图的 Transitive Closure 就是此图的 adjacency matrix 的 1 次方、2 次方、…… 、V 次方，然后统统 OR 起来就对了。

由于 OR 的性质，事实上还可以一边 OR 矩阵、一边乘矩阵，结果仍会正确。

p1~N+1(i, k) = p1~N(i, k)                  OR
               ( p1~N(i, 0) AND p1(0, k) ) OR
               ( p1~N(i, 1) AND p1(1, k) ) OR
               ...                         OR
               ( p1~N(i, 9) AND p1(9, k) ) OR

p1~N(i, k)：由 i 点能不能走到 k 点，当走了 1 条、2 条、…… 、N 条道路的时候。

矩阵的 V 次方，可参考本站文件“ Matrix ”，藉由 Divide and Conquer 便能以 O(logV) 次矩阵乘法求得。矩阵相乘一般需时 O(V^3)，当然还可以更快。

另外这个方法也可以用来计算从一点走到另外一点，走了 N 步之后总共有几种走法。各位可以想想看。

Transitive Closure: Warshall's Algorithm

把两点之间的所有路线，依照中继点来分类

一条路线的中继点，可能有第 0 点、第 1 点、…… 第 V-1 点。现在把 i 点到 j 点的路线分成两种：经过第 V-1 点、未经过第 V-1 点。接著两种再各自细分为：经过第 V-2 点、未经过第 V-2 点。如此不断细分下去直到：经过第 0 点、未经过第 0 点。

tc(i, j, k) = tc(i, k, k-1) && tc(k, j, k-1) || tc(i, j, k-1)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^    ^^^^^^^^^^^^^
              经过第 k 点                         没有经过第 k 点

tc(i, j, k)：由 i 点能不能走到 j 点，当中继点只能是第 0 点到第 k 点的时候。

过程可以想成是一次增加一个中继点，随时更新所有路线。

採用 Dynamic Programming，时间複杂度是 O(V^3)，空间複杂度可以精简至 O(V^2)。

Transitive Closure: Divide and Conquer

精简掉不必要计算的地方，去掉强连通分量

环上的点肯定是相互连通，可以免算 Transitive Closure。因此可以直接收缩图上所有环，再去找 Transitive Closure。没有环的图有很强的性质。

把图分作两部分，Divide and Conquer

精简过后的图进行 Topological Sort，然后将所有点依照顺序先后，分成前半群和后半群。这时便可以轻易的递迴求得这两群点的 Transitive Closure，也可以轻易的求得前半群往后半群的递移情况。

精简过后的图进行 Topological Sort，其 adjacency matrix 会呈现一个可爱的上三角矩阵。将此矩阵切成四份，前半群点的 Transitive Closure 是左上角矩阵，后半群点的 Transitive Closure 是右下角矩阵，前半群往后半群的递移情况是右上角矩阵。

演算法

一、收缩图上所有环。
　　例如使用收缩图上所有 Strongly Connected Component 的演算法。
二、进行拓扑排序（图上无环），以利 Divide and Conquer 将图分成两部分。
三、把排序结果分成前半和后半两群点，分别递迴计算这两群点的递移闭包。
四、于 Divide and Conquer 的合併阶段，计算前半群走到后半群的递移情况。
　　至于由后半群往前半群是没有道路的，因为拓扑排序。

1. 令 G 为精简过后的图的 adjacency matrix。
   G 均分成四份，左上为 A，右上为 T，左下为 0 矩阵，右下为 B。
2. 递迴求出 A*。递迴求出 B*。
3. G*均分成四份，左上会是 A*，右上会是 A*TB*，左下会是 0 矩阵，右下会是 B*。

时间複杂度正比于矩阵相乘的时间複杂度。

http://www.student.cs.uwaterloo.ca/~cs466/Old_courses/F08/transitiveClosure.pdf

延伸阅读：分成前中后三群

当图的构造特殊时，刚好可以分成三群，而且只有前群到中群、中群到后群的边，便可以使用此式子。

1. 令 G 为图的 adjacency matrix。
   G 均分成九份，上为 A，右为 B，其馀皆为 0 矩阵。
2. G*均分成九份，上仍为 A，右仍为 B，右上为 AB，
   左上、中、右下为单位矩阵，其馀皆为 0 矩阵。

延伸阅读：直接 Divide and Conquer

这裡再提供一个完全不用求 Strongly Connected Component，就可以直接做 Divide and Conquer，其原理是以集合为单位来求 Transitive Closure。时间複杂度正比于矩阵相乘的时间複杂度。

1. 令 G 为图的 adjacency matrix。
   G 均分成四份，左上为 A，右上为 B，左下为 C，右下为 D。
2. 递迴求出 D*。
3. 令 E = A + BD*C，并且递迴求出 E*。
4. G*均分成四份，左上会是 E*，右上会是 E*BD*，左下会是 D*CE*，右下会是 D* + D*CE*BD*。

Connectivity

Regular Graph / Factor

无向图当中，“Regular Graph”是每一点都连著一样多的边的图；“Factor”是每一点都连著一样多的边的子图。

简而言之：每个点的度数都一样的图、子图。

我们可以在名称开头冠上数字、横槓，明确呈现度数。例如 1-Regular Graph 是每个点都连著一条边的图，2-Factor 是每个点都连著两条边的子图。

Complete Graph / Clique

无向图当中，“完全图 Complete Graph”是所有两点之间都有一条边的图；“团 Clique”是所有两点之间都有一条边的子图。

简而言之：每个点的度数都是 V-1 的图、子图。

Degree

无向图当中，一个点的“度 Degree”，就是碰触邻边的次数。没有自环的情况下，“度 Degree”等于邻边数量。

有向图当中，可以进一步细分为“入度 In-degree”与“出度 Out-degree”，分别是指入边的数目、出边的数目。

“度”可以呈现一个点与其他点的联繫强度。

有向图当中，因为每条边都是有始有终，所以整张图的入度总数目必等于出度总数目。

无向图当中，以边为主角，每条边碰到两个点。所有碰到的点的度数加起来，就是边数的两倍。换句话说，整张图的度数总和必等于边数的两倍。

UVa 12035

给定各点 degree 求原图（Erdos-Gallai Theorem）

http://mathworld.wolfram.com/GraphicSequence.html

小游戏： http://armorgames.com/play/5900/king-of-bridges

小游戏： http://www.agame.com/game/connectors.html

求得其中一种可能性，时间複杂度 O(V^2)。

UVa 10720 11414

给定各点 degree 求原图（Havel-Hakimi Algorithm）

度数按照大到小排序
d1 d2 d3 ... is graphical
iff d2-1 d3-1 ... dd1+1-1 dd1+2 dd1+3 dd1+4 ... is graphical
    |-------- d1 -------|

求得其中一种可能性，时间複杂度 O(V^2)。

Oriented Graph

一张无向图，无向边改成有向边，称做“定向图”。替每一条边选择一个方向，称作“定向 Orientation”。

根据 Robbins' theorem，没有桥的无向图，一定能改成强连通的 Orientation，反之亦然。

UVa 610 10972

Graph Width（Under Construction!）

Graph Width

http://mathsci.kaist.ac.kr/~jisujeong/jisu_grow2015.pdf
http://link.springer.com/article/10.1007/s00453-015-0033-7

Tree Decomposition

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

Partial k-Tree

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

UVa 12615

Clique Tree

ICPC 7458

Tree Root

http://www.csie.ntu.edu.tw/~hil/paper/swat06.ppt

Similiarity（Under Construction!）

Similarity

两棵树的距离：

Edit Distance
Rotation Distance
Chain Rotation Distance