Hidrológiai Közlöny 1972 (52. évfolyam)

12. szám - Dr. Vágás István: Folyóhálózatok gráf-elmélete

556 Hidrológiai Közlöny 1972. 12. sz. Folyóhálózatok gráf-elmélete Dr. VÁGÁS ISTVÁN* a mflszaki tudományok kandidátusa Árvízi helyzetképeink, árvízi előrejelzéseink megbízhatóságát — az egyedi árhullám-levonulás törvényszerűségeinek megismerése mellett — a vízgyűjtő-rendszer fő- és mellékfolyóinak egymásra hatását figyelembe véve fokozhatjuk. Az egymásra hatás vizsgálatára az irányított gráfok, ill. az ezekből képzett háló- és fadiagrammok alkalmas eszköznek ígérkeznek. Ezeket a diagrammokat azonban az információ-elmélet is kiterjedten hasznosítja. Célszerű tehát a vízgyűjtő folyóhálózati rendszerek elméletét az információ-elmélet, í'.zon belül itt főként a kódolás-elmélet megállapításainak értelmezése és hasznosítása segítségével felépítenünk. Folyóhálózat, mint irányított gráí A gráf, mint ismeretes, csúcspontokból és élekből álló topológiai alakzat. Az irányított gráfnak minden éle irányítással is el van látva. A fa olyan összefüggő gráf, amely nem tartalmaz egymásba záródó éleket (köröket). Képe a fák elágazó ágrendszerére emlékeztet, s ha a fa bármelyik ágát elmetszenénk, maga a fa is két, össze nem függő részre esnék szét. Az adott csúcspontban gyökerező irányított fát, azontúl, hogy irányítás nélküli értelemben is fát alkot, még az is jellemzi, hogy a gyökér pontjából bármely más csúcspontjába vezető útja is összefüggő, a fa irányításának megfelelően irányított út (1. ábra). Két, vagy több gráf közötti viszony tekinteteiében, mint a legfontosabbat, az izomorf iát emelhetjük ki. Izomorf gráfok csúcsai között olyan kölcsönösen egyértelmű megfeleltetés adható, hogy két csúcs az egyik gráfban akkor és csak akkor van éllel összekötve, ha a megfelelő két csúcs a többi, izomorf gráfban is azonos irányítású éllel van összekötve [1, 2, 3, 4, 5]. Ha a folyók hozzáfolyás (elfolyás) nélküli szakaszait éleknek, az összefolyási pontokat pedig csúcspontoknak, s a víz folyási irányát a gráf irányításának tekintjük, úgy bármelyik vízgyűjtő hálózat általánosságban irányított gráfot értelmez. Még pontosabb meghatározásra is módunk van a továbbiakban. Ha eltekintünk a bifurkáció, árhullám-megcsapolás, mesterséges vízkivétel, árapasztó- és összekötő csatorna, valamint a sziget eseteitől, úgy a vízfolyási hálózat rendszere gráfelméletileg: fa, és ezen belül bármely csúcspontra a vízfolyás irányának megfordít ásóival ültethetünk irányított fát, Tanulmányunkban kiemelten csak a fa-alakzatokkal foglalkozunk, minthogy — az előfordulás gyakorlati eseteiben ezt tartjuk jellegzetesnek, — a vízgyűjtő hálózatok ide nem tartozó esetei is jórészt visszavezethetők a fa-alakzatokra. A fa-alakzatokra vonatkozóan még egy alapvető megjegyzést teszünk. Minthogy a természetes * Alsótiszavidéki Vízügyi igazgatóság, Szeged. o— Kjor / Csúcspont Grál Irányított- gróf I. ábra. Gráf-elméleti alapalakzatok Hue. 1. OcHOeime (ßopMaquii epacfi-mcopuu Fig. I. Fundamental configurations in the graph theory vízfolyásoknál kizártnak tekinthetjük, hogy egy „csúcspontban" kettőnél több „él" összefuthasson, azaz kizárjuk a többszörös vízbetorkolás esetét, a folyami hálózatot leképező fa: bináris fa. Ez lehetővé teszi, hogv a kettes számrendszerben rejlő előnyöket kihasználhassuk. Folyóhálózat, mint bináris la A folyóhálózat minden elemének, azaz az azt értelmező faalakazat minden élének (összefüggő élhalmazának) egyértelmű elnevezése van, hiszen minden vízfolyást földrajzi neve jelöl meg és különböztet is meg egyúttal. Ez a ténv az alapja annak, hogy a faalakzat minden ága irredúcibilis kóddal jellemezhető. A bináris elágazások következtében mindenkor lehetséges és mindenkor a legegyszerűbben alkalmazható a bináris kód. Bármely kódközlemény kódjelekből és az ezekből összeállított kódszavakból áll. A bináris kód két kódjele: a 0 és az I számjegy. A kódolási eljárás olyan utasítás, amely valamely fogalomhoz kódjelekből álló sorozatot: kódszót, vagy kódszavakat rendel hozzá.