30. Erősen összefüggő komponensek

A gráfos alkalmazások között is találkozunk olyan problémákkal, amelyeket megoldását a részekre bontott gráfon határozzuk meg, majd ezeket alkalmas módon teljes megoldássá egyesítjük. A részekre bontás alapja gyakran a gráfok összefüggősége: a gráfot olyan részekre bontjuk, amelyek a csúcsok közötti közlekedés szempontjából „egyben lévőnek” érzünk.

Egy irányítatlan gráfot összefüggőnek mondunk, ha bármely két csúcsa összeköthető úttal. Ha egy gráf összefüggő komponensekre esik szét, akkor ez egyes részeken belül szabadon lehet közlekedni az irányítatlan éleken, de a komponensek között nincsen átjárás. Ez egy ekvivalencia osztályozás a csúcsok között, az elérhetőség relációja alapján.

Az irányított gráfok esetén kétféle összefüggőséget is bevezetnek. A gráfot egyszerűen csak összefüggőnek mondjuk, ha az élek irányításától eltekintve, az előző értelemben összefüggő. Szigorúbb fogalom az erős összefüggőség, amely azt követeli meg, hogy egy ennek eleget tevő gráfban bármely csúcs elérhető bármelyik másikból, a gráf irányított élein haladva. Ha egy irányított gráf bomlik részekre az erős összefüggőség relációja szerint, akkor a gráf erősen összefüggő (erős) komponenseihez jutunk.

Ebben a fejezetben az irányított gráfok erősen összefüggő komponenseinek előállítására adunk eljárást, amely két mélységi bejárás egymás utáni alkalmazásával lehetséges.

30.1. Néhány fogalom és összefüggés

Definíció: Legyen G=(V,E) irányított, véges gráf. G összefüggő, ha G irányítás nélkül összefüggő. G erősen összefüggő, ha esetén út.

A definíciók közötti különbség érzékelhető, ha egy város úthálózatára egyszer a gyalogos, másszor az autós szemével tekintünk. A gyalogosok számára az egyirányú utca nem jelent megkötést, tehát ők tekinthetik irányítatlannak az utcákat, míg az autósok számára az utcák irányítottak. Egy városrész összefüggő, ha gyalogosan bármely pontjából bármely pontjába eljuthatunk, míg a városrész erősen összefüggő, ha ugyanez megtehető autóval is. Érezhető, hogy az erősen összefüggőség valóban szigorúbb követelmény, mint az (egyszerű) összefüggőség.

A 30.1. ábrán látható gráf összefüggő, de nem erősen összefüggő, hiszen például a 2-es csúcsból nem lehet eljutni az 1-es csúcsba.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej30_01_full.png30.1. ábra. Egy összefüggő, de nem erősen összefüggő gráf

Definíció: Legyen G=(V,E) irányított, véges gráf, . Ekkor legyen u v, ha léteznek , illetve utak a gráfban.

Állítás: A reláció ekvivlenciareláció, tehát osztályozza a V csúcshalmazt.

Definíció: A reláció ekvivalencia osztályait nevezzük a gráf erős komponenseinek.

Állítás: Egy összefüggő gráf két erős komponense között az élek csak egy irányba mehetnek.

Bizonyítás: Indirekt tegyük fel, hogy két erős komponens között oda-vissza is mehetnek élek. Legyen a két komponens és (30.2. ábra). Ekkor és csúcsok között léteznek és utak, ugyanis az erős komponenseken belül definíció szerint, és között pedig az indirekt feltevés szerint létezik út, tehát , ami ellentmondás.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej30_02_full.png30.2. ábra. Erős komponensek közötti utak

Definíció: Legyen G=(V,E) irányított, véges gráf. G redukált gráfja olyan irányított gráf, amelynek csúcsai G erős komponensei, és a redukált gráf két csúcsa között, akkor halad él, ha csúcsoknak megfelelő G erős komponensei között halad él, továbbá az él irányítása megegyezik az erős komponensek között haladó él(ek) irányításával.

A 30.1. ábrán látható gráf redukált gráfját illusztráltuk a 30.3. ábrán.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej30_03_full.png30.3. ábra. Redukált gráf

Állítás: A redukált gráf DAG, azaz körmentes irányított gráf.

Bizonyítás: Indirekt tegyük fel, hogy a redukált gráf nem DAG, azaz létezik benne irányított kör. Legyen egy ilyen kör . Ekkor a kör mentén lévő komponensek kölcsönösen elérhetők, vagyis , ami ellentmondás.

Vissza a tartalomjegyzékhez

30.2. A redukált gráf előállításának algoritmusa

A redukált gráf előállításához tehát a gráf erős komponenseit kell meghatároznunk, amelyet a következő algoritmussal végezhetünk:

1.A gráfot bejárjuk mélységi bejárással, a csúcsokat a befejezési számok sorrendjében kiírjuk egy verembe.

2.Transzponáljuk a gráfot, azaz megfordítjuk az élek irányítását.

3.Bejárjuk a transzponáltat mélységi bejárással, de nem az alapvető sorrend szerint vesszük a csúcsokat kiinduló csúcsnak, hanem az 1. lépésben készített veremből történő kivétel sorrendjében.

A lépések végrehajtásával egy mélységi erdőt kapunk, amelyben a fák a gráf erős komponensei lesznek. Ezeknek a fáknak a csúcsait összevonhatjuk egy csúccsá, majd a csúcsok között az éleket az eredeti gráf éleinek megfelelően megadjuk, így megkapjuk a redukált gráfot.

Az algoritmus műveletigényénél figyelembe kell venni a mélységi bejárás , a gráf megfordítás , illetve a verem műveletek műveletigényeit, így .

Megjegyzés: Ha a gráf DAG, akkor az algoritmus 3. lépésében említett bejárási sorrend nem más, mint a gráf egy topologikus rendezése.

Állítás: Bármely mélységi bejárás során, egy erős komponens összes csúcs ugyanabba a mélységi fába kerül.

Bizonyítás: Legyen u az a csúcs, amelyet a bejárás során először érünk el az erős komponens csúcsai közül. Ekkor a komponens összes többi csúcsa még fehér, továbbá erős komponensről van szó, így az összes csúcsba vezet út. Emiatt az erős komponens összes többi csúcsába vezet fehér csúcsokból álló út. A Fehér út tétel szerint az erős komponens összes többi csúcsa u leszármazottja lesz a mélységi fában.

Állítás: Futtassuk le a fenti algoritmust a G=(V,E) gráfon. Legyenek a gráf csúcsai, és tekintsük az algoritmus 3. lépésében kapott mélységi fákat. Ekkor, akkor és csak akkor, ha u és v ugyanabban a mélységi fában vannak.

Bizonyítás:

: Az erős komponensek csúcsai minden mélységi bejárás során ugyanabba a fába esnek, továbbá G és erős komponensei azonosak, így u és v ugyanabban a mélységi fába esnek a mélységi bejárása során.

: Tegyük fel, hogy u és v ugyanabban a mélységi fában vannak. Legyen w ennek a fának a gyökere. Mivel u leszármazottja w -nek, út -ben, tehát út G-ben.

Legyen az útnak a legkisebb mélységi számú csúcsa az algoritmus 1. lépésbeli bejárásánál. Ekkor w leszármazottja -nek (mivel elérésekor minden csúcsa fehér, alkalmazható a Fehér út tétel). Tehát út G-ben.

Az gyökerű részfában a legnagyobb befejezési szám, tehát -nek -nél előbb kell lennie a fordított bszám listában, azonban w mégis előbb van a listában, mivel -ben való bejárásnál gyökér lett. Ebből következik, hogy . Tehát az úton a legkisebb mélységi szám, és a legnagyobb befejezési szám (az első bejárás szerint), így csúcsai leszármazottai -nek, tehát út G-ben.

Mivel út és utak G-ben, . Hasonlóan belátható, hogy . Mivel a reláció ekvivalencia reláció, .

Vissza a tartalomjegyzékhez

30.3. Szemléltetés

Tekintsük a 30.1. ábrán bemutatott gráfot. Futtassuk le a mélységi bejárást a gráfon. A csúcsok feldolgozási sorrendje legyen a csúcsok címkéje szerint rendezett. A 30.4. ábrán látható az első mélységi bejárás eredménye. A befejezési számok szerint csökkenően a csúcsok sorrendje: 1, 4, 2, 5, 3. (Alább két ábra látható, a második ábra már a tranzitív gráf bejárását szemlélteti.)

A kép (nagyobb változata) külön ablakban is megtekinthető.fej30_04_full.png30.4. ábra. Egy gráf mélységi bejárása

A kép (nagyobb változata) külön ablakban is megtekinthető.fej30_s1_full.png30.5. ábra. A tranzitív gráf mélységi bejárása, az első két mélységi fa előállítása

A gráf transzpontáltján kell a mélységi keresést lefuttatni a csúcsok fent említett sorrendjében (lásd: 30.5. ábra), vagyis az 1. csúcstól indítjuk a mélységi bejárást. Mivel ebből a csúcsból a transzponáltban nem indult ki él, ezért a mélységi bejárás azonnal visszalép, így ki is alakul az első fa a mélységi erdőben, amely csupán az 1-es csúcsból áll. Ezt követően az algoritmus a 4-es csúcsból indítja a bejárást, de mivel csupán az 1-es csúcsba vezet él (amelyet már felfedeztünk), ismét visszalépés következik, és kialakul a második mélységi fa.

A kép (nagyobb változata) külön ablakban is megtekinthető.fej30_s2_full.png30.6. ábra. A harmadik mélységi fa előállítása

A kép (nagyobb változata) külön ablakban is megtekinthető.fej30_14_full.png30.7. ábra. A tranzitív gráf mélységi fái

A következő lépésben a mélységi bejárás a 2-es csúcsból indul, amelyből az 1-esbe már nem, de a 3-as csúcs felé tovább tud lépni, majd onnan az 5-ös csúcsra (30.6. ábra).

Innen ismét visszalépések következnek, és kialakul a harmadik mélységi fa a gráfban, amely a 2,3,5 csúcsokat tartalmazza. A 30.7. ábrán láthatjuk színek szerint a tranzitív gráf mélységi fáit, vagyis az eredeti gráfunk erős komponenseit. Jól látható, hogy a 2,3,5 csúcsokat összevonva az eredeti gráfban visszakapjuk a 30.3. ábra redukált gráfját.

Vissza a tartalomjegyzékhez