DT
D é n e s T a m á s matematikus TD
email:
titoktan@freemail.hu
Gráfbeli pályák és jelsorozatok kapcsolata
Abstract
Egy adott jelkészletből (nevezzük ABC-nek)
előállított jelsorozatok tulajdonságainak vizsgálatához bemutatunk egy
matematikai modellezési eszközt (ezek a
gráfbeli pályák), amellyel az úgynevezett strukturális összehasonlítások is
könnyen elvégezhetők. Mint látni fogjuk
a gráf modell nem csak szemléletesen és áttekinthetően képezi le a
problémákat, hanem nagyon hatékony, gyors algoritmust is szolgáltat a
gyakorlati megoldáshoz.
Az információ-dömping világában már nem csupán
elméleti, hanem kulcsfontosságú gyakorlati jelentősége van a szövegeket és más
jelsorozatokat tároló, kezelő, rendszerező informatikai rendszerekben
(szövegszerkesztő, kulcsszó szerinti keresés, kriptológia, stb.) annak, hogy
milyen hatékonysággal tudjuk leírni, összehasonlítani a jelsorozatokat. Az
információs rendszereken túli érdekes alkalmazások merülnek fel a
folyamat-elemzés, vagy akár a genetika területén is.
Jelen dolgozat ismerteti a jelsorozatok (tágabban:
szekvenciális rendszerek) gráfmodelljét, majd a gráfbeli pályák egy
probléma-hierarchiáját, valamint egy igen hatékony algoritmust gráfbeli pályák
összehasonlítására.
1. A gráf modellről
Ebben a részben néhány felhasználásra kerülő
gráfelméleti fogalom definícióját és a kifejtéshez szükséges alapvető tételeket
fogalmazzuk meg.
Egy gráfot a csúcsai (szögpontjai) és élei
halmazával definiálunk, az alábbiak szerint:
1.1. definíció
Legyen P=
n elemű halmaz és E
[1], ekkor
a 
=(P,E) rendezett párt
irányított gráfnak nevezzük,
ahol P
a gráf szögpontjainak, E az éleinek halmaza. A továbbiakban csak irányított gráfokról
lesz szó, azaz az E-beli elemek
irányított élek, melyeket a kezdő és végpontjaiból álló rendezett párral adunk
meg.
Ilyen például az 1.ábrán az 
=(AB) irányított él. 
1.2. definíció
A 
=(P,E) gráfban
az U=
E-beli élekből álló élsorozatot pályának nevezzük, ha
mindegyik él végpontja megegyezik az utána következő él kezdőpontjával.
A pálya hossza
a benne levő élek száma. Ezt a továbbiakban egy adott U pálya esetén l(U)-val jelöljük.
Egy pályát megadhatunk a benne foglalt csúcsok
(szögpontok) sorozatával is. Például a
2.ábrabeli U=
pályát az U=(ABDC)
formában is megadhatjuk.
Egyszerű
pályának az
olyan pályát nevezzük, amely egyetlen élt sem tartalmaz kétszer.
Elemi pályáról akkor beszélünk, ha az
élekhez tartozó kezdő és végpontok között egyik sem szerepel kétszer. Az elemi
pályát szokás irányított útnak is nevezni.
1.3. definíció
Egy gráfot
összefüggőnek nevezünk, ha bármely két szögpontja között vezet út.
1.4. definíció
Ha egy gráfban két szögpontot több, azonos
irányítású él köt össze, ezeket párhuzamos
éleknek nevezzük.
1.5. definíció
Az olyan élt, amelynek kezdő és végpontja megegyezik
hurokélnek nevezzük.
A továbbiakban minden általunk tárgyalt gráfban
megengedett a párhuzamos és hurokélek létezése. Párhuzamos éleket tartalmazó
gráfok éleinek megkülönböztetésére (bizonyos eltérő tulajdonságok jelzésére)
szokás az élek úgynevezett színezését alkalmazni. Az ilyen gráfot színezett élű gráfnak nevezzük.
Jelöljük egy
=(P,E) irányított
gráf tetszőleges 
szögpontjának kimenő
fokszámát 
-vel, bemenő fokszámát
-vel, és definiáljuk az alábbi S halmazt:
(1.1) S=
A gráfbeli pályák kitüntetett szerepére mutat rá az
alábbi 1.1. és 1.2. gráfelméleti tétel
(lásd [2] 52.oldal
3-4., 3-5.tétel), melyeket bizonyítás nélkül közlünk:
1.1. Tétel
Ha 
=(P,E) irányított,
összefüggő gráf és nem minden 
szögpontjára
teljesül, hogy 
, akkor 
felbontható k darab irányított pályára, ahol
(1.2) k= 
Példaként tekintsük a 2.ábrán bemutatott gráfot, ahol P= 
E= 
S= 
k= 
= 4
A négy pálya, amelyekre a gráf felbontható: 
1.2. Tétel
Ha 
=(P,E) irányított,
összefüggő gráf, melyben mindegyik p
szögpontra 
, akkor az E-beli élek egyetlen pályát alkotnak. (például ilyen gráfot kapunk, ha az 1.ábra gráfjában az (AC) élt (CA)-ra változtatjuk)
A jelsorozatok vizsgálatára tehát kézenfekvően adódik a gráf modell, hiszen ha annak az ABC-nek melyből a jelsorozatokat képezzük, megfeleltetjük a gráf P szögponthalmazát és a jelsorozatban az „x betű után következik y” relációnak megfeleltetjük az (xy) irányított élt, így a teljes jelsorozat pontosan egy gráfbeli pálya lesz. Természetesen vonatkozik ez a megfeleltetés bármely jelsorozatra, amely ugyanebből az ABC-ből keletkezik.
2. Gráfbeli pályákkal kapcsolatos problémák
Gráf modellek vizsgálata során, a pályákkal kapcsolatban
három fő problématípust szoktak megkülönböztetni: az elérhetőségi, a pályák leszámlálási és keresési problémákat.
ELÉRHETŐSÉG
A probléma: Létezik-e pálya egy 
=(P,E) gráf 
szögpontjai között ?
Ez a problématípus a gráfhoz rendelt úgynevezett
szomszédossági mátrix segítségével jól algoritmizálható módon oldható meg.
2.1. definíció
Adott 
=(P,E) párhuzamos
éleket nem tartalmazó, n
szögpontú gráfhoz rendelt 
mátrixot a gráf szomszédossági mátrixának nevezzük, ha
(2.1) 
Ha az M mátrixot logikai mátrixként kezeljük, akkor
az 
(a mátrix k-adik
hatványa) mátrixban szereplő 1-esek éppen azokat a szögpont párokat
jelölik ki, amelyeket k
hosszúságú pálya köt össze.
Képezve tehát az
(2.2) M=
logikai mátrixot (
a logikai összeadást jelöli, r pedig a leghosszabb 
-beli pálya hosszát), az
M-ben levő 0 elemek pontosan azokat a szögpont párokat
jelölik ki, amelyek között nincs összekötő pálya.
PÁLYÁK LESZÁMLÁLÁSA
A probléma: Az elérhetőségi feladat megoldása csupán arra ad választ, hogy
létezik-e pálya két vizsgált szögpont között.
Sokszor ennél több érdekel, mégpedig az, hogy ha létezik pálya két
szögpont között, akkor hány ilyen van és ezek hogyan oszlanak meg hosszúság
szerint ?
Ez a probléma ugyancsak visszavezethető az adott
gráf szomszédossági mátrixának hatványozására. Itt azonban nem logikai, hanem a
szokásos aritmetikai műveleteket használjuk.
Tekintsük egy adott
n szögpontú 
=(P,E) gráf M=
szomszédossági
mátrixának i-edik sorát és j-edik
oszlopát és tegyük fel, hogy azok k-adik eleme 1-es:
j.oszlop
Az i.sor
a 
szögpontból kiinduló
élekről, a j.oszlop pedig a 
szögpontba beérkező
élekről ad felvilágosítást. Tehát
az 
azt jelenti, hogy
léteznek a 
és a 
élek, azaz létezik 
-ből 
-be vezető 2 hosszúságú pálya. Így világos, hogy az alábbi formula éppen a 
-ből 
-be vezető 2
hosszúságú pályák számát adja:
(2.3) 
A gondolatmenet általánosításából adódik, hogy a
szomszédossági mátrix m-edik hatványa éppen az m hosszúságú pályák számát adja meg.
Az m-nél
nem hosszabb pályák számáról az 
mátrix elemei
tájékoztatnak, amely a következőképpen áll elő:
(2.4) 
PÁLYÁK
ÖSSZEHASONLÍTÁSA
A probléma: Tegyük fel, hogy gráfunk
q darab pályára bontható,
azaz q
darab különböző színnel színezett pálya egyesítéseként áll elő. Ekkor a
következő vizsgálati célokat tűzzük ki:
C1. Határozzuk meg a q darab pálya közös (azonos) részélsorozatait, azaz a pályák
közös
szakaszait.
C2. Határozzuk meg a közös szakaszok egyes pályákon
belüli hosszát és elhelyezkedését.
A C1.
és C2. problémák szemléletesen a
következőt jelentik:
Rajzoljuk rá egy-egy celluloid lemezre (külön-külön)
gráfunk szögpontjait úgy, hogy ezek pontosan fedésbe hozhatók legyenek, ezután
rajzoljuk a lemezekre a gráf egy-egy pályáját (lásd a 3. és 4.ábrát).
3.ábra 4.ábra
8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 8 7 6 5 4 3 1 2
5.ábra
Ha most a két lemezt egymásra illesztjük úgy, hogy a
megfelelő számozású szögpontok fedjék egymást
(lásd 5.ábra), akkor az
erősebben kirajzolódó élek pontosan a két pálya közös szakaszait mutatják.
Feladatunk tehát olyan hatékony algoritmus tervezése, amely a „celluloid lapok
egymásra illesztését” elvégzi és megadja az így leolvasható értékes
információkat a közös pályaszakaszokról.
3. A matematikai módszer
3.1.definíció
Legyen 
=(P,E) irányított
gráf és 
két gráfbeli pálya. Az üres pályát (olyan
pályát, amely nem tartalmaz élt) a 
jellel jelöljük.
Első lépésként definiálunk a pályák között egy 
szorzás műveletet,
melynek segítségével megfogalmazzuk a módszer alapját képező tételt. A 
műveletet a
következőképpen definiáljuk:
(3.1) 
Valamint, ha
U tetszőleges nem üres pálya,
akkor 
3.1. Tétel
Legyen 
=(P,E) irányított
gráf. Bármely 
-beli pálya 
-beli elemi pályák 
szorzatára bontható.
Bizonyítás
Tekintsünk egy tetszőleges 
-beli 
pályát. Ha U
elemi pálya, akkor a tétel állításának eleget tesz, így kész a
bizonyítás.
Ha U nem elemi pálya, akkor a 
szögpont sorozatban
van legalább egy olyan szögpont, amely legalább kétszer fordul elő és nem
azonos a kezdő, illetve a végponttal.
Legyen balról az első olyan szögpont, amely
másodszor fordul elő 
Ekkor tehát 
elemi pálya, hiszen
minden k-nál kisebb sorszámú szögpont
különböző. Hagyjuk el most U-ból az
részpályát. Speciális eset áll elő, ha j=1
és k=2, ekkor ugyanis 
egy hurokél, amelyet
tekinthetünk elemi részpályának. Ezután
a fennmaradó 
, vagy hurokél esetén az
pályával ismételjük
meg a fenti eljárást egészen addig, amíg a fennmaradó részpálya elemi lesz,
vagy üres pálya. Ez minden esetben elérhető,
hiszen az U pálya hossza véges.
Tegyük fel, hogy
m-szer ismételjük a fenti eljárást a kívánt végfeltétel eléréséig. Ekkor
felírhatjuk a következő összefüggést:
(3.2) 
Az eljárás biztosítja, hogy mindegyik 
részpálya,
valamint 
elemi pálya és 
végpontja
megegyezik 
kezdőpontjával,
így (7) szerint a (8)
összefüggés valóban teljesül.
Q.E.D.
3.2. definíció
Egy X=
véges halmaz
önmagára történő leképezését n-edfokú permutációnak nevezzük.
Az X halmaz két valódi részhalmaza közötti
kölcsönösen egyértelmű megfeleltetést részleges
permutációnak nevezzük.
A permutációk, illetve részleges permutációk
jelölésére a továbbiakban az úgynevezett leképezéses írásmódot fogjuk
használni.
Például, ha 
, akkor például permutáció
(A felső sor az ős,
részleges permutáció 
az alsó a képelemeket
tartalmazza.)
3.2. Tétel
Legyen 
=(P,E) irányított
gráf. Bármely 
-beli elemi pálya felírható
P egy részleges
permutációjaként.
Bizonyítás
Tekintsük az
-beli elemi pályát és legyen az őselemek, illetve képelemek
halmaza rendre a következő:
(3.3) 
(3.4)
Az elemi pálya definíciója szerint X=P,
Y=P eset csak egyetlen esetben állna elő, ha
és X=Y,
azaz U egyetlen hurokélből áll, amit az
feltétel kizár.
Tekintsük tehát a következő 
leképezést:
(3.5)
Könnyű belátni, hogy a (3.5) szerinti 
leképezés
kölcsönösen egyértelmű.
(3.3), (3.4), (3.5)
pontosan eleget tesz a 8.definíció
feltételeinek, azaz 
a P
halmaz egy részleges permutációja, melynek leképezéses alakját (3.6)
mutatja. (Az U pálya leképezéses alakját L(U)-val jelöljük.)
(3.6) L(U)= 
Q.E.D.
3.3. definíció
Két leképezés
szorzatán
ezek egymás utáni végrehajtását értjük.
A 3.1. és
3.2. tétel alapján kimondhatjuk, hogy
egy 
=(P,E) irányított
gráfban bármely U pálya felírható P-beli részleges permutációk szorzataként. Azaz
(3.2) alapján:
(3.7) 
Mivel a leképezéses alakban az oszlopok (ős-kép
párok) sorrendje felcserélhető,
így megtehetjük, hogy minden pálya leképezéses alakját az ősöknek valamilyen
rögzített (például növekvő indexű) sorrendje szerint írunk fel. Ez a lehetőség
kínálja a pályák összehasonlításának egy algoritmusát, melyet a következőkben
ismertetünk.
4. Az algoritmus
Az előzőkben leírtak alapján minden 
=(P,E) irányított
gráfbeli U pályához egy 
=n oszlopból
álló 
mátrix rendelhető
az alábbi definíció szerint:
4.1. definíció
Tegyük fel, hogy
L(U) a (3.7) alakú
felbontásban k részleges permutációt
tartalmaz, akkor sorainak száma k.
Jelöljük a mátrix i-edik sorának j-edik elemét 
-vel, ekkor
(4.1) 
A 
jelölés azt jelenti,
hogy a 
őselem képe 
Például, ha
, akkor
tehát k=3
és 
a következő: 
Két tetszőleges
gráfbeli pálya közös szakaszait kezdőpont szerint csoportosítjuk (ez a
mátrix alapján kézenfekvően adódik).
Algoritmusunk leírásához jelöljük a két összehasonlítandó pályát U
és U’-vel, a hozzájuk rendelt
leképezés mátrixokat rendre 
és 
-vel. A két
pálya 
szögpontból kiinduló
közös szakaszait az alábbi algoritmussal határozzuk meg:
1. START
2. i=0
3.
i=i+1, j=0
4. Ha 
akkor menj 24.-re Magyarázat: i:
az 
mátrix sorindexe
j:
az 
mátrix sorindexe
k: a 10.definició szerinti érték
5. t=1
6. Ha 
akkor menj 3.-ra
7. j=j+1
8. Ha 
akkor menj 3.-ra
9. Ha 
akkor menj
7.-re
10. s=i, z=j
11. t=
a két pálya közös
szakaszának új eleme)
12. Ha 
akkor menj 16.-ra
13. Ha 
akkor menj 20.-ra
14. Ha 
akkor menj 5.-re
15. Menj
11.-re
16. s=s+1
17. Ha 
akkor menj 5.-re
18. Ha 
akkor menj 5.-re
19. Menj
13.-ra
20. z=z+1
21. Ha 
akkor menj 5.-re
22. Ha 
akkor menj 5.-re
23. Menj
14.-re
24. END
Az algoritmus bármely 
szögpontból kiinduló
közös szakaszok meghatározására hasonlóan működik, csupán az 5.lépésben
t=r áll.
Érdemes felhívni a figyelmet arra, hogy ez az
algoritmus a két pálya összes közös szakaszát előállítja és az algoritmus
könnyen párhuzamosítható egy megfelelő méretű mátrix memória tárolóval.
Sokkal egyszerűbb a feladat, ha a teljes U’
pályát keressük az U pályában. Ekkor ugyanis U’
első eleme a vizsgálandó kezdőpont és pontosan l(U’) lépésben a kérdés
eldönthető. Lássunk egy szöveges illusztrációt:
U=(versirodalom) a d e
i l m
o r s v
a d e
i l m o
r s v
U’=(dal) 
a d e
i l m
o r s v
U’’=(iroda) 
A „d”
illetve „i” oszlopból indulva U’-t két lépésben,
U’’-t négy lépésben megtalálja
az algoritmus.
5. MEGJEGYZÉSEK AZ ALGORITMUSRÓL
Tegyük fel, hogy az
összehasonlítandó U és
U’ pályák leképezéses alakja ( L(U), L(U’) ) 
darab részleges
permutáció szorzataként áll elő, valamint a
szögpontból kiinduló
közös szakaszaik átlagos hossza l.
Ekkor az algoritmus átlagosan
(5.1) N(U,U’)= 
számú elem összehasonlítást végez az összes közös
szakasz megtalálásához.
Ugyanezen feltételek mellett például shifteléses
eljárás esetén az összehasonlítások száma
N’(U,U’)=
a közös szakaszok
hosszától függetlenül. Mivel 
(fenti
illusztrációnkban például 
), így majdnem mindig
teljesül, hogy 
.
Érdekes annak a speciális esetnek a vizsgálata,
amikor az egész U’ mintát keressük az U jelsorozatban. Napjaink informatikai rendszereiben ez
kulcsfontosságú és rendkívül gyakori feladat (pl.: kulcs alapján történő
keresés, szövegkiemelés, helyesírás ellenőrzés).
Ebben az esetben ugyanis algoritmusunk szempontjából
lényegtelen 
értéke, hiszen az
összehasonlításokat csupán az U’ első eleme által meghatározott mátrix
oszloptól kezdve l(U’) lépésben végezzük el és az összehasonlítások
során biztosan eldönthető, hogy U’ része-e
U-nak.
Ugyanez a feladat az ismert Knuth-Morris-Pratt algoritmussal kb.
2(l(U)+l(U’)-2) összehasonlítást igényel
(lásd [5]).
IRODALOM
[1] C. Berge:
Graphs and Hypergraphs
North-Holland Publishing Company, 1973.
[2] Busacker, R.G.-Saaty, T.L.: Véges gráfok és hálózatok
Műszaki
Könyvkiadó, Budapest, 1969.
[3] Dénes, T.:
Signal series as sequential systems
III. Hungarian Computer Science
Conference, Budapest 1981.
[4] Farrar, J.C.-Nievergelt, J.-Reingold,
E.M.: Matematikai problémák
megoldásainak
számítógépes
módszerei
Műszaki Könyvkiadó, Bp. 1977.
[5] M.Crochemore, W.Rytter: Text algorithms
Oxford University Press,
1994.