Grafo dengiantysis medis


Matematikos uždavinys. Maximum leaf spanning tree. Grafo dengiančiojo medžio radimas.


Tai uždavinys, skirtas duotam grafui G surasti jo tokį dengiantįjį medį T, kad T turėtų maksimalų įmanomą lapų skaičių (MLST). Ši problema yra labai glaudžiai susijusi su jungiojo dominuojancio poaibio (Connected Dominating Set) problema, t.y. sudėjus gautą maksimalų lapų skaičių ir dominuojančias viršūnes, gaunasi grafo G viršūnių skaičius.

Dengiantysis medis yra pripažintas pačiu pagrindiniu subgrafu. Šiais laikais jis pagrindinę vietą užima šnekant apie daugumą tinklo dizaino bei analizės problemas. Vienas to pavyzdžių būtų MLST naudojimas norint tinkle sumažinti maršrutizatorių skaičių kažką tiekiant vartotojams, pvz interneto ar telekomunikacijos paslaugas (lapai atitinka vartotojus).

  • Matematika Uždaviniai
  • 2012 m.
  • 5 puslapiai (686 žodžiai)
  • Universitetas
  • Matematikos uždaviniai
  • Microsoft Word 428 KB
  • Grafo dengiantysis medis
    10 - 2 balsai (-ų)
Grafo dengiantysis medis. (2012 m. Birželio 04 d.). http://www.mokslobaze.lt/grafo-dengiantysis-medis.html Peržiūrėta 2016 m. Gruodžio 07 d. 16:39