3. tétel Flashcards
(12 cards)
Szomszédsági lista
A lista elemeit a gráf élei adják, ezért gyakran nevezik éllistás ábrázolásnak is. Minden csúcshoz tartozik egy-egy lista, mely az adott csúcsból kiinduló éleket tartalmazza. A lista elemeiben a célcsúcsok indexeit tároljuk. Működik mind irányított, mind irányítatlan gráfnál. Irányítatlan gráfnál egy élnek két listaelemet feleltetünk meg, azaz egy irányítatlan élt egy oda-vissza mutató irányított élpárral valósítunk meg. Ha az élekhez tartoznak súlyok, akkor azokat is tárolni kell a listában.
A szomszédsági listás ábrázolás helyfoglalása irányított gráfoknál a csúcsok plusz az élek számával arányos, irányítatlan gráfoknál pedig a csúcsok plusz az élek számának kétszeresével arányos. (V+2E) Mivel a memóriaigény az élek számával arányos, ezért ezt az ábrázolási módot ritka / nem sűrű gráfoknál használjuk.
Szomszédsági mátrix
Egy n darab csúcsú gráfot egy n*n-es mátrixban is tárolhatjuk, ahol az oszlopokat és sorokat rendre a csúcsokkal indexeljük. Egy mezőben akkor van 1-es, ha a hozzá tartozó oszlop által meghatározott csúcs szomszédja a sor által meghatározott csúcsnak.
Ha súlyozott a gráf, akkor az élsúlyokat (élköltségeket) is el kell tárolni. Ezt is a mátrixon belül oldjuk meg. A súly valós számokat vehet fel. Természetesen adódik, hogy ahol előzőleg 1-est írtunk, azaz létezett az illető él, oda most írjuk be az él költségét. A nem létező élek esetére vezessük be a végtelen élsúlyt. Egy ilyen “élen” csak végtelen nagy költséggel tudunk végig haladni (tehát nem tudunk).
A mátrixos ábrázolás helyfoglalása mindig ugyanakkora, független az élek számától, a mátrix méretével 𝑛2-tel arányos. A mátrixos reprezentációt sűrű gráfok esetén érdemes használni, hogy ne legyen túl nagy a helypazarlás.
Mélységi keresés (Depth-first search)
Rekurzív algoritmus irányított gráfokban lévő csúcsok keresésére. A gráf csúcsainak 3 állapota lehet:
* Fehér: még nem jártuk be.
* Szürke: már bejártuk, de még nem állíthatjuk, hogy az illető csúcsból elérhető összes csúcsot bejártuk (van olyan szomszédja, ami még fehér).
* Fekete: az adott csúcsból elérhető összes csúcsot már bejártuk (a szomszédjai feketék).
Elindulunk a kiindulási pontból egy irányba, ameddig el nem érünk addig a csúcsig, amelyikből már nem tudunk tovább menni. Miután elértük, elkezdünk visszafelé haladni, és feketére színezni a korábban érintett pontokat. Ez egészen addig tart, míg egy olyan csúcshoz nem érünk, amelynek van fehér színű szomszédja. Ekkor abba az irányba megyünk tovább, majd folytatjuk ugyan ezt a logikát, míg az egész gráf fekete nem lesz.
Szélességi keresés (Breadth-first search)
Irányított és irányítatlan gráfoknál egyaránt használatos, hogy megkeressen egy adott csúcsot. Az algoritmus először eléri a kezdőcsúcsot. Ezután eléri a kezdőcsúcstól 1 távolságra lévő csúcsokat, ezután a kezdőcsúcstól 2 távolságra lévő csúcsokat és így tovább. Ha egy csúcsot egyszer már elértünk, akkor már bejártnak tekintjük. Az elérési sorrendnél azt kell figyelembe venni, hogy amíg az összes, a kezdőcsúcstól k távolságra lévő csúcsot ki nem írtuk, addig nem szabad k-nál nagyobb távolságú csúcsokat kiírni.
Futási ideje: Ο(é𝑙𝑒𝑘 𝑠𝑧á𝑚𝑎 + 𝑐𝑠ú𝑐𝑠𝑜𝑘 𝑠𝑧á𝑚𝑎)
Minimális feszítőfák
Legyen egy irányítatlan és súlyozott gráf, melyben minden csúcsot érinteni kell. Úgy kell bejárni a csúcsokat, hogy az élek súlyainak összege minimális legyen és az így kapott fa ne tartalmazzon kört.
Prim algoritmus
Egy összefüggő, irányítatlan, súlyozott gráf minimális feszítőfáját határozza meg mohó stratégia segítségével. Működési elve, hogy csúcsonként haladva építi fel a fát egy tetszőleges csúcsból kiindulva és minden egyes lépésben a lehető legolcsóbb élt keresi meg egy következő csúcshoz (mohó).
Futási idő: Ο(𝑛 log(𝑛)), ahol n = csúcsok száma
Az algoritmus lépései:
* Válasszuk ki a gráf egy tetszőleges csúcsát, legyen ez egy egycsúcsú fa.
* Ciklus, ameddig van a gráfnak olyan csúcsa, amelyik nincs benne a fában:
o Válasszuk ki a fa csúcsai és a gráf többi csúcsa között futó élek közül a legkisebb súlyút.
o A kiválasztott él nem fabeli csúcsát tegyük át a fába az éllel együtt.
Kruskal algoritmus
A Prim algoritmushoz hasonlóan ez is egy irányítatlan és súlyozott gráf minimális feszítőfáját határozza meg mohó stratégia segítségével. Ha a gráf összefüggő, akkor minimális feszítőfát, ha nem összefüggő, akkor pedig minimális feszítőerdőt hoz létre.
Futási idő: Ο(log(𝑛)), ahol n = csúcsok száma
Az algoritmus lépései:
* Súlyuk szerint sorba rendezzük az éleket és kiválasztjuk a legkisebb súlyút.
* Kiválasztjuk a soron következő élet, majd bevonjuk a feszítőfába, amennyiben nem alkot vele kört.
* Ha van még nem vizsgált él, folytassuk az előző lépésekkel.
Adott csúcsból induló legrövidebb utak problémája
Egy gráfban egy út hossza az utat alkotó élek súlyainak összege. Súlyozatlan gráf esetén az élek súlyait 1-nek tekintjük.
Bellman-Ford algoritmus
Kiszámítja a legrövidebb utat egyetlen csúcstól az összes többi csúcshoz egy irányított súlyozott gráfban. Képes negatív súlyú élszámok kezelésére is. Ha van benne ilyen, akkor azt az algoritmus jelzi, ha nincs, akkor visszaadja a legrövidebb utat. Nem mohó algoritmus, az adott csúcsból induló legrövidebb utat keresi. Futási idő: Ο(𝑐𝑠ú𝑐𝑠𝑜𝑘 𝑠𝑧á𝑚𝑎 * é𝑙𝑒𝑘 𝑠𝑧á𝑚𝑎)
Az algoritmus lépései:
* Végig iterálunk a végpontokon abc sorrendben, a kiindulási pontból kezdve. Ha nincs még eljutási súly, akkor kihagyjuk azokat az elemeket.
* Megnézzük, hogy az adott pontból elérhető szomszédok hány egységre vannak, majd beírjuk őket a tömbbe, amennyiben az elérési út kisebb, mint a meglévő.
* Addig folytatjuk a szomszédokba való eljutáshoz tartozó költség számítást, ameddig nem kapunk negatív értéket vagy a lefutás iterációinak a száma kisebb, mint a csúcsok száma (ez esetben negatív körünk van), vagy a tömb már nem változik (ekkor van a legrövidebb út).
Dijkstra algoritmus
Súlyozott és irányított gráfokon működik, melyekben nem lehet negatív súlyú él, de kör igen.
Az adott csúcsból induló legrövidebb utat keresi meg.
Futási idő: Ο(é𝑙𝑒𝑘 𝑠𝑧á𝑚𝑎 + 𝑐𝑠ú𝑐𝑠𝑜𝑘 𝑠𝑧á𝑚𝑎 ∗ log(𝑐𝑠ú𝑐𝑠𝑜𝑘 𝑠𝑧á𝑚𝑎))
Az algoritmus lépései:
* Kiindulunk a kezdőpontból, majd megnézzük a szomszédokat, és a legrövidebb súlyú úton megyünk tovább. Ekkor egy súlyt rendelünk a ponthoz.
* Ha átérünk a következő pontba, akkor megnézzük, hogy az elérhető utak közül (összeadva) melyik a legkisebb, és abba az irányba megyünk tovább.
* Egészen addig ismételjük, míg minden csúcsba el nem jutunk.
A legrövidebb utak problémája körmentes gráfokra
A Bellmen-Ford algoritmussal megoldható Ο(𝑐𝑠ú𝑐𝑠𝑜𝑘 𝑠𝑧á𝑚𝑎 + é𝑙𝑒𝑘 𝑠𝑧á𝑚𝑎) bonyolultsággal.
Ford-Fulkerson algoritmusa
- Maximum folyam algoritmus, az a lényege, hogy A pontból B pontba a lehető legtöbb
egységnyi (bármit) átvigyünk kapacitási kritériumok mellett. - D – 0 / 4 → Z jelentése: D pontból Z pontba 4(kapacitás) egység vihető át maximum és
jeleneleg 0(folyam) megy át rajta - Javító utat mindig reziduális hálózaton keresünk
- Tetszőlegesen választunk utat random
- Addig megyünk reziduális hálóval ameddig nem tudunk eljutni sből tbe
- Edmonds karp algoritmus!!
- Egy adott élre a reziduális kapacitás egy olyan érték, amely megadja, hogy adott folyam esetén legfeljebb mennyivel növelhetjük a folyamot úgy, hogy a kapacitást ne haladja meg. A reziduális hálózat olyan gráf, amely tartalmazza az eredeti összes csúcspontját, valamint olyan irányított éleket, amelyekre a reziduális kapacitás nagyobb mint 0.
Az algoritmus lépései: - Kezdetben minden folyam értékét 0-ra állítjuk.
- A reziduális hálózaton keresünk egy utat a termelőből a gyártóba. Erre használhatjuk valamelyik korábbi gráf bejáró algoritmust.
- Amennyiben nem találunk utat, az algoritmus véget ér.
- A kapott úton megvizsgáljuk, hogy melyik utat alkotó élen a legkisebb a reziduális kapacitás, majd az út minden élén ennyivel növeljük a folyamok értékét.
