支配 (图论)

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

大概步骤

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

1. 对图进行DFS（深度优先遍历）并求出搜索树和DFS序。这里用 ${\displaystyle dfn[x]}$ 表示点 ${\displaystyle x}$ 在dfs序中的位置。
2. 根据半必经点定理计算出所有的半必经点作为计算必经点的根据
3. 根据必经点定理修正半必经点，求出支配点。

半必经点

用 idom[x] 表示点 ${\displaystyle x}$ 的直接支配节点，用 semi[x] 表示点 ${\displaystyle x}$ 的半必经点。

那什么是半必经点呢？

對於一個節點 ${\displaystyle Y}$ ，存在某個點 ${\displaystyle X}$ 能夠通過一系列點 ${\displaystyle p_{i}}$ （不包含 ${\displaystyle X}$ 和 ${\displaystyle Y}$ ）到達點 ${\displaystyle Y}$ 且 ${\displaystyle \forall i\ dfn[i]>dfn[Y]}$ ，就稱 ${\displaystyle X}$ 是 ${\displaystyle Y}$ 的半必經點，記做 semi[Y]=X

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

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

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

• 对于一个节点 ${\displaystyle Y}$ 考虑所有能够到达它的节点，设其中一个为 ${\displaystyle X}$ 
• 若 ${\displaystyle dfn[X]<dfn[Y]}$ ，则 ${\displaystyle X}$ 是 ${\displaystyle Y}$ 的一个半必经点

• 若 ${\displaystyle dfn[X]>dfn[Y]}$ ，那么对于 ${\displaystyle X}$ 在搜索树中的祖先 ${\displaystyle Z}$ (包括 ${\displaystyle X}$ )，如果满足 ${\displaystyle dfn[Z]>dfn[Y]}$ 那么 semi[Z] 也是 ${\displaystyle Y}$ 的半必经点

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

1. ^ Prosser, Reese T. Applications of Boolean matrices to the analysis of flow diagrams. AFIPS Joint Computer Conferences: Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference (Boston, MA: ACM). 1959: 133–138. 
2. ^ Lowry, Edward S.; and Medlock, Cleburne W. Object code optimization. Communications of the ACM. January 1969, 12 (1): 13–22.  引文使用过时参数coauthors (帮助)
3. ^ Cytron, Ron; Hind, Michael; and Hsieh, Wilson. Automatic Generation of DAG Parallelism. Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation. 1989: 54–68. CiteSeerX: 10.1.1.50.9287 .  引文使用过时参数coauthors (帮助)

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