Dominator (grafteori)
| 1 | dom | Mal:Color | Mal:Color | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 2 | dom | Mal:Color | Mal:Color | Mal:Color | Mal:Color | Mal:Color | |
| 3 | dom | Mal:Color | |||||
| 4 | dom | Mal:Color | |||||
| 5 | dom | Mal:Color | |||||
| 6 | dom | Mal:Color | |||||
| Korresponderende dominator-relasjoner | |||||||
| Mal:Color er ikke strengt dominert | |||||||
| Mal:Color 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.