1. Gráfelméleti alapfogalmak
Gráfelméleti alapfogalmak: gráf, egyszerű gráf, komplementer gráf, izomorfia, részgráf, feszített részgráf, élsorozat, séta, út, kör, összefüggő gráf, (összefüggő) komponens. A legrövidebb út feladat nemnegatív élsúlyokkal, Dijkstra algoritmusa.
Alapfogalmak
Fokszámösszeg-tétel (Kézfogás-lemma)
Legyen $G$ tetszőleges gráf. Ekkor:
$\sum_{v \in V(G)} d(v) = 2 \cdot |E(G)|$
vagyis $G$-ben a csúcsok fokainak az összege egyenlő $G$ élszámának a kétszeresével.
$G$ minden éle kettővel járul hozzá a csúcsok fokának összegéhez:
- ha $e = \{u,v\}$ nem hurokél, akkor egyszer $u$-nál és egyszer $v$-nél számítódik be az összegbe,
- ha pedig $e$ a $w$ csúcsra illeszkedő hurokél, akkor $w$ fokát növeli kettővel.
Így az összegzés eredménye valóban az élszám kétszerese.
Interaktív Szemléltető
Kattints a csomópontokra az élek behúzásához és figyeld a változást!
Kidolgozott példa
A feladat szövege
Egy sakk klubban tíz klubtag tartózkodott. Megkérdezték tőlük, hány partit játszottak aznap este. A válaszok: 4, 2, 3, 4, 5, 6, 5, 4, 6, 4. Holmes szerint valaki tévedett vagy hazudott. Miért?
Megoldás levezetése
Modellezzük a szituációt egy $G$ gráffal:
- Csúcsok A klubban tartózkodó 10 vendég.
- Élek Két csúcs között fussun él, ha játszottak partit.
Ekkor a vendégek által mondott számok a gráf csúcsainak fokszámai ($d(v)$). A fokszámösszeg-tétel alapján:
$\sum_{v \in V(G)} d(v) = 2 \cdot |E(G)|$
Adjuk össze a Dr. Watson által gyűjtött számokat:
Mivel a gráf éleinek száma ($|E|$) csak egész lehet, az összegnek mindenképpen párosnak kellene lennie. A 43 páratlan, tehát Holmes tudta, hogy ilyen gráf nem létezhet.
Létezhet-e a gráf?
Írd be a fokszámokat vesszővel elválasztva, és nézzük meg az összeget!
Törlések és részgráfok
Csúcstörlés
A (legalább két csúcsú) $G$ gráfból a $v \in V(G)$ csúcs törlése azt jelenti, hogy $V(G)$-ből elhagyjuk $v$-t és $E(G)$-ből elhagyjuk az összes, $v$-re illeszkedő élt.
Éltörlés
Egy $e \in E(G)$ él törlése azt jelenti, hogy $E(G)$-ből elhagyjuk $e$-t (de ez e végpontjait nem érinti).
Részgráf
Azokat a gráfokat, melyek megkaphatók $G$ bizonyos csúcsainak és éleinek törlésével (amiknek a száma akár nulla is lehet), G részgráfjának nevezzük.
Részgráf Labor
Kattints a csúcsokra vagy élekre a törléshez!
Feszített részgráf
A $G$ gráf egy $H$ részgráfját feszített részgráfnak nevezzük, ha $H$ megkapható $G$ bizonyos csúcsainak a törlésével, élek további törlése nélkül.
Ha a $V(H) = X \subseteq V(G)$ halmaz csúcsai maradnak meg a törlések után (vagyis a $V(G) \setminus X$ halmaz csúcsait töröltük), akkor $H$-t az $X$ csúcshalmaz által feszített részgráfnak hívjuk.
Komplementer gráf
A $G$ egyszerű gráf komplementerének nevezzük és $\bar{G}$-vel jelöljük azt a gráfot, mire:
$E(\bar{G}) = \{\{u, v\} : u, v \in V(G), \{u, v\} \notin E(G)\}$
Szövegben: $\bar{G}$ csúcshalmaza azonos $G$ csúcshalmazával és két különböző csúcs pontosan akkor szomszédos $\bar{G}$-ben, ha $G$-ben nem szomszédosak.
Dinamikus Komplementer Vizualizáció
Kattints az élekre a módosításhoz!
Automatikus invertálás
Példa: Élszám számítása komplementerből
Feladat
A 21 csúcsú $G$ egyszerű gráfról és annak $\bar{G}$ komplementeréről tudjuk, hogy mindkettőnek van 8 darab 4 fokú és 5 darab 10 fokú pontja. Hány éle van $G$-nek?
Megoldás
Jelölje $d_G(v)$, illetve $d_{\bar{G}}(v)$ a $v$ csúcs fokát $G$-ben, illetve $\bar{G}$-ben. Mivel a gráfunk 21 csúcsú, tudjuk, hogy minden $v$ csúcsra igaz:
$d_G(v) + d_{\bar{G}}(v) = 20$
Ez azért van, mert $v$ bármely tőle különböző csúccsal $G$ és $\bar{G}$ közül pontosan az egyikben szomszédos. Ennek segítségével meghatározhatjuk az összes csúcs fokszámát $G$-ben:
- $G$ eredeti pontjai: 8 darab 4 fokú és 5 darab 10 fokú csúcs.
- $\bar{G}$ 10 fokú pontjai $G$-ben: $20 - 10 = 10$ fokúak (ezek azonosak $G$ megadott 10 fokú pontjaival).
- $\bar{G}$ 4 fokú pontjai $G$-ben: $20 - 4 = 16$ fokúak.
Ezek alapján $G$-ben minden csúcs fokát ismerjük már: van 8 darab 4 fokú, 5 darab 10 fokú és 8 darab 16 fokú csúcsa. Számoljuk ki a fokszámösszeget:
A 1.3. Tétel (Fokszámösszeg-tétel) szerint $G$ éleinek száma a fokszámösszeg fele:
A "Kiegészítő" elv
Képzeld el a 21 csúcsú teljes gráfot ($K_{21}$). Ebben minden csúcsból 20 él indul ki. Amikor kettéválasztjuk $G$-re és $\bar{G}$-re, ezek az élek oszlanak meg: ami nincs az egyikben, az benne van a másikban.
Izomorfia
A $G$ és $H$ gráfok izomorfak, ha létezik olyan $f: V(G) \to V(H)$ kölcsönösen egyértelmű függvény, amire a következő teljesül:
Ennek a jele: $G \cong H$
Mit jelent ez a gyakorlatban?
Két gráf izomorf, ha az egyik "átrajzolható" a másikká a csúcsok és élek folytonosságának megtartásával. Ha két gráf izomorf, minden lényeges tulajdonságuk (élszám, fokszámok, körök hossza) megegyezik.
Izomorfia példafeladat
Feladat
Melyek izomorfak az alábbi gráfok közül?
Megoldás levezetése
Az első két gráf izomorf. Ezt például a csúcsok megfelelő betűzésével (bijekció megadásával) lehet igazolni: a bal oldali gráf bármely két csúcsa pontosan akkor szomszédos, ha a középső gráf azonosan betűzött két csúcsai szomszédosak.
A jobb szélső gráf nem izomorf a másik kettővel.
Strukturális indoklás:
A harmadik gráfban található négyszög (4 hosszú kör). Ha ez a gráf izomorf lenne a másik kettővel, akkor azokban is lennie kellene négyszögnek (mivel az izomorfia tartja a körök hosszát).
Azonban az első gráfban bármely $v$ csúcsot is nézzük, annak szomszédai között nincs két olyan, amiknek $v$-n kívül is lenne közös szomszédja, így nem alkothatnak négyszöget.
Élsorozat, séta és út
A $P = (v_0, e_1, v_1, e_2, v_2, \dots, e_k, v_k)$ sorozatot élsorozatnak nevezzük a $G$ gráfban, ha $v_0, v_1, \dots, v_k \in V(G)$ a gráf csúcsai, $e_1, e_2, \dots, e_k \in E(G)$ a gráf élei és minden $i = 1, 2, \dots, k$ esetén $e_i = \{v_{i-1}, v_i\}$ (vagyis az $e_i$ él végpontjai $v_{i-1}$ és $v_i$).
-
Végpontok
Az élsorozat végpontjai $v_0$ és $v_k$. $P$-t az $u$-ból $v$-be vezető élsorozatnak mondjuk, ha a végpontjai (valamilyen sorrendben) $u$ és $v$.
-
Hossz
Az élsorozat hossza $k$, vagyis a benne szereplő élek száma.
Séta
A $P$ élsorozatot sétának nevezzük, ha az $e_1, e_2, \dots, e_k$ élek közül bármely kettő különböző.
Út
Útnak pedig akkor nevezzük $P$-t, ha a $v_0, v_1, \dots, v_k \in V(G)$ csúcsok közül bármely kettő különböző.
A fogalmak hierarchiája
Minden út egyben séta is, és minden séta egyben élsorozat is.
Páratlan fokszámú csúcsok kapcsolata
Feladat
Legyen $v$ a $G$ gráfnak egy páratlan fokszámú csúcsa. Mutassuk meg, hogy létezik $G$-ben olyan $v$-ből induló (pozitív hosszúságú) út, aminek a másik végpontja is páratlan fokszámú.
Megoldás levezetése
Induljunk el $v$-ből és járjunk be „vaktában” egy $P$ sétát $G$-ben – vagyis mindig csak arra vigyázzunk, hogy olyan élen lépjünk tovább, ami korábban még nem szerepelt $P$-ben.
A $P$ séta ugyanis párosával „fogyasztja” az általa érintett, $v$-től különböző csúcsok éleit: egy $u \neq v$ csúcson való áthaladás nyilván kettőt használ fel $u$ élei közül. Így $w$ valóban páratlan fokú kell legyen, különben $P$-nek az utolsó $w$-be való belépése után még volna olyan, $w$-re illeszkedő él, amit $P$ korábban nem érintett.
Ugyanez a gondolat mutatja azt is, hogy $w \neq v$; valóban, $P$ első, $v$-ből induló éle elhasznál egyet $v$ élei közül, így az ezután megmaradó, $v$-re illeszkedő élek száma már páros, vagyis $P$ $v$-ben sem akadhat el.
Vizuális szemléltetés: Az elakadás elve
Figyeld meg, hogyan „fogyasztja” az éleket a séta. A páros fokszámú csúcsokon mindig át tudunk haladni (be- és kimenet), de a páratlan fokszámú csúcsnál a lehetőségek elfogynak.
Minden belépéshez kell egy kilépés – kivéve a páratlan végponton.
Út kinyerése élsorozatból
Ha a $G$ gráfban létezik az $u$ csúcsból a $v$-be vezető élsorozat, akkor létezik $u$-ból $v$-be vezető út is.
Legyen $P_1$ egy $u$-ból $v$-be vezető élsorozat $G$-ben. Ha $P_1$ út, akkor készen vagyunk a bizonyítással.
Ha nem út, akkor létezik olyan $x$ csúcs, amit egynél többször érint. Vágjuk ki most $P_1$-ből az $x$ első és utolsó elfordulása közötti szakaszt (úgy, hogy csak maga az $x$ csúcs maradjon meg).
A kapott sorozat legyen $P_2$. Ekkor $P_2$ is $u$-ból $v$-be vezető élsorozat, de a hossza már kisebb $P_1$-énél.
Ha $P_2$ már út, akkor készen vagyunk. Ha nem, akkor $P_2$ is tartalmaz ismétlődő csúcsot, így a fentiek szerint ismét kivágható belőle egy szakasz, amivel egy még rövidebb $P_3$ élsorozatot kapunk.
Konklúzió
Ez az eljárás véges sok lépés után megáll és szolgáltatja a kívánt $u$-ból $v$-be vezető utat, mert az általa előállított élsorozatok hossza folyamatosan csökken.
Vizuális algoritmus
Kattints a "Kör kivágása" gombra a ciklus kivágásához!
Utak tranzitivitása
Ha a $G$ gráfban létezik az $u$ csúcsból a $v$-be vezető út és létezik a $v$ csúcsból a $w$-be vezető út is, akkor létezik az $u$-ból a $w$-be vezető út is.
Vezessen a $P$ út $u$-ból $v$-be, a $Q$ út pedig $v$-ből $w$-be. Ekkor $P$ és $Q$ összekapcsolásával egy $u$-ból $w$-be vezető $R$ élsorozatot kapunk.
Bár $R$ nem feltétlen út (hiszen lehetnek olyan csúcsok és élek, amik $P$-ben és $Q$-ban is szerepelnek, így ezeket $R$ egynél többször tartalmazza).
A korábbi **1.8. Állítás** (rövidítési eljárás) miatt $R$ létezéséből egy $u$-ból $w$-be vezető út létezése is következik.
Vizuális magyarázat
Két út "összeragasztása" a közös $v$ pontnál egy élsorozatot eredményez, amiből az elágazások/hurkok levágásával egy tiszta $u \to w$ utat kapunk.
A tranzitivitás biztosítja az összefüggőség átvihetőségét.
Összefüggő gráf
Összefüggőség-vizsgáló
Kattints az élekre! A rendszer figyeli, elérhető-e minden csúcs.
Összefüggőség bizonyítása fokszámokból
Feladat
A 100 csúcsú $G$ egyszerű gráf $v$ csúcsának a foka 66, az összes többi csúcsának a foka legalább 33. Mutassuk meg, hogy $G$ összefüggő.
Megoldás levezetése
Ha $w \neq v$ tetszőleges, $v$-vel nem szomszédos csúcs, akkor $v$-nek és $w$-nek kell legyen közös szomszédja.
$d(v) + d(w) \geq 66 + 33 = 99$
szomszédok együttes száma
Mivel egyszerű gráfban a csúcsok fokszáma azonos a szomszédaik számával, $v$-nek és $w$-nek összesen legalább 99 szomszédja van. Azonban $v$-n és $w$-n kívül a gráfban összesen csak $100 - 2 = 98$ csúcs található.
A skatulyaelv alapján lehetetlen, hogy ezek között ne legyen közös szomszéd, hiszen több szomszédsági kapcsolatunk van, mint ahány rendelkezésre álló csúcsunk.
Ezért $v$ és bármely $w \neq v$ csúcs között van $G$-ben (legföljebb kettő hosszúságú) út. Ebből következik, hogy bármely $x, y \in V(G)$ csúcsok között létezik élsorozat: ilyet kapunk, ha egy $x$-ből $v$-be vezető utat összekapcsolunk egy $v$-ből $y$-ba vezetővel.
Így az korábbi állítás (rövidítési eljárás) szerint $x$-ből $y$-ba vezető út is van $G$-ben, vagyis $G$ valóban összefüggő.
Vizuális skatulyaelv
A 98 rendelkezésre álló csúcs nem elegendő ahhoz, hogy $v$ (66 szomszéd) és $w$ (33 szomszéd) szomszédai teljesen elkerüljék egymást.
A két halmaz uniója (66 + 33 = 99) túllépi a keretet, így a metszet nem lehet üres.
Összefüggő komponensek
Legyen $G$ egy gráf és $v \in V(G)$ egy tetszőleges csúcsa.
-
A $w \in V(G)$ csúcsot $v$-ből úton elérhetőnek (vagy röviden: $v$-ből elérhetőnek) nevezzük, ha létezik $G$-ben $v$ és $w$ között út.
-
Jelölje $X$ a $v$-ből úton elérhető $G$-béli csúcsok halmazát. Ekkor az $X$ által feszített részgráfot a $v$ csúcs komponensének nevezzük.
-
A $G$ gráfnak egy $K$ feszített részgráfja akkor összefüggő komponens (vagy röviden: komponens) $G$-ben, ha $G$-nek van olyan csúcsa, aminek a komponense $K$.
Komponens Interaktív
Kattints egy csúcsra a hozzá tartozó összefüggő komponens ($K$) kijelöléséhez!
A komponensek tulajdonságai
Bármely $G$ gráf esetén:
- $G$ komponensei összefüggők;
- $G$ minden csúcsát $G$-nek pontosan egy komponense tartalmazza.
(i) pont bizonyítása
Legyen $K$ egy komponens $G$-ben, tartozzon például a $v$ csúcshoz. Ha $x,y \in V(K)$ tetszőleges csúcsok, akkor mindketten elérhetők $v$-ből úton. Korábbi következményünk (tranzitivitás) szerint $x$ és $y$ egymásból is elérhetők. Mivel $K$ bármely két csúcsa között vezet út, ezért az valóban összefüggő.
(ii) pont bizonyítása
Minden csúcs benne van egy komponensben: a sajátjában. Tegyük fel, hogy a $v \in V(G)$ csúcs a saját komponensén kívül a $w$ csúcséban is benne van. Jelölje ezt a két komponenst $K_v$, illetve $K_w$; meg kell mutatnunk, hogy $K_v = K_w$.
Legyen $x \in V(K_w)$ tetszőleges csúcs. Mivel $v \in V(K_w)$ is igaz, ezért $v$ és $x$ is elérhetők úton $w$-ből. A tranzitivitás miatt ezek egymásból is elérhetők. Ebből következik, hogy $x \in V(K_v)$ is igaz.
Mivel $K_v$ és $K_w$ feszített részgráfok és a csúcshalmazaik a fentiek szerint azonosak, ezért $K_v = K_w$ valóban igaz.
Vizuális összefoglaló: Diszjunkt halmazok
A tétel (ii) pontja azt jelenti, hogy a gráf csúcsai "zsákokba" (komponensekbe) vannak osztva. Nincs olyan csúcs, amelyik két zsákban lenne egyszerre, és nincs olyan sem, amelyik kimaradna.
Alternatív bizonyítás: Páratlan fokszámok
Feladat Újragondolva
Mutassuk meg komponensek segítségével, hogy egy páratlan fokszámú $v$ csúcsból vezet út egy másik páratlan fokszámú csúcsba.
Megoldás komponensekkel
Legyen $G$-ben a $v$ komponense $K$. Tudjuk, hogy egy gráf (vagy annak bármely komponense, mint önálló gráf) fokszámösszege páros.
Logikai kényszer
Ebben a $K$ komponensben kell lennie $v$-n kívül is legalább egy páratlan fokú csúcsnak, különben a $K$-beli csúcsok fokszámösszege páratlan volna (mivel csak egy páratlan tagunk lenne), ami ellentmondana a Fokszámösszeg-tételnek.
Mivel találtunk egy másik páratlan fokú csúcsot ugyanabban a $K$ komponensben, a komponens definíciója szerint $v$ és ezen csúcs között vezet út.
Összefüggőség: Komponens-méret alapú bizonyítás
Feladat
Adott egy 100 csúcsú egyszerű gráf, ahol egy $v$ csúcs foka $d(v)=66$, a többi csúcs foka pedig legalább 33. Bizonyítsuk be az összefüggőséget a komponensek méretének vizsgálatával!
Megoldás ellentmondással
Méretvizsgálat
$|V(K)| + |V(K')| \geq 67 + 34 = 101$
Ez lehetetlen, mivel a gráfban összesen csak 100 csúcs található ($n=100$).
Mivel két diszjunkt komponens nem létezhet, $G$-nek csak egyetlen komponense van, tehát a gráf összefüggő.
A "Túlméretes szigetek" elve
Képzeld el a gráfot egy 100 férőhelyes tárolóként. Ha az egyik "sziget" 67 helyet foglal el, a maradék 33 helyre nem fér be egy másik, legalább 34 helyet igénylő sziget.
Körséta és Kör
A $G$ gráfban a $P = (v_0, e_1, v_1, e_2, v_2, \dots, e_k, v_k)$ élsorozatot:
-
Körsétának nevezzük, ha $P$ séta és $v_0 = v_k$;
-
Körnek nevezzük, ha $P$ egy pozitív hosszúságú körséta és a $v_0, v_1, \dots, v_{k-1}$ csúcsok mind különbözők.
Vizuális különbség
A körséta visszatér a kiindulópontba, de közben érinthet többször is egy csúcsot. A kör ezzel szemben "tiszta": a kezdő és végponton kívül minden csúcsot pontosan egyszer érint.
Az ábrán a sárga csúcsot kétszer érintjük.
Minden érintett csúcs különböző.
A legrövidebb út feladat nemnegatív élsúlyokkal
Konzervatív súlyfüggvény
Legyen adott a $G = (V,E)$ irányított gráf, az $s, v \in V(G), s \neq v$ csúcsok és $G$ élein a $w : E \rightarrow \mathbb{R}$ konzervatív súlyfüggvény. Ekkor ha létezik $s$-ből $v$-be egy $t$ összsúlyú, $k$ élből álló $Q$ élsorozat, akkor létezik $s$-ből $v$-be egy legföljebb $t$ összsúlyú és legföljebb $k$ élű $P$ út is.
Bizonyítás: Ha $Q$ eleve irányított út, akkor az állítás magától értetődően igaz. Ha nem, akkor létezik olyan csúcs, amit $Q$ egynél többször érint.
Keressünk $Q$-ban egy olyan ismétlődő csúcsot, amelynél a $Q$ mentén haladva az élek számában mért távolság a két előfordulás között a lehető legkisebb; jelölje ezt a csúcsot $u$ és $Q$-nak az $u$ legközelebbi előfordulásai közötti szakaszát $C$.
Ekkor $C$ persze egy $u$-ból $u$-ba vezető zárt élsorozat, de ennél több is igaz rá: irányított körnek kell lennie. Valóban, ha nem az volna, akkor létezne olyan $w$ csúcs, amit $C$ egynél többször érint, így $w$ előfordulásai között kisebb volna a távolság $Q$ élei mentén haladva, mint $C$ élszáma – ez pedig $u$ és $C$ választása miatt (a minimális távolság elve alapján) lehetetlen.
Vágjuk ki $Q$-ból a $C$ irányított kört (abban az értelemben, hogy $Q$-nak ebből az $u$-tól $u$-ig tartó szakaszából csak maga az $u$ csúcs marad meg), a kapott élsorozat legyen $Q_1$.
Ekkor $Q_1$ is $s$-ből $v$-be vezet, az éleinek a száma $k$-nál kisebb, az összsúlya pedig legföljebb $t$, mert $w$ konzervativitása miatt $C$ összsúlya (vagyis a kivágott $e$ élek $w(e)$ súlyainak az összege) nemnegatív volt: $w(C) \geq 0 \implies w(Q_1) = w(Q) - w(C) \leq w(Q) = t$
Ha $Q_1$ sem irányított út, akkor $Q_1$ is tartalmaz ismétlődő csúcsokat, így a fentiek szerint ismét kivágható belőle egy nemnegatív összsúlyú irányított kör. Ezt a műveletet ismételve végül a $P$ irányított úthoz jutunk, hiszen az élsorozat élszáma folyamatosan csökken. Mivel az összsúlya a fentiek szerint nem nőhetett (minden kör kivágásakor az összsúly csökken vagy változatlan marad a körök nemnegatív súlya miatt), ezzel az állítást beláttuk. Q.E.D. ∎
Legyen adott a $G = (V,E)$ irányított gráf, az $s, v \in V(G)$ csúcsok és $G$ élein a $w : E \rightarrow \mathbb{R}$ konzervatív súlyfüggvény. Ha az $s$-ből $v$-be vezető $P$ legrövidebb út áthalad az $u$ csúcson, akkor $P$-nek az $s$-től $u$-ig tartó $P_u$ szakasza egy $s$-ből $u$-ba vezető legrövidebb út.
Bizonyítás: Tegyük fel indirekt, hogy létezik $s$-ből $u$-ba egy $P_u$-nál rövidebb $P'$ út. Ekkor $s$-ből $P'$ mentén $u$-ig haladva, majd onnan $P$-nek az $u$-tól $v$-ig tartó szakaszán tovább folytatva egy $s$-ből $v$-be vezető $Q$ élsorozatot kapunk.
Megjegyzés: $Q$ nem feltétlenül út, mert $P'$-nek lehet közös éle vagy csúcsa a $P$ út $u$-tól $v$-ig tartó szakaszával.
Mivel a $P_u$ részutat a nála rövidebb $P'$ útra cseréltük, a kapott $Q$ élsorozat összsúlya szigorúan kisebb, mint a $P$ út összsúlya: $w(Q) = w(P') + w(P_{u \to v}) < w(P_u) + w(P_{u \to v}) = w(P)$
A korábbi **11.2. Állítás** miatt létezik a gráfban egy olyan $P_{new}$ egyszerű irányított út $s$-ből $v$-be, amelynek összsúlya legfeljebb $w(Q)$. Így: $w(P_{new}) \leq w(Q) < w(P)$ Ez azt jelenti, hogy találtunk egy $P$-nél szigorúan rövidebb utat $s$-ből $v$-be, ami ellentmondás, hiszen feltételeztük, hogy $P$ a legrövidebb út. Ezzel a következményt beláttuk. ∎
Kör-kivágó Szimulátor
Kövesd végig az irányított élsorozat egyszerű úttá alakítását!
Az élsorozat: s → a → b → c → a → t. A sárga 'a' csúcs kétszer szerepel.
Dijkstra algoritmusa
Dijkstra algoritmus (leírása)
A Dijkstra-algoritmus egy $G = (V,E)$ irányított gráfban, egy kitüntetett $s \in V$ forrásból kiindulva határozza meg a legrövidebb utak hosszát az összes többi csúcsba, feltéve, hogy a $w : E \rightarrow \mathbb{R}_0^+$ súlyfüggvény nemnegatív.
// DIJKSTRA PSZEUDOKÓD
Input: G = (V,E) irányított gráf, s ∈ V forrás, w: E → ℝ⁺₀ súlyok
Output: t(v) távolságok és p(v) szülők minden v ∈ V-re
1. K = ∅ // állandósult csúcsok halmaza
2. t(s) = 0, és minden v ≠ s-re t(v) = ∞
3. p(v) = undefined minden v ∈ V-re // szülő mutatók
4. ciklus amíg K ≠ V:
a. Válasszunk egy a ∈ V \ K csúcsot, amire t(a) minimális!
b. K = K ∪ {a}
c. minden u ∈ V \ K csúcsra, amire létezik (a,u) él:
ha t(a) + w(a,u) < t(u) akkor
t(u) = t(a) + w(a,u)
p(u) = a
Ha a $w : E \rightarrow \mathbb{R}_0^+$ súlyfüggvény nemnegatív, akkor a Dijkstra-algoritmus futása során minden $v \in V$ csúcs állandósulásakor (amikor $v$ bekerül a $K$ halmazba) $t(v)$ értéke megegyezik a valódi legrövidebb $s \rightarrow v$ út hosszával, azaz $t(v) = \text{táv}(s,v)$.
Bizonyítás: A helyességet teljes indukcióval bizonyítjuk $K$ mérete szerint.
Bázis: Amikor $|K| = 1$, akkor $K = \{s\}$, és $t(s) = 0 = \text{táv}(s,s)$. Ez igaz, mivel nemnegatív súlyok mellett a legrövidebb $s \rightarrow s$ út hossza 0.
Indukciós lépés: Tegyük fel, hogy az állítás igaz minden eddig $K$-ba helyezett csúcsra. Legyen $a \in V \setminus K$ a következő kiválasztott csúcs (amire $t(a)$ minimális). Megmutatjuk, hogy $t(a) = \text{táv}(s,a)$.
Tegyük fel indirekt, hogy $t(a) > \text{táv}(s,a)$ (mivel $t(a)$ egy konkrét élsorozat hossza, ennél rövidebb út létezhet, így $t(a) < \text{táv}(s,a)$ nem lehetséges).
Legyen $P$ egy valódi legrövidebb út $s$-ből $a$-ba. Mivel $s \in K$ és $a \notin K$, az úton kell lennie olyan éleknek, amelyek $K$-ból kivezetnek. Legyen $(x, y)$ az első olyan irányított él a $P$ úton, amelyre $x \in K$ és $y \notin K$ (előfordulhat, hogy $y = a$).
Mivel $x \in K$, az indukciós feltevés miatt $t(x) = \text{táv}(s,x)$. Amikor $x$ bekerült $K$-ba, az algoritmus frissítette $x$ kimenő éleit, így $y$ távolságát is: $t(y) \leq t(x) + w(x,y) = \text{táv}(s,x) + w(x,y)$
Mivel $P$ a legrövidebb út $s$-ből $a$-ba, és $x \rightarrow y$ a $P$ úton van, az optimalitás miatt a $P$-nek az $s$-től $y$-ig tartó részútja is a legrövidebb $s \rightarrow y$ út, így: $\text{táv}(s,y) = \text{táv}(s,x) + w(x,y)$ Ebből következik, hogy $t(y) \leq \text{táv}(s,y)$. Mivel a valódi távolság alsó korlátja $t(y)$-nak, így valójában $t(y) = \text{táv}(s,y)$.
Mivel a súlyok nemnegatívak, a legrövidebb út részútja nem lehet hosszabb a teljes útnál: $\text{táv}(s,y) \leq \text{táv}(s,a)$ Összerakva az egyenlőtlenségeket és az indirekt feltevést kapjuk: $t(y) = \text{táv}(s,y) \leq \text{táv}(s,a) < t(a)$ Vagyis $t(y) < t(a)$ adódik, ami ellentmond annak, hogy $a$-t választottuk ki, mint a $V \setminus K$ halmaz legkisebb $t$ értékű elemét. Az ellentmondás bizonyítja, hogy $t(a) = \text{táv}(s,a)$. Q.E.D. ∎
Lépésszám és optimalizáció
A Dijkstra-algoritmus futásideje a csúcsok ($n = |V|$) és élek ($m = |E|$) számától, valamint a felhasznált adatszerkezetektől függ:
- Tömbös megvalósítás: Ha a legkisebb $t(u)$ értéket egyszerű lineáris kereséssel választjuk ki a $V \setminus K$ halmazból, a minimumkeresés lépésszáma lépésenként $O(n)$, ami $n$ lépésben $O(n^2)$ műveletet jelent. Az élek frissítése (relaxáció) összesen $O(m)$ időt vesz igénybe. Így a teljes futásidő $O(n^2)$. Ez sűrű gráfok esetén optimális.
- Kupac (Heap) megvalósítás: Ha a csúcsokat bináris kupacban tároljuk, a legkisebb elem kiválasztása és törlése $O(\log n)$ időt vesz igénybe, az élek frissítése során pedig a távolságok csökkentése (decrease-key) szintén $O(\log n)$ műveletet igényel. Így a teljes lépésszám $O((n+m) \log n)$, ami ritka gráfok ($m \ll n^2$) esetén rendkívül gyors.
Fontos megjegyzés: A Dijkstra-algoritmus csak nemnegatív súlyok esetén működik. Negatív súlyú élek jelenlétében a Bellman-Ford algoritmus használható (bár a tantárgyban ez már nem tananyag).
Dijkstra Szimulátor (Feladat 11.8)
Lépkedj végig a Dijkstra-algoritmus futásán a tankönyvi példagráfon!
Kezdeti állapot: s távolsága 0, a többié végtelen. Induláshoz kattints a 'Következő lépés' gombra!
| Csúcs | K-ban? | t(v) távolság | p(v) szülő |
|---|---|---|---|
| s | Nem | 0 | - |
| b | Nem | ∞ | - |
| c | Nem | ∞ | - |
| d | Nem | ∞ | - |
| g | Nem | ∞ | - |
| f | Nem | ∞ | - |
Összefoglaló Kvíz
Milyen jól ismered a gráfokat?
Vidd fölé az egeret vagy kattints a válasz felfedéséhez!
#01 Fokszámösszeg
Ha egy gráf 15 éllel rendelkezik, mennyi a csúcsainak fokszámösszege?
#02 Hierarchia
Minden séta egyben út is? Vagy fordítva?
#03 Komplementer
Egy 10 csúcsú gráfban a $v$ csúcs foka 4. Mennyi lesz $v$ foka a komplementer gráfban?
#04 Komponensek
Lehet-e egy csúcs egyszerre két különböző összefüggő komponens tagja?
Tudtad-e?
Minden egy sétával kezdődött
A gráfelmélet 1736-ban született meg, amikor Leonhard Euler bebizonyította, hogy Königsberg városában nem lehet úgy végigmenni a hét hídon, hogy mindegyiken pontosan egyszer haladjunk át. Ő volt az első, aki a hidakat élekként, a városrészeket pedig csúcsokként ábrázolta.
Hat lépés távolság
A koncepció, miszerint a Földön bárki elérhető bárki máson keresztül maximum 5-6 ismerősön át, először Karinthy Frigyes 1929-es, Láncszemek című novellájában jelent meg. Ez a társadalmi gráfok és az összefüggőség egyik leghíresebb példája.
Honnan jön a "Gráf" név?
Bár Euler alapozta meg a tudományt, a "gráf" (graph) kifejezést csak 1878-ban használta először James Joseph Sylvester. Ő vette észre a hasonlóságot a kémiai molekulák szerkezeti ábrái és a matematikai csomópontok között.
A zsebedben lévő gráf
Amikor a Google Térkép útvonalat tervez, valójában egy gigantikus gráfban keres élsorozatokat. Az útkereszteződések a csúcsok, az utcák pedig az élek. Egy-egy város térképe több millió csúcsból álló összefüggő komponenst alkot.