2.4. 2.4. Címkézési technika

A címkézési technika tulajdonképpen nem más, mint azon pontok szisztematikus felkutatása, amelyek az s kitüntetett pontból éleken elérhetők. A pontok felkutatása során valamilyen módon megjelöljük azokat a pontokat, amelyekhez már elérkeztünk. Ezért célszerű a pontokhoz egy rekeszt rendelni. Ha egy ponthoz eljutottunk, akkor a pont rekeszébe valamilyen jelet írunk. Ez a jel szintén célszerűségi okokból a pontok azonosító címe (címkéje) legyen. Az S halmazt, azaz az pontból elérhető pontok halmazát ezek után a következő, programozásra is alkalmas eljárással építjük fel:

Kiválasztunk egy pontot, amelyről tudjuk, hogy az S halmazba tartozik. Induláskor ez csak az pont lehet. Az olyan eddig még nem vizsgált pontoknak a rekeszébe, amelyekhez az pontból vezet él, beírjuk az pont címét (címkézünk). Ezek a pontok most már az -hez tartoznak. Az így nyert pontokat sorra véve folytatjuk az eljárást. Hogy az ismétlődést elkerüljük, jelölnünk kell azt, ha egy pontot már megvizsgáltunk a továbbhaladás szempontjából. Ezt a címke előjelezésével oldjuk meg. Ha egy pontba eljutunk, akkor "negatív" címkével látjuk el és ha ebből a pontból továbbmentünk, ahová csak lehetett, akkor a címkét pozitívra változtatjuk át. A 0. lépésben (induláskor) az pont rekeszébe a „ ” címkét tesszük. Összefoglalva tehát a címkézési technika egy közbülső lépése abból áll, hogy:

Tekintünk egy negatív címkézett pontot (a pont már meg van címkézve, de címkéje negatív). Ennek a pontnak negatív címével címkézünk minden olyan üres rekeszű pontot, amelyek ebből a negatív címkézett pontból éllel közvetlenül elérhetők, majd utána (vagy akkor is, ha nem találtunk ilyen pontokat) a negatív címkézett pont címkéjét pozitívra váltjuk.

A címkézésből kiolvasható, hogy ha egy pont rendelkezik címkével (akár pozitív akár negatív címkével), akkor ez a pont -ből elérhető éleken. Ha a pont címkéje negatív, akkor még nem kíséreltük meg a pontból a továbbhaladást, ha viszont a pont címkéje pozitív, akkor már megkíséreltük a pontból a továbbhaladást.

Ha eljutottunk a ponthoz (), akkor -ből kiindulva visszafelé haladva a címkék segítségével megkapjuk az -ből a -be vezető utat.

Ha nem jutottunk el a ponthoz (), akkor a címkézett pontok tartoznak az -be, a címkézetlenek pedig a -be.

Az alábbiakban példákon keresztül mutatjuk be a címkézési technikát. Felhívjuk a figyelmet a példák tanulmányozására, mert néhány fontos jelölést is bevezetünk, amelyek hasznos alkalmazásoknak bizonyulnak a továbbiakban.

1. Példa:

Legyen adott az alábbi ábrával egy digráf hat ponttal és kilenc éllel. A digráf pontjait a további példákban is a sorszámaikkal jelöljük, nem pedig az eddig használt jelöléssel, amit leginkább az elmélet leírása során használunk. A digráf két kitüntetett pontja legyen és .

Határozzuk meg a digráfban a két kitüntetett pont közötti utat!

A címkézést a struktúra táblázaton végezzük és mindig balról az első negatív címkéjű pontból nézzük meg a továbbhaladást. A példában a címkézést lépésenként mutatjuk be. Az egyes lépésekben a pontok rekeszeit a táblázat fölött tüntettük fel (egyébként bárhol elhelyezhettük volna a rekeszeket). A későbbiekben természetesen csak egy rekeszsort fogunk használni. Az első példáknál azért írtunk minden továbbhaladási lépéshez rekeszsort, hogy a címkézési technika lépéseit nyomon tudjuk követni.

Az alábbiakban szavakban is leírjuk a címkézési technika lépéseit.

0. lépés:

Csupán abból áll, hogy a kezdőpont () címkéjeként „ ”-t írunk. Ezután megnézzük, hogy az pontból mely pontok érhetők el, ezt a 2. sorban található * szimbólumok jelzik. Látható, hogy elérhető közvetlenül a 4-es és a 6-os pont.

1. lépés:

A 4-es és a 6-os pont rekeszébe beírjuk a 2-es pont címét negatív előjellel. Az első lépéshez tartozik még a 2-es pont címkéjének pozitívra váltása. Ebben az állapotban tehát 3 darab pont tartozik a ponthalmazba, azaz az pontból úttal elérhető pontok halmazába.

2. lépés:

Tovább bővítjük az elérhető pontok halmazát. Az előző lépésből látható, hogy a 4-es és a 6-os pont címkéje negatív, tehát ezek közül valamelyikből nézzük meg a továbbhaladás lehetőségét. Javasoljuk a szisztematikus címkézés miatt, hogy mindig balról jobbra haladjunk, azaz balról az első negatív címkéjű pontot vizsgáljuk, példánkban ez a 4-es pont. Ebből a 4. sor alapján csak az 1-es pontba mehetünk, tehát az 1-es pontnak a „-4” címkét adjuk, a 4-es pont címkéjét pedig pozitívra változtatjuk.

