====== 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ő, [[matematika:kombinatorika:grafelmelet#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 [[matematika:kombinatorika: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*. ===== Piros-kék eljárás ===== Az algoritmus: A gráf éleit színezzük a következő szabályok szerint. - 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ő. - 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 a//g// 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: - A Piros-Kék színezés mindig takaros (a kék színt tekintve) - 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. ===== Prim algoritmus ===== 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. ===== Kruskal algoritmusa ===== 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. ===== Borůvka modszere ===== 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.