支配树

在有向图 G 中，存在源点 s，若从 s 出发的到达点 y 的路径都经过点 x，称 x 支配 y。

注意：若源点 s 有多个，则可以虚拟一个起点。

性质 1：源点 s 支配所有的点，点 x 一定支配 x 本身。

性质 2：支配的传递性，若 x 支配 y，y 支配 z，则 x 支配 z。

性质 3：若 x 支配 y，y 支配 x，则 x=y。

性质 4：若 x 支配 z，y 支配 z，则 x 和 y 之间一定存在支配关系。

定义 dom[i] 表示支配点i的点集，idom[i] 表示支配点i的点集中离i最近且不等于i的点。

性质 5：除了源点s，所有点i都有唯一的idom[i]

将i只想idom[i]即可得到一棵树，称之为原有向图的支配树。

性质 6：支配树的根节点为原图的源点s，形态唯一。

性质 7：支配树上点i的所有祖先节点，就是点集dom[i]

应用场景：无向图的必经点的分析工具是圆方树，有向图的必经点的分析工具是支配树。

DAG图的支配树：
对于DAG的拓扑序，显然拓扑序大的节点不可达拓扑序最小的节点，进而拓扑序大的点不能支配拓扑序小的点