Dominance (graf)

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
Červeně jsou označeny dominující vrcholy grafu

Dominancí grafu označujeme mohutnost minimální dominující množiny uzlů. Dominující množinou je taková množina uzlů, která svou množinou sousedních uzlů pokrývá všechny zbývají uzly grafu.

Reference[editovat | editovat zdroj]

  • KOLÁŘ, Josef. Teoretická informatika. Praha: [s.n.], 2004. ISBN 80-900853-8-5. Kapitola 3.1, s. 41.