Minimális költségű feszítőfa keresése

Az alapfeladat: Adott n település, melyek közé úthálózatot szeretnénk építeni úgy, hogy bármely településből el lehessen jutni a többibe. Ismerjük továbbá az egyes településeket összekötő utak építési költségeit. Keressük a legkisebb költségű megoldást!

Értelmezés: Adott egy összefüggő, egyszerű gráf, súlyozott élekkel - ezek a „költségek”. Keressünk egy minimális költségű (költségösszegű) olyan részgráfot, mely a gráf összes pontját tartalmazza!

Egy ilyen részgráf nyilván fa kell legyen, ugyanis ha volna benne kör, akkor annak egy tetszőleges élét elhagyva - ezzel a költségek összegét csökkentve - még továbbra is összefüggő maradna a gráf. A keresett gráf tehát egy olyan fa, mely a gráf összes pontját tartalmazza, azaz *feszítő fa*.

Az algoritmus: A gráf éleit színezzük a következő szabályok szerint.

1. Piros szabály: Vegyünk a gráfban egy olyan kört, melyben nincs piros színű él. Az egyik maximális költségű él pirosra színezhető.
2. Kék szabály: Vegyünk egy olyan nem üres csúcshalmazt, melyből nem vezet ki kék él. Ekkor a kivezető élek közül az egyik minimális költségűt színezzük kékre.

A Piros szabály azt az élt színezi pirosra, amely biztosan nem lehet benne a minimális költségű feszítő fában. A Kék szabály azt azélt színezi kékre, amely benne lesz az általunk készített minimális költségű feszítőfában.

Kezdetben a gráf színezetlen. Alkalmazzuk a Piros és Kék szabályt tetszőleges sorrendben, tetszőkleges helyen, ez elvezet egy minimális költségű feszítőfához.

Definíció: Takaros színezésnek nevezünk egy élszínezést, ha az összes adott színű él része a gráf egy minimális költségű feszítőfájának.

Pontosítás: Ha a G irányított gráfban bármely él piros, kék vagy színtelen lehet, akkor a színezés takaros, ha az összes kék él része a gráf egy minimális költségű feszítőfájának, miközben a piros élek egyike sem része ennek a feszítőfának.

Lemma: Legyen G egy súlyozott élű összefüggő gráf, F egy minimális költségű feszítőfája. Legyen g = (u, v) a G-nek egy olyan éle, ami nem éle F-nek, és tegyük fel, hogy az F-beli u-ból v-be vezető úton van olyan g' él, amelyre g nem nagíobb g' súlyánál. Ekkor az F-ből ag hozzávételével és a g' elhagyásával adódó F' gráf is egy minimális költségű feszítőfa G-ben.

Az FU{g}-ben ugyanis lesz g'-t tartalmazó kör, így g'-t elhagyva a F' összefüggő marad, miközben a költség nem nőhet.

Állítás: A Piros-Kék eljárás kékkel színezett élei egy minimális költségű feszített fát adnak.

Bizonyítás:

A bizonyítás két részből áll:

1. A Piros-Kék színezés mindig takaros (a kék színt tekintve)
2. A színezés nem reked meg.

I. A színezés takaros - bizonyítás teljes indukcióval

• A színezetlen gráf nyilván takaros
• Ha egy takaros színezésből kiindulva piros szabályt alkalmazunk, akkor az új színezett él, f piros lesz. Ha f nem éle F-nek, akkor nincs mit bizonyítanunk. Ha f része F-nek. akkor f törlésével F két komponensre esik szét. A körnek, amelyre a piros szabályt alkalmaztuk biztosan lesz f' (f-től különböző) a két komponenst összekötő éle. A Piros-szabály és f' választása miatt f' szintelen, és súlya nem nagyobb f súlyánál. Ekkor F'=F\{f'}U{f} egy minimális költségű feszítőfa.
• Ha egy takaros színezésből kiindulva kék szabályt alkalmazunk, akkor az f új élt hozzávéve a színezés takaros marad: Legyen F az eddigi színezést tartalmazó minimális költségű feszítőfa. Ha az új él ennek éle, akkor nincs mit bizonyítani. Tegyük fel, hogy az f él nem része F-nek. Legyen f két végpontja P és Q. Ekkor F-ben van P-t Q-val összekötő út. Keressük meg ennek az útnak a választott ponthalmazból kilépő f' élét. Ez az f' él nem lehet piros (mert F takaros). A Kék-szabály szerint kék sem lehet, és f súlya nem lehet nagyobb f' súlyánál. Így F'=F\{f'}U{f} a Lemma miatt szintén minimális költségű feszítőfa.

II. A színezés nem reked meg. Takaros színezés lévén a kék élek erdőt alkotnak. Ha egy színezetlen él egy kék fa két pontját köti össze, akkor Piros-szabályt alkalmazhatunk rá. Ha egy színezetlen él különböző kék komponenseket köt össze, akkor a kék szabály alkalmazható az él egyik végpontját tartalmazó kék komponensre.

A teljes színezés is takaros, így a kék élek egy minimális költségű feszítőfát adnak ki.

A Piros-Kék algoritmusban a helyesség szempontjából közömbös a sorrend, de a hatékonyság szempontjából nem.

Prime módszere a Piros-Kék eljárást alkalmazza úgy, hogy minen lépésben az F kék fát bővítjük. Kezdetben az F csak a kiindulási pontot tartalmazza, az eljárás végére a gráf összes pontját. A következő kék élnek az egyik legkisebb súlyú élet választjuk azok közül, amelyek F-beli pontból F-en kívüli pontba mennek.

Az eljárás csak a Kék-szabályt alkalmazza. A kék gráf az eljárás során végig fa.

Az eljárás egy mohó algoritmus.

A módszer lényege röviden:
A következo befestendő f él legyen mindig a legkisebb súlyú színtelen él. Ha az f két végpontja ugyanazon kék fában van, akkor az él legyen piros, különben pedig kék.

Részletesebben:
Állítsuk sorba költség szerint növekvő sorrendbe az éleket. A legkisebb költségű éltől haladjunk sorba a nagyobb költségűek fele. Ha a soronkövetkező él két külön komponensbe lévő pont között van, akkor azt vegyük fel a kiválasztott élek közé. Így eljutunk egy minimális költségű feszítőfához.

Inicializálás: Legyen A az üreshalmaz, az eddig kiválasztott élek halmaza. Algoritmusunk ezt növeli addig, amíg egy feszítőfa élhalmazává nem válik.

Rendezési lépés: Rakjuk sorba az éleket költségeik szerint, a kisebb költségű elemek kerüljenek előre.

Beválasztási lépések: Az első nem vizsgált élre nézzünk meg, hogy A-hoz hozzáadva körmentes élhalmazhoz jutunk-e. Ha igen, akkor bővítsük A-t az éllel. Ha nem, akkor A maradjon. Ha még van nem vizsgált él, akkor újra végezzük el a beválasztási lépést. Ha az összes él vizsgált, akkor álljunk le. Az aktuális A az algoritmus eredménye: egy minimális költségű feszítőfa.

Minden egyes kék fához válasszuk ki a legkisebb súlyú belőle kimenő (színtelen) élet. Színezzük kékre a kiválasztott éleket.