支配 (圖論)

關於與「支配 (圖論)」標題相近或相同的條目頁，請見「支配」。

1	dom	1	2	3	4	5	6
2	dom		2	3	4	5	6
3	dom			3
4	dom				4
5	dom					5
6	dom						6
支配關係圖
灰色節點 表示非嚴格支配
紅色節點 表示直接支配

在計算機科學中，控制流圖的一個節點（基本塊） d 支配節點 n，當且僅當從開始節點（可以理解為源）到節點 n的每一條路徑均要經過節點d，寫作d dom n (一寫作d $\gg$ n)。根據上述定義，容易得到每個節點均支配其自身。

以1作為開始節點的控制流圖實例

一些相關概念：

• 說一個節點 d 嚴格支配節點n，當且僅當 d支配 n 而不等於 n。
• 節點 n 的直接支配節點（immediate dominator），簡稱 idom 是一個獨特的節點，它嚴格支配節點 n，卻不嚴格支配任何嚴格支配節點n的其他節點。不是所有的節點均有直接支配節點，如開始節點就沒有。
• 一個節點 d 的可支配邊界是一個點集，其中任意節點n均滿足， d 能支配 n 的前驅結點，卻不能嚴格支配 n。就是 d 支配能力的極限。
• 一個支配樹是一棵樹，它的所有節點兒子是被其直接支配的所有節點。由於直接支配節點是唯一的，故其為一棵樹，開始節點即為樹根。
• 求解支配樹一般使用 Tarjan 算法

求解支配樹的一般方法

一般而言，會使用 Tarjan 算法在 $O(|V|+|E|)$的時間內將其求出

大概步驟

首先來介紹一些這個算法的大概步驟

1. 對圖進行DFS（深度優先遍歷）並求出搜索樹和DFS序。這裡用 $dfn[x]$表示點 $x$在dfs序中的位置。
2. 根據半必經點定理計算出所有的半必經點作為計算必經點的根據
3. 根據必經點定理修正半必經點，求出支配點。

半必經點

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

那什麼是半必經點呢？

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

當然一個點的「半必經點」 $X$會有多個，而且這些半必經點一定是搜索樹中點 $X$的祖先。

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

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

• 對於一個節點 $Y$考慮所有能夠到達它的節點，設其中一個為 $X$
• 若 $dfn[X]<dfn[Y]$，則 $X$是 $Y$的一個半必經點

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

歷史

計算機科學中支配的概念第一次被提出是在Reese T. Prosser在1959年一篇關於流網絡的論文中提出的 而在此論文中，Prosser並未提出一種有效算法以計算支配關係,解決這一問題的有效算法直到十年後才被 Edward S. Lowry and C. W. Medlock 提出。Ron Cytron等人在1989年將其應用於高效計算應用於靜態單賦值形式的φ 函數時對其重新燃起了興趣。

參考

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