支配

在计算机科学中，控制流图的一个节点 d 支配节点 n，当且仅当从开始节点（可以理解为源）到节点 n的每一条路径均要经过节点d，写作d dom n (一写作d ${\displaystyle \gg <!--\; \gg \; -->}$ n)。根据上述定义，容易得到每个节点均控制其自身。

一些相关概念：

一般而言，我们会使用 Tarjan 算法在 ${\displaystyle O(|V|+|E|)}$的时间内将其求出

首先来介绍一些这个算法的大概步骤

我们用 idom 表示点 ${\displaystyle x}$的最近支配点，用 semi 表示点 ${\displaystyle x}$的半必经点。

那什么是半必经点呢？

对于一个节点 ${\displaystyle Y}$，存在某个点 ${\displaystyle X}$能够通过一系列点 ${\displaystyle p_i}$（不包含 ${\displaystyle X}$和 ${\displaystyle Y}$）到达点 ${\displaystyle Y}$且 ${\displaystyle \mathrm{\forall <!--\; \forall \; -->}idfn>dfn}$，我们就称 ${\displaystyle X}$是 ${\displaystyle Y}$的半必经点，记做 semi=X

当然一个点的“半必经点” ${\displaystyle X}$会有多个，而且这些半必经点一定是搜索树中点 ${\displaystyle X}$的祖先。

对于每个点，我们只需要保存其半必经点中最小的一个，下文中用表示点的半必经点中值最小的点的编号。

我们可以更书面一点的描述这个定理：

计算机科学中支配的概念第一次被提出是在Reese T. Prosser在1959年一篇关于流网络的论文中提出的 而在此论文中，Prosser并未提出一种有效算法以计算支配关系,解决这一问题的有效算法直到十年后才被 Edward S. Lowry and C. W. Medlock 提出。Ron Cytron等人在1989年将其应用于高效计算应用于静态单赋值形式的φ 函数时对其重新燃起了兴趣。

4.https://blog.csdn.net/a710128/article/details/49913553