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ű.