Önmagában is érdekes és az alkalmazásokban is gyakran előforduló probléma a gráfok ill. a hálózatok összefüggőségének vizsgálata. A gráfelméletben többféle "összefüggőség" fogalom is definiált, itt mi csak egyfélével dolgozunk: Összefüggő gráf az olyan gráf, amelyben bármely két pont között van legalább egy út.

Ha visszagondolunk a sorozat egyik korábbi, a minimális utak keresésével foglalkozó cikkére, azt is mondhatnánk, hogy az összefüggőség nem probléma, hiszen meghatározva a minimális utakat az összes viszonylatra, kiderül, hogy van-e olyan viszonylat, amelynek nincs útja. A dolog természetesen nem ilyen egyszerű ennek a témakörnek is megvannak a saját speciális feladatai és megoldásai, az alábbiakban ebből adunk egy kis ízelítőt.

Minimális feszítőfa

Egy összefüggő gráf egy feszítőfáján értjük a gráf egy olyan - fa struktúrájú - részgráfját amely minden pontot tartalmaz. Ha már hálózatról beszélünk, vagyis az éleknek van hossza, akkor egy ilyen fát is minősíthetünk, mérhetünk az élei hosszának összegével. Így már beszélhetünk két ilyen fa hossz szerinti összehasonlításáról és kereshetjük a legrövidebb, a minimális hosszúságút. (Megjegyezzük, hogy ilyenből egy hálózaton belül több is lehet.) A minimális hosszúságú feszítőfát a továbbiakban röviden minimális feszítőfának nevezzük.

A keresés bonyolultsága lényegesen megnő akkor, ha a gráf irányított. Ezért itt és most csak az egyszerűbb esettel foglalkozunk: a hálózat irányítatlan, más szóval minden él két irányú és a két irányban azonos hosszú. Az 1. ábra hálózata ilyen, a vastagított élek egy minimális feszítőfát adnak.

1.ábra

A feladatot szemléltessük egy példával. Egy település utcahálózatának kereszteződései legyenek a pontok, az összekötő szakaszok az élek. Az önkormányzat a jelenlegi utcahálózat bizonyos szakaszain (mindkét irányban használható) kerékpárutat akar kiépíteni. A kiépítés költsége a hálózat minden szakaszára ismert. Mely szakaszokon építsenek kerékpárutat ha be kell tartani az alábbi követelményeket:

  • Minden pontból minden pontba el lehessen jutni, csak a kerékpárutak használatával is.
  • A kiépítés költsége a lehető legkisebb legyen.

A megoldás: a hálózatban az élhossz legyen minden élen a kerékpárútnak a megfelelő útszakaszon való kiépítési költsége, és határozzunk meg egy minimális feszítőfát. Ennek élei mentén kell kiépíteni a kerékpárutakat. (Az Olvasó biztosan észrevette, hogy itt hallgatólagosan elfogadtuk azt a tényt - ami egyébként egzaktan bizonyíthatóan igaz - hogy a minimális összélhosszúságú, és minden pontot tartalmazó részgráf szükségszerűen egy fa.)

Az ismertetendő algoritmus (Kruskal -féle algoritmus) a hálózat pontjaiból képez először egyelemű, majd minden lépésben bővülő halmazokat. Ezek a halmazok önmagukban összefüggő és minimális összhosszú részhálózatoknak felelnek meg. Két ilyen halmazt akkor tudunk egyesíteni, ha van a két részhálózatot összekötő él. Az élek vizsgálatát hossz szerinti növekvő sorrendben végezzük. Ha sikerül az összes pontot egy halmazba összeszedni, akkor a gráf összefüggő, és az egyesítéseknél "összekötő" élek egy minimális feszítőfát alkotnak.

