Grafo dengiantysis medis


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ždavinys
  • Microsoft Word 428 KB
  • 2012 m.
  • 5 puslapiai (686 žodžiai)
  • Universitetas
  • Milda
  • Grafo dengiantysis medis
    10 - 2 balsai (-ų)
Grafo dengiantysis medis. (2012 m. Birželio 04 d.). https://www.mokslobaze.lt/grafo-dengiantysis-medis.html Peržiūrėta 2018 m. Vasario 25 d. 00:06
×