3. lépés:

Az előző lépésből látható, hogy két negatív címkéjű pont van, ebből a balról az elsőt választjuk, azaz az 1-es pontot, ahonnan az 1. sor alapján a 3-as és a 6-os pontba mehetünk. A 3-as pontot megcímkézzük „-1”-el, az 1-es pont címkéjét pedig pozitívra változtatjuk. A 6-os pont címkéjét nem módosítjuk, hisz az már a ponthalmazba tartozik, tehát elérhető valamilyen úton az kezdőpontból.

4. lépés:

Az előző lépésből látható, hogy az első negatív címkéjű pont a 3-as pont, ebből a 3. sor és a már meglévő címkék alapján csak az 5-ös pontba mehetünk. Az 5-ös pontot megcímkézzük „-3”-al, a 3-as pont címkéjét pedig pozitívra változtatjuk. Ezzel befejeztük a címkézést, mert olyan állapothoz jutottunk, amikor a végpont is a megcímkézett pontok közé került, azaz az 5-ös pont úttal elérhető az kezdőpontból.

Az alábbi megjegyzést tesszük. A bizonyítás során a ponthalmazt az összes olyan pont halmazaként definiáltuk, amelyek a kezdőpontból elérhetők. Amennyiben a címkézés során olyan állapotba kerülünk, hogy a végpont is elérhető, akkor álljunk meg, mivel a kítűzött példában nem az volt a feladatunk, hogy az összes elérhető pontot felkutassuk, hanem utat keressünk. Ebben a példában egyébként nem is tudtuk volna tovább folytatni a címkézést, mivel minden pont meg lett címkézve. Könnyen látható, hogy az út megtalálásakor a címkének pozitívra változtatása felesleges munka. Természetesen folytathatjuk a címkézést egy nagyobb méretű feladat esetén, ha kíváncsiak vagyunk az összes elérhető pontra is.

A példánkban tehát azt kaptuk, hogy létezik út 2-ből 5-be. Azt azonban még nem tudjuk, hogy milyen úton lehet eljutni. Erre nagyon könnyű a válasz, hiszen az utat a címkéken visszafelé haladva határozhatjuk meg. A címkék definíciójából nyilvánvaló az út meghatározása, hisz egy adott pont címkéje azt mutatja, hogy közvetlenül honnan érkeztünk az adott ponthoz. Az 5-ös pont címkéje azt mutatja, hogy a 3-as pontból érkeztünk oda, a 3-as pont címkéje pedig azt, hogy az 1-es pontból érkeztünk oda, az 1-eshez a 4-esből, a 4-eshez pedig a 2-esből. A 2-es pont „+s” címkéje pedig azt mutatja, hogy visszafelé eljutottunk a kezdőponthoz. A címkézés alapján kapott út tehát a következő:

Írhattuk volna az utat fordított sorrendben is, de mindig a végpontból kell visszafelé haladni a címkéken. Az út másik leírása lehet például:

Természetesen létezhet más út is, de a címkézési technika egyetlen út meghatározására szolgál. Ha például a címkézés során jobbról balra vagy össze-vissza haladtunk volna, akkor másik utat kaphattunk volna.

Az alábbi struktúratáblázaton a fentebb meghatározott 2-ből az 5-be vezető „utat” (valójában csak az út éleit) illusztráljuk bekeretezéssel. Az út éleit a struktúratáblázatban úgy szemléltetjük, hogy a címkéken a végponttól visszafelé haladva az adott élet a táblázatban bekeretezzük.

2. Példa:

Keressünk az előző digráfban utat 1-ből a 2-be (, )! A címkézés lépéseit az alábbiakban közöljük, most már nem magyarázzuk meg az egyes lépéseket.

A címkézés során nem találtunk utat, viszont találtunk egy üres vágást, amely az 1-et és a 2-t elválasztja. Az üres vágást meghatározó ponthalmazok az alábbiak:

, amely a címkézett pontok összessége,

, amely a címkézetlen pontok összessége.

Az alábbi struktúratáblázaton a fentebb meghatározott üres vágást illusztráljuk lefedéssel. A vágás éleit a megismert lefedéssel szemléltetjük a struktúratáblázatban. A példabeli vágás üres, így olyan lefedő vonalrendszert kapunk, amelynél fedetlen helyeken nincs él, azaz nincs * jel.

3. Példa :

Határozzuk meg az előző digráfban a 3-ból a 4-be vezető utat! Célszerű a címkézésnél az és az pontokat megjelölni (pl. nyíllal), hogy a címkézést csak addig folytassuk, míg a pont rekeszébe címke kerül (ekkor van út) vagy addig, amikor már csak pozitív előjelű címkék vannak (nincs út, van üres vágás). E példában és a későbbiekben is csak egy rekeszsort használunk.

Megoldás: A 3-ból a 4-be vezető út: .