Dominator (graph theory)
http://dbpedia.org/resource/Dominator_(graph_theory) an entity of type: Thing
在计算机科学中，控制流图的一个节点（基本块） 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 算法
rdf:langString
In computer science, a node d of a control-flow graph dominates a node n if every path from the entry node to n must go through d. Notationally, this is written as d dom n (or sometimes d ≫ n). By definition, every node dominates itself. There are a number of related concepts:
rdf:langString
Die Dominanzrelation ist eine Relation, die auf den Knoten eines Kontrollflussgraphen definiert ist. Sei ein Kontrollflussgraph und seien zwei seiner Knoten. Wenn nun jeder Pfad in , der in beginnt und in endet, den Knoten beinhaltet, so sagt man, dass der Knoten den Knoten dominiert.Man schreibt auch . Im oben abgebildeten Kontrollflussgraph etwa dominiert Knoten 2 den Knoten 5, aber Knoten 3 dominiert Knoten 5 nicht, da es einen Pfad gibt, der den Knoten 3 nicht beinhaltet. Klarerweise dominiert jeder Knoten sich selbst.Daher ist die Dominanzrelation reflexiv.
rdf:langString
Доминатор в теории графов — бинарное отношение на узлах ориентированного графа с выделенным входным узлом, показывающее преимущество при прохождении пути от входного узла: узел графа доминирует над узлом (записывается как или ), если любой путь от входного узла графа к проходит через . В частности, каждый узел доминирует над самим собой. Наиболее широкое применение получили в графах потока управления, используемых в теории построения компиляторов.
rdf:langString
rdf:langString
Dominanzrelation (Kontrollflussgraph)
rdf:langString
Dominator (graph theory)
rdf:langString
Доминатор (теория графов)
rdf:langString
支配 (圖論)
xsd:integer
396116
xsd:integer
1115030812
rdf:langString
Die Dominanzrelation ist eine Relation, die auf den Knoten eines Kontrollflussgraphen definiert ist. Sei ein Kontrollflussgraph und seien zwei seiner Knoten. Wenn nun jeder Pfad in , der in beginnt und in endet, den Knoten beinhaltet, so sagt man, dass der Knoten den Knoten dominiert.Man schreibt auch . Im oben abgebildeten Kontrollflussgraph etwa dominiert Knoten 2 den Knoten 5, aber Knoten 3 dominiert Knoten 5 nicht, da es einen Pfad gibt, der den Knoten 3 nicht beinhaltet. Klarerweise dominiert jeder Knoten sich selbst.Daher ist die Dominanzrelation reflexiv. Da außerdem für aus und folgt, dass den Knoten dominiert, ist die Dominanzrelation auch transitiv. Wenn der Knoten den Knoten dominiert und , dann spricht man auch davon, dass den Knoten strikt dominiert.Man schreibt dann auch .Die strikte Dominanzrelation kann als Baum dargestellt werden.Dieser Baum wird auch Dominator-Baum (engl. dominator tree) genannt.Der obige Beispielgraph besitzt folgenden Dominator-Baum:
rdf:langString
In computer science, a node d of a control-flow graph dominates a node n if every path from the entry node to n must go through d. Notationally, this is written as d dom n (or sometimes d ≫ n). By definition, every node dominates itself. There are a number of related concepts:
* A node d strictly dominates a node n if d dominates n and d does not equal n.
* The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n. Every node, except the entry node, has an immediate dominator.
* The dominance frontier of a node d is the set of all nodes ni such that d dominates an immediate predecessor of ni, but d does not strictly dominate ni. It is the set of nodes where d's dominance stops.
* A dominator tree is a tree where each node's children are those nodes it immediately dominates. The start node is the root of the tree.
rdf:langString
在计算机科学中，控制流图的一个节点（基本块） 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 算法
rdf:langString
Доминатор в теории графов — бинарное отношение на узлах ориентированного графа с выделенным входным узлом, показывающее преимущество при прохождении пути от входного узла: узел графа доминирует над узлом (записывается как или ), если любой путь от входного узла графа к проходит через . В частности, каждый узел доминирует над самим собой. Наиболее широкое применение получили в графах потока управления, используемых в теории построения компиляторов. Полезным способом представления информации о доминаторах является дерево, именуемое деревом доминаторов, в котором входной узел является корнем, а каждый узел доминирует только над своими потомками в дереве.
xsd:nonNegativeInteger
9660
