Dominator (grafteori)
Utseende
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 | |||||
Korresponderende dominator-relasjoner | |||||||
Grå noder er ikke strengt dominert | |||||||
Røde noder er umiddelbart dominert |
En dominator er innen informatikken en spesiell type kontrollflytgraf hvor en node d dominerer en node n hvis enhver sti fra inngangsnoden til n må gå gjennom d. Dette betegnes som d dom n, eller noen ganger som d n. Enhver node dominerer per definisjon seg selv.
Det finnes en rekke relaterte konsepter:
- En node d dominerer strengt en node n hvis d dominerer n og d ikke er lik n.
- Den umiddelbare dominator eller idom til en node n er den unike node som strengt dominerer n men ikke strengt dominerer noen annen node som strengt dominerer n. Enhver node, bortsett fra inngangsnoden, har en umiddelbar dominator.[1]
- Dominance frontier til en node d er mengden med noder n slik at d dominerer en umiddelbar forgjenger til n, mens d ikke strengt dominerer n. Det er mengden med noder hvor d's dominans stanser.
- Et dominatortre er et tre hvor hver node's barn er de noder det umiddelbart dominerer. Fordi den umiddelbare dominator er unik, er det et tre. Startnoden er roten til treet.
Referanser
[rediger | rediger kilde]- ^ Lengauer, Thomas; and Tarjan; Robert Endre (juli 1979). «A fast algorithm for finding dominators in a flowgraph». ACM Transactions on Programming Languages and Systems. 1 (1): 121–141. doi:10.1145/357062.357071.