10.7 A feszítő fa probléma
Egy G gráf feszítő fáján azt a feszítő részgráfot értjük, amely fa. Egy konstruktív bizonyítással belátható, hogy minden összefüggő gráfnak van feszítő fája.
Az optimalizáció-elmélet egyik ismert problémája az, hogy hogyan lehet megtalálni egy gráf valamilyen speciális tulajdonsággal rendelkező feszítő fáját.
Legyen adott a G=(V,E) gráf és egy pozitív értékű f függvény, amely a gráf élein van definiálva: . Keressük azt a T=(V,E΄) összefüggő feszítő fát, amelyre
minimális.
Az ilyen tulajdonságú feszítő részfát gazdaságos feszítő fának nevezzük. Tegyük fel, hogy számítógépeket akarunk összekötni egy hálózattá, és az egyes gépek összekötésének a költségét az alábbi gráf írja le:
11. ábra Egy számítógép hálózat építési költségeit leíró gráf
Két algoritmust mutatunk be a probléma megoldására.
Algoritmus-1: (Kruskal Algoritmus (1956)):
- Válasszuk ki a legolcsóbb élet G-ből, azaz azt az élet, amelyre f(e) minimális.
- A következő élet a még ki nem választottak közül mindig úgy választjuk, hogy az a legolcsóbb legyen. A választásnál arra kell ügyelnünk, hogy nem képezhetünk körutat a kiválasztott élekből.
- Ha ilyen él már nincs, akkor véget ér az algoritmus.
Algoritmus-2:
- Az algoritmus lényege az, hogy drága élet csak akkor szabad választani, ha biztosítani akarjuk a gráf összefüggőségét.
- Töröljük tehát a legdrágább élet a gráfból mindaddig, amíg a gráf összefüggő marad.
- Ha ilyen él már nincs, akkor véget ér az algoritmus.
Figyeljük meg, hogy a két gazdaságos feszítőfához rendelt függvényérték annak ellenére megegyezik, hogy a két feszítőfa eltér egymástól. Ez azért van, mert vannak azonos súlyú élek, és így a választás nem egyértelmű.