支配 (圖論)

1  dom          3  4  5  6 2  dom           5   3  dom                  4  dom                  5  dom                  6  dom                  支配关系图  表示非严格支配  表示直接支配

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

一些相關概念：

 说一个节点 d 严格支配节点n，当且仅当 d支配 n 而不等于 n。
 节点 n 的直接支配节点（immediate dominator），简称 idom 是一个独特的节点，它严格支配节点 n，却不严格支配任何严格支配节点n的其他节点。不是所有的节点均有直接支配节点，如开始节点就没有。
 一个节点 d 的可支配边界是一个点集，其中任意节点n均满足， d 能支配 n 的前驱结点，却不能严格支配 n。就是 d 支配能力的极限。
 一个支配树是一棵树，它的所有节点儿子是被其直接支配的所有节点。由于直接支配节点是唯一的，故其为一棵树，开始节点即为树根。
求解支配树一般使用 Tarjan 算法

 求解支配树的一般方法 
一般而言，会使用 Tarjan 算法在 的时间内将其求出

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

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

 半必經點 
用 idom[x] 表示點 的直接支配节点，用 semi[x] 表示點 的半必經點。

那什麼是半必經點呢？
 對於一個節點 ，存在某個點 能夠通過一系列點 （不包含 和 ）到達點 且 ，就稱 是 的半必經點，記做 semi[Y]=X
當然一個點的“半必經點” 會有多個，而且這些半必經點一定是搜索樹中點 的祖先。

對於每個點，只需要保存其半必經點中最小的一個，下文中用表示點的半必經點中值最小的點的編號。

可以更書面一點的描述這個定理：

 對於一個節點 考慮所有能夠到達它的節點，設其中一個為 
 若 ，則 是 的一個半必經點

 若 ，那麼對於 在搜索樹中的祖先 (包括 )，如果滿足 那麼 semi[Z] 也是 的半必經點

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