A feszítő fát adó eljárásban két helyen van választási lehetőségünk: ott, hogy melyik xk-t választjuk és ott, hogy ha már kiválasztottuk, melyik korábban kiválasztott xi szomszédjával kötjük össze. Ennek megfelelően általában többféle feszítő fát tudunk kiválasztani és erre többféle eljárás ismert. Most ezek közül ismertetünk néhányat.
DEFINICIÓ:
Definiáljuk egy gráf pontjai közötti távolság fogalmát: Két pont távolságán a köztük a gráfban futó legrövidebb út hosszát értjük. (Ha a két pont között nem fut út a gráfban, akkor távolságukat értelmezhetjük végtelennek.)
Az alábbi ábrán például a b pont egyaránt kettő távolságra van az a, c, e pontoktól, a d ponttól viszont három távolságra van. Az a és e pont távolsága is három. Érdemes meggondolni, mely pontok távolsága változik, ha a gráfból elhagyjuk az fc élt.
10. feladat:
Van-e olyan faváza minden összefüggő gráfnak, amely „megtartja” bármely két pont távolságát, azaz, ha a és b távolsága a gráfban d, akkor ugyanennyi a távolsága a favázban is?
| TARTALOMJEGYZÉK |