Szolnoki Tudományos Közlemények XII. Szolnok, 2008.
Prof. Dr. POKORÁDI LÁSZLÓ RENDSZEREK ÉS FOLYAMATOK GRÁF-MODELLEZÉSE Egy technikai rendszer vagy műszaki folyamat vizsgálatának első fontos állomása az elemek, illetve állapotok közti — sok esetben bonyolult kölcsönhatásokat is jelenthető — kapcsolatok tényének feltárása és gráfban történő ábrázolása. A rendszerelemek közti kapcsolatok (például jel- vagy anyagáramok) leíró gráf elemzésével meg tudjuk határozni, hogy egy elem melyik más elemekre gyakorol-e valamilyen szintű hatást. A tanulmány célja egy a Szerző által kidolgozott, jól algoritmizálható módszer bemutatása, mellyel a vizsgált rendszer elérhetőségi mátrixa meghatározható.
1. BEVEZETÉS A rendszerelmélet gyakorlati alkalmazásaiban, a megoldás lehetőségének megítélésében a vizsgált rendszer mérete az egyik legfontosabb tényező. A méret ekkor durván a rendszerben szereplő elemek számát jelenti, ahol az elemeket „intuitív” értelemben kell definiálnunk. A diszkrét állapotterű — vagy valamilyen módon így approximált — (például karbantartási) folyamatok ábrázolása, szemléltetése a lehetséges állapotok, és az állapot-váltások alkotta gráfok segítségével történhet. Egy rendszert elemzése során először annak diszkrét gráfjával (vagy hálózatával) kell reprezentálni. Ez számos fizikai (például elektromos, mechanikus, hidraulikus) rendszer esetén megtehető. Sőt, parciális differenciálegyenletekkel leírt rendszerek gráfmodellje is megkonstruálható [6]. A defektoszkópia egy adott szerkezeti rész műszaki állapotának meghatározása, valamely kijelölt vagy megengedett minőségi szinthez történő hasonlítás alapján. Defektószkópiai rendszervizsgálat során a különféle elemek, aggregátok állapotáról csak bináris (jó – hibás) információkat állapíthatunk meg, illetve azok hatásait elemezzünk. A tanulmány célja a rendszerek defektószkópiai elemzése során alkalmazható — könnyen algoritmizálható — gráfelméleti, mátrixaritmetikai módszer bemutatása. —1—
A cikk az alábbi fejezetekből áll: A 2. fejezetben a gráfelmélet, illetve annak — a későbbi vizsgálat szempontjából fontos — (matematikai) alapfogalmait ismertetjük. A 3. fejezetben a rendszerek elérhetőségi mátrixai meghatározásának egy, a Szerző által kidolgozott mátrixaritmetikai eljárását mutatjuk be. A 4. fejezet egy rövid esettanulmányon keresztül szemlélteti a módszer alkalmazását.
2. GRÁFELMÉLETI ALAPOK Matematika-történeti források szerint az első gráfelméleti munka a Szentpétervári Tudományos Akadémia közleményeiben jelent meg 1736-ban, mikor is Leonhard Euler (1707-1783) svájci matematikus, aki ekkor az akadémia meghívására Oroszországban dolgozott, megoldotta a königsbergi-hidak problémáját. Königsberg (mai nevén Jekatyerinburg) a Balti-tenger Gdanski öble közelében a Pregolja (Pregel) folyó két partján és a folyó két szigetén terült el. A folyó két szigetét hidak kötötték össze egymással és a partokkal is (1. ábra). Felvetődött a kérdés, tehetünke olyan sétát, hogy minden hídon pontosan egyszer menjünk át, és a séta végén visszaérjünk a kiindulási pontunkhoz. Euler általánosságban oldotta meg a feladatot. Megállapította, hogy a kérdésre csak tagadó válasz adható: a hidakat nem lehet a kívánt módon bejárni. (Érdekesség, hogy később a mérnökök „megoldották” a königsbergi hidak problémáját — építettek még egy hidat.)
1. ábra A köningsbergi hidak (forrás: [8]) A gráfelméletnek és mérnöki alkalmazásának kiterjedt matematikai és műszaki szakirodalma található. Például az [1]; [2]; [4]; [5]; [6]; [7] és [9] publikációk. A gráf olyan alakzat, amely pontokból és egyes pontpárokat összekötő (nem feltétlenül egyenes) vonaldarabokból áll. Matematikai megfogalmazásban a G(P;E;f) gráfon olyan alakzatot értünk, amely a P pontokból és bizonyos pontokat összekötő E vonaldarabokból áll. A P halmaz elemeit pontoknak (esetleg gráf szögpontjainak vagy csúcsainak), az E halmaz elemeit pedig a gráf éleinek nevezzük [1]. A fenti jelölésben szereplő f függvény az E halmazt képezi le a PxP-re, azaz bármely e élhez hozzárendel egy pontpárt a P halmaz elemei közül. Ezért f-t szokás illeszkedési leképezésnek is nevezni [2]. Irányított gráfról akkor beszélünk, ha az élek végpontjainak sorrendjére is tekintettel vagyunk. A gráfokat általában grafikusan ábrázoljuk — lásd a későbbi esettanulmányt szemléltető 3. ábrát. A gáfok másik ábrázolási, leírási módja pedig a belőlük képezhető különböző mátrixok alkalmazása — lásd például a (10) egyenletet.
—2—
A gráf szögpontjai közti kapcsolatokat az úgynevezett csúcs- (szomszédossági-, vagy adjacencia-) mátrixszal lehet táblázatosan megadni. Az irányítatlan gráf — A = [aij]-vel jelölt — szomszédossági mátrixa i-edik sor j-edik elemének aij értéke jelöli a pi és a pj szögpontokat összekötő élek számát [1]. Irányított gráf esetén az A mátrix i-edik sor j-edik elemének aij értéke a pi szögpontból induló és a pj végpontú élek számát jelöli. A főleg rendszertechnikai szakirodalmak nem a fentiekben leírt definíciókat használják. A rendszerek és folyamatok modellezése szempontjából a legfontosabb kérdés a rendszer elemei, a folyamat állomásai közti kapcsolat létének feltárása. Ezért azt nem szükséges vizsgálnunk, hogy a szomszédos pontok között vannak-e többszörös élek és hurok élek. Így a továbbiakban az alábbi definíciókat fogjuk alkalmazni: Az irányítatlan gráf A-val jelölt szomszédossági mátrixa i-edik sor j-edik elemének értéke 1, ha az i-edik és a j-edik szögpontokat közvetlenül összeköti a gráf valamely éle, illetve 0, ha nem. Matematikailag felírva: 1, ha van olyan él, amelynek két végpontja pi és p j aij = 0, minden más esetben
.
(1)
Irányított gráf esetén az A mátrix aij eleme pedig: 1, ha van pi - böl induló és p j - be vezető él aij = 0, minden más esetben
.
(2)
Könnyen belátható, hogy a korábban definiált csúcsmátrixból a szignum függvény felhasználásával — lásd (6) és (7) egyenletek — megkapható a fenti definíció szerinti szomszédossági mátrix.
3. AZ ELÉRHETŐSÉGI MÁTRIX MEGHATÁROZÁSA Egy rendszer elemei közti összetett kapcsolatokat, egymásra hatásokat a rendszer vizsgálati gráfjának úgynevezett elérhetőségi mátrixa jellemzi. Egy m szögpontból álló gráf elérhetőségi mátrixán azt az m sorból és oszlopból álló Zmxm = [zij] négyzetes mátrixot értjük, ahol: 1, ha a pi - csúcsból a p j szögpont elérhető zij = 0, ha nem
(3)
Egy adott rendszer vagy diszkrét állapotterű folyamat gráfelméleti vizsgálatánál az egyik fő feladat az elérhetőség, hatásgyakorlás tényének egzakt feltárása — azaz az elérhetőségi mátrix meghatározása. Ez a mátrix egy rendszer esetén például azt mutatja meg, hogy az egyik (az i-edik) —3—
elem anomáliája, meghibásodása hatással van-e a másik (j-edik) elem működésére. Valamely folyamat vizsgálata esetén pedig megadja azt, hogy mely állapotokból lehet mely állapotokba eljutni. A [4] irodalom alapján az elérhetőségi mátrixot a szomszédossági mátrix hatványai segítségével tudjuk felállítani. Ehhez a mátrixszorzás szabályainak megfelelően határozzuk meg az mxm méretű A adjacencia-mátrix A2 jelű négyzetmátrixának aij[2 ] elemét az: m
aij[2 ] = ∑ ais asj
(4)
s =1
egyenlettel. A korábbi definíciókat felhasználva kijelenthetjük, hogy
ais asj = 0
,
ha nem tudunk egy lépésben eljutni az i-edik szögpontból az s-edikbe (azaz ha ais = 0), vagy ha az s-edikből a j-edikbe (vagyis ha asj = 0). Ha egy-egy lépésben el tudunk jutni pi-ből ps-be és ps-ből pj-be, azaz, ha ais = asj = 1:
ais asj = 1
.
Így a (4) egyenlettel meghatározott aij[2 ] értéke — a fenti szorzatok szummázása következtében — azt adja meg, hogy a gráf i-edik szögpontjából hány különböző úton tudunk két lépéssel eljutni a j-edik szögpontba. Fontos itt megjegyezni, hogy jelen tanulmányban az utak különbözőségén az általuk érintett szögpontok, vagy azok sorrendjének különbözőségét értjük. Az ugyanazon szögpontokat megegyező sorrendben tartalmazó, de más élekből álló utakat azonosaknak tekintjük. Ilyen eset fordulhat elő, ha a gráfon belül két szögpontot egynél több él köt össze. Ezt az egyszerűsítő feltételt azért vezetjük be, mert végső célunk az elérhetőség vagy el nem érhetőség tényének megállapítása a tényleges utak egymástól függetlenül. Vizsgálatunk fő célja a gráfok szögpontjai közt meglévő kapcsolatok feltárása. Könnyen belátható az A szomszédossági mátrix Ak-val jelölt k-adik hatványmátrixának aij[k ] eleme azt mutatja meg, hogy k lépésben az i-edik szögpontból a j-edikbe hány egymástól — a fenti értelmezés szerinti — független úton lehet eljutni. Ennek a kijelentésnek pontos, matematikailag egzakt bizonyítása a [4] irodalomban található meg.
—4—
A hatványmátrixok k
Hk = ∑ An
(5)
n =1
összegével kapott Hk összegmátrix hij[k ] eleme azt adja meg, hogy legfeljebb k lépésben az i-edik szögpontból a j-edikbe hány — egymástól független — úton lehet eljutni. Képezzünk a Hk mátrixokból Sk jelű mátrixokat az alábbi függvény szerint: S k = sign H k [k ]
[k ]
(6)
sij = sign hij
ahol: 1, ha η > 0 signη = 0, ha η = 0 − 1, ha η < 0
(7)
és nevezzük el ezeket a Hk mátrix szignum mátrixának. Az így kapott szignum mátrixok sij[k ] elemei azt adják meg, hogy legfeljebb k lépésben a gráf pi szögpontjából el lehet-e jutni a j-edik szögpontjába — a (3) egyenlettel megadott elérhetőségi mátrixszal analóg módon — azaz:
1, ha a pi - csúcsból a p j szögpont maximum k lépésben elérhető sij[k ] = 0, ha nem
(8)
Mivel egy m szögpontból álló gráfban a leghosszabb lehetséges élsorozat maximum m élből állhat, mely — a kiindulási szögpont kivételével — minden hozzá tartozó szögpontot csak egyszer érint — azaz a lehetséges leghosszabb kör, vagy pálya —, a fenti mátrixműveleteket végezzük el mszer. Az így kapott Sm szignummátrix lesz a vizsgált gráf elérhetőségi mátrixa. A fentiek alapján megállapítható, hogy egy m szögpontból álló gráf Amxm szomszédossági mátrixának ismeretében a Zmxm elérhetőségi mátrixa m
Z = sign∑ A n n =1
egyenlettel meghatározható [6].
—5—
(9)
4. HELIKOPTER FÉKLEVEGŐ RENDSZER VIZSGÁLATA A fentiekben leírt módszer szemléltetése érdekében határozzuk meg a 2. ábrán látható helikopter féklevegő rendszer elérhetőségi mátrixát a rendszer állandósult (befékezett) állapotát vizsgálva. A működés elemzése során megállapítható, hogy a 10, 12 és 13 jelű elemek passzívaknak tekinthetők. A különféle szűrök nem játszanak szerepet a rendszer állandósult üzemállapotai során, még a 11 jelű fedélzeti feltöltő csonknak szerepe csak a rendszer karbantartása során van. A 9 jelű visszacsapó szelepek is passzívnak tekinthetők. De, mivel azok meghatározzák az adott csőszakaszban a sűrített levegő áramlásának irányát, így a rendszer működését leíró gráfot „irányítottá teszik”. A fenti megfontolások, és a részegységek működésének elemzése alapján tudjuk felvenni a rendszer irányított gráfját, amit a 3. ábra szemléltet.
2. ábra Mi-8 Hip helikopter levegőrendszerének elvi rajza (forrás: [3]) 1– vezérlő berendezés; 2 – redukciós gyorsító; 3;4 – nyomásmérők; 5 – légsűrítő; 6 – levegőtartályok; 7 – fékberendezések; 8 – nyomásautomata; 9 – visszacsapó szelep; 10;13 – levegőszűrők; 11 – feltöltő csonk; 12 – ülepítő szűrő.
3. ábra A vizsgált rendszer gráfja (forrás: Szerző) —6—
A (2) egyenlet alapján felírt szomszédossági mátrix:
0 0 0 0 A= 0 1 0 0
1 0 0 0 0 1 1 0
0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 0 1 1 0 0
.
(10)
A fenti A mátrixból kiindulva, a (4); (5); (6), valamint a (9) egyenletek felhasználásával a vizsgált gráf elérhetőségi mátrixa:
1 1 0 0 Z= 1 1 1 1
1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 1
0 0 0 0 0 0 0 0
1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 1
.
(11)
Természetesen a bemutatott egyszerű példa esetén a gráf (vagy már a rendszer elvi rajz) megtekintéséből is belátható, hogy: 4 4
az 5 jelű légsűrítőre nem gyakorol hatást a rendszer valamely más elemének meghibásodása — a Z mátrix 5. oszlopa csak zérus elemeket tartalmaz; a 3 és 4 jelű nyomásmérő műszerek üzemzavara, meghibásodása nem gyakorol hatást a többi elem működésére — mivel a mátrix 3. és 4. sorai csak zérus elemeket tartalmaznak.
Természetesen, egy összetettebb rendszer, tehát bonyolultabb gráf esetén a fenti bekezdésben tett megállapítások belátása könnyen nem lehetséges, így az ismertetett módszer alkalmazása szükségessé válhat.
FELHASZNÁLT IRODALOM [1] [2] [3] [4]
ANDRÁSFALVI, B., Gráfelmélet, Polygon, Szeged, 1997., pp. 174. BRONSTEJN, I. N. – SZEMENGYAJEV, K. A. – MUSIOL, G. – MÜHLIG, H., Matematikai kézikönyv, Typotex, Budapest, 2006, pp. 1209. ДАНИЛОВ, В.А., Вертолет Ми–8, Транспорт, Москва, 1988, pp. 278. FAZEKAS, F., Alkalmazott matematika II., egyetemi jegyzet, Tankönyvkiadó, Budapest, 1979., pp. 347. —7—
[5] [6] [7] [8] [9]
POKORÁDI, L., Karbantartás elmélet, DE MFK, Debrecen, 2002., http://www.mfk.unideb.hu/userdir/pokoradi/karb_elm.pdf, pp. 101. POKORÁDI, L., Rendszerek és folyamatok modellezése, Campus Kiadó, Debrecen, 2008., pp. 242. SZABÓ, I., Gépészeti rendszertechnika, Műszaki Könyvkiadó, Budapest, 1986., pp. 541. SAIN, MÁRTON, Matematikatörténeti ABC, Tankönyvkiadó, Budapest, 1977, pp. 253. ZADEH, L.A. – POLAK, E., Rendszerelmélet, Műszaki Könyvkiadó, Budapest, 1972., pp. 476.
—8—
