oktatas:matematika:kombinatorika:minimalis_koeltsegu_feszitofa [MaYoR elektronikus napló]

Ez az oldal csak olvasható. Megtekintheted a forrását, de nem változtathatod meg. Ha úgy gondolod, hogy ez helytelen, kérdezd az Adminisztrátorokat!
====== 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.