Az algoritmus pontosabb leírásához vezessünk be néhány jelölést.

  • xy jelölje az x és y pontokat összekötő élet.
  • E jelölje az élek egy részhalmazát. Ez kezdetben az összes élt tartalmazza. Ebből választjuk ki sorra a vizsgálandó éleket.
  • F jelölje az élek egy részhalmazát. Ez kezdetben üres. Ebbe gyűjtjük a fát alkotó éleket.
  • H jelöljön egy olyan halmazt, amelynek elemei is halmazok, mégpedig ponthalmazok. A H elemei önmagukban összefüggő és minimális összhosszú részhálózatoknak felelnek meg.

Ezek után az algoritmust a következőképpen definiálhatjuk:

  • Kezdőállapot

E: minden élt tartalmaz. F: üres. H: minden egyelemű ponthalmazt tartalmaz.

  • Javító lépések

Mindaddig, amíg a H -ban legalább kettő halmaz van és emellett az E -ben is van legalább egy él, ismételjük az alábbi műveletsort: Válasszunk ki és töröljünk is az E -ből egy minimális hosszú élet, jelölje ezt xy. Ha az x és az y a H -ban lévő két különböző halmazban van, akkor egyrészt az xy élet vegyük fel az F -be, másrészt a két halmazt egyesítsük, az egyesített halmazt vegyük fel a H -ba, az eredetieket pedig töröljük a H -ból.

  • Végállapot

Ha a javító lépéseket azért nem tudjuk folytatni, mert a H -ban csak egy halmaz van, akkor készen vagyunk, az F adja a megoldást. Ha viszont a befejezés oka az, hogy ugyan még több halmaz van, de nincs több él az E -ben, akkor a hálózat nem összefüggő, nincs feszítőfa.

2.ábra

Az algoritmust a 3. ábrán követhetjük a példahálózaton. Megadjuk a kezdőállapotot, az első három javító lépést, egy közbeeső javító lépést és a végállapotot. A közbeeső lépés utáni fát a 2. ábra, a végeredményt az 1. ábra is mutatja. A példában az E halmazt közvetlenül nem jegyezzük. A példához megjegyezzük még, hogy a minimális hosszú él kiválasztásánál - ha erre több lehetőség is volt - az abc sorrend szerinti elsőt választottuk mindig ki. (Ez természetesen nem előírás, csak egy lehetőség. Máshogy választva esetleg egy másik minimális feszítőfát kaphatunk.)

3.ábra

 

Összefüggő komponensek

A témakör egy másik alapfeladata a következőképpen fogalmazható meg:

  • Bontsuk fel a hálózatot önmagukban összefüggő részhálózatokra, más néven komponensekre.

A feladat ugyan látszólag más mint az előbb, de rögtön látni fogjuk, hogy tulajdonképpen a fenti feladat egy egyszerűbb speciális esetéről van szó, amelyet az előbbi algoritmus egy szintén egyszerűsített változatával oldhatunk meg.

Egyszerűsítsük az algoritmust. Mivel itt nincs szó hosszakról (tehát a hálózat csak mint gráf játszik szerepet) az élek vizsgálati sorrendje közömbös. Fára mint eredményre nincs szükségünk, tehát az éleket nem kell gyűjteni. Az algoritmus ezek után:

  • Kezdőállapot

E: minden élt tartalmaz. H: minden egyelemű ponthalmazt tartalmaz.

  • Javító lépések

Mindaddig, amíg a H -ban legalább kettő halmaz van és emellett az E -ben is van legalább egy él, ismételjük az alábbi műveletsort: Válasszunk ki és töröljünk is az E -ből egy élet, jelölje ezt xy. Ha az x és az y a H -ban lévő két különböző halmazban van, akkor a két halmazt egyesítsük, az egyesített halmazt vegyük fel a H -ba, az eredetieket pedig töröljük a H -ból.

  • Végállapot

A H -ban lévő halmazok adják az összefüggő komponenseket. (Ha csak egy ilyen van, akkor a hálózat összefüggő.)

4.ábra

Az algoritmus szemléltetésére "szétszedtük" a példahálózatot és töröltük az élhosszakat, így kaptuk a 4. ábra gráfját. Feltételezve hogy a gráfot az éltárolásos rendszerben tároljuk, a legegyszerűbb az élek vizsgálatát is ebben a sorrendben végezni. A H változását az 5. ábrán követhetjük. Az ábrán soronként az egy - egy kezdőpontból kiinduló összes él vizsgálata utáni állapotot adjuk meg.

5.ábra

Programtechnika

A fenti algoritmusok beprogramozásánál több olyan nehézségre is bukkanunk, amelyek megoldása, áthidalása nem nyilvánvaló, sőt komoly programtervezési meggondolásokat is igényel. Ilyen lehet pl. a halmazok (E,F,H) konkrét megvalósítása, ábrázolása, különösen ha nagyobb hálózatokra is gondolunk. Ezért a programszövegek megértését itteni magyarázattal is segítjük.

Kezdjük talán a H halmaz tárolásával/kezelésével. Ez a halmaz olyan, egymással diszjunkt (közös elem nélküli) ponthalmazokból áll, amelyek uniója (egyesítése) lefedi/magába foglalja a gráf összes pontját. Másképpen fogalmazva a gráf valamennyi pontjára igaz az, hogy benne van H-nak valamely ponthalmazában (hogy egy adott pont éppen melyik halmazban van, azt az algoritmus lépései definiálják), így minden pontra csak ezt az információt (azaz hogy éppen melyik halmazban található) kell feljegyeznünk,.

Mivel a H-beli ponthalmazok száma (jelölje ezt HDB)

- kezdetben megegyezik a pontok számával

- az algoritmusok során mindig csökken (hiszen halmazokat egyesítünk)

- egynél nem lehet kevesebb,

ezért ha megsorszámozzuk a H-beli halmazokat és ezt a halmazsorszámot rendeljük hozzá a pontokhoz, akkor egy pontszám elemű tömbben tárolható a H halmaz.

A kérdés ezek után már csak az, hogyan adminisztráljuk a H halmaz megváltozását, azaz két H-beli ponthalmaz egyesítését/összevonását? Ahhoz, hogy a H-beli halmazok megtartsák 1-től induló folyamatos sorszámozásukat, a nagyobb sorszámú összevonandó halmaz elemeit áttesszük a kisebb sorszámú halmazba, míg ezen 'kiürülő' (nagyobb sorszámú) halmazt úgy töröljük, hogy a legutolsó (HDB sorszámú) halmaz elemeit átrakjuk ebbe a halmazba. Ezek a 'pontmozgatások' egyetlen ciklussal megtehetők, hiszen csak a 'mozgatandó' pontokhoz rendelt halmazsorszámokat kell megváltoztatnunk, és ezután már csak a H-t alkotó ponthalmazok számát (HDB) kell eggyel csökkentenünk.

Az E és F élhalmazok kezelése ennél egyszerűbben megoldható, hiszen egy élről csak azt kell nyilvántartanunk, hogy az algoritmus során éppen melyik halmazban található (E-ben, F-ben vagy egyikben sem). Ezt az információt pedig, a gráf tárolási módjától függően, vagy egy egydimenziós tömbben (éltárolás) vagy egy kétdimenziós tömbben/mátrixban (mátrixos tárolás) tárolhatjuk/kezelhetjük.

 

Témazáró

Ezzel cikksorozatunk végére értünk. Reméljük, hogy az - ebben a témakörben kevésbé jártas - érdeklődő diákok, tanár és gyakorló számítástechnikus kollégák számára sikerült egy kicsit rávilágítanunk erre az önmagában is nagyon érdekes, de alkalmazásaiban is nagyon fontos területre. Továbbolvasásra, a témakörben való mélyebb tájékozódáshoz ajánlunk néhány magyar nyelvű és bevezető, tankönyv jellegű szakkönyvet:

  • Wirth: Algoritmusok + Adatstruktúrák = Programok.
  • Aho - Hopcroft - Ullman : Számítógép - algoritmusok tervezése és analízise
  • Lovász - Gács: Algoritmusok

Mindhárom könyv a Műszaki Könyvkiadó (Budapest) többszöri kiadásában is megjelent.