支配

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

一些相关概念：

• 我们说一个节点 d 严格控制节点n，当且仅当 d控制 n 而不等于 n。
• 节点 n 的最近必经点（immediate dominator），简称 idom 是一个独特的节点，它严格支配节点 n，却不支配任何严格支配节点n的其他节点。不是所有的节点均有最近必经点，如开始节点就没有。
• 一个节点 d 的可支配边界是一个点集，其中任意节点n均满足， d 能严格支配所有节点u（(u,v)是图中的一条有向边），却不能严格支配 n。就是 d 支配能力的极限。
• 一个支配树是一棵树，它的所有节点儿子是被其最近支配的所有节点。由于最近必经点是唯一的，故其为一棵树，开始节点即为树根。
• 求解支配树一般使用 Tarjan 算法

图论