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
Dr. Vágás I.: Folyóhálózatok gráf-elmélete Hidrológiai Közlöny 1972. 12. sz. 561 kódolás során előforduló leghosszabb kódszó hoszsza L n bit. A további, ennél rövidebb kódszavak hosszúsága legyen L v L., ... Li ... bit. Ha valamelyik Li hosszúságú ágat a kódfán képzeletben fj„ hosszúságúra egészítenénk ki, ezt 2 Ln~ Li féleképjKin végezhetnénk el, tekintve, hogy éppen ennyi él „hiányzik" a kódfán a teljességhez (5. ábra). Ezt az elvet minden kódszóra érvénvesíthetZ4 7 1"' L i'2 , 1 0/ L, ' 1 Ln L, = 2 / Ln /1 Lt = 2 Ln -Li = 1 (i- o Lt = / f ' t-3 3 Ln -Li = 0 / / U ' 3 Ln -L„ = 0 -o 1 In ' 3 2 L"' L*= 1 n Ln = a 5. ábra. A Kruft— Fu.no összefüggés igazolása Puc. 5. nodmoepOeiiue 83auMoceit3u Kpatftm—®ÜHO Fig. 5. Verification of the Kraft — Fano relationship jiik, és meghatározhatjuk, hogy összesen mennyi kiegészítési lehetőségünk van a teljes kódfa képzéséhez. Másrészről — ha a teljes kódfa kiegészítendő volna'— megállapíthatjuk, hogy a maximális kiegészítési lehetőség 2 /-». A többi kiegészítés összege vagy ennyi, vagv ennél kevesebb, tehát: 2 LnLi + 2 L'i~ Li+ . . . +2'-»-'"»-f . . . + 2 J-n-!'II^ L2 L" (6) A Kraft-Eano tétel ebből 2'-»-nel való egyszerűsítésből adódik: 2-z-i +2~ l* + . . . 1 (7) lí tétel fennállása szükséges és elégséges feltétele annak, hogy bármely bináris kód irredúeibilis legyen. Minthogy azonban a folyóhálózat minden tagjához a tapasztalat szerint mindenkor irredúeibilis kód rendelhető, kimondhatjuk: A Kraft—Fano tétel bináris, vagy binarizálható folyóhálózati rendszerekben mindenkor érvenyes. ö. példa. Ellenőrizzük a Kraft-Fano tételt a Tisza vízrendszerének I. példában figyelembe vett folyóin. A 2. példában már megadott kódszó hosszakat figyelembe véve az ott közölt összeadásból kit űnik, hogy az ott összeadott törtszámok összege éppen I. Ez a tétel határesete. Összefoglalás A tanulmányban a folvóhálózatok gráf-elméleti leírásának alap-kérdéseivel foglalkoztunk. Megállapítható egyrészről, hogy a folyók hálózata, mint bináris fa-alakzat, az információ-elmélet tételeinek megfelelően jellemezhető, és az entrópia fogalma az árhullám-találkozások jellemzésére is felhasználható. Az entrópia maximuma az árhullámok találkozása szempontjából a legveszélyesebb helyzetre utal. A l'olvóhálózat ot jellemző gráf másrészről egy kezdőpont értelmezésével és az abból indított élek segítségével folyamat-ábrává — hálódiagrammá — is kiegészíthető. A folyamat-ábrán az ismert „kritikus út." módszerrel állapítható meg, hogy milyen időkésleltetések mellett várható a mellékfolyók árhullámainak egymásra futása, és mikor nines ilyen veszély. A tanulmány következtetései elsősorban a Tisza vízrendszerének, vagy az ahhoz hasonló vízrendszereknek tanulmányozása során hasznosíthatók. IRODALOM [ 1J Busacker, U. G., iSaaty, T. L.: Véges gráfok ós hálózatok. Műszaki Könyvkiadó, Budapest, 1909. |2] Fritz József: Bevezetés az információelméletbe. Tankönyvkiadó, Budapest, 1971. Rakt. sz. 29199. [:t| Holló Gyula: Vízgyűjtő rendszerek modellezése vélet len jellegű gráfsémákkal. Műegyetemi Tudományos Diákkör számára készített dolgozat. Kézirat, 1971. [4] Reza, M. Fazlolluh: Bevezetés az információelméletbe. Műszaki Könyvkiadó, Budapest, 19GG. [5] Vágás István: Az előrejelzés megbízhatósága. Vízügyi Közlemények, 1971. 3. rpat})-TeopH» peiHbix ceTeü JJ-p Baeaui, 11. B flatinoii CTATBE airrop 3amtMaeTC>t OCHOBHUMH BonpocaMii omteamm rpa(J)-Teopnn pciHbix CCTCÍÍ. EbiJio VCRAHOBJICHO c OAHOÜ CTopoHbi, MTO pcmaH ceTb, xai< űuiiapnait, depeeooőpajiiau ifjopMatfun ,MO>KCT GBITB xapaKTcpH30BaHa COOTBCTCTBCHHO TesucaM meopuu-un(fiopMaifuu H TAKHM ()Gpa30M nonsiTtte íiimponuu MOJKCT OblTb IipHHJlTO H AJUl XapaKTCpitCTHKH BCTpCIIt naBOAOMHI>1X BOJIH. MaKClIMVM UHTpOnHH C TOWKH 3pCHH5I BCTpC'III naBOAOWHbix BOJiH noKa3WBaeT ita caMoe ottacuoe IIOJIO>Kcmie. XapaicrepHwfi ;IJI>I pcMHoil cent rpatji c ,ipvroií CTOpOHbl C TOJIKOBaHHeM OJIHOÍÍ HaMaJlbHOÍi TOHKIt II II/IVIUIIX OT 3T0ÍÍ TO'IKU I paHCft MOJKCT ŐblTb AOIIOJTHCH B 11 pOI/eCcityw jniopy- o cemeeyio öuaepaMMy. Ha nponcccuoii aniope npii noMomit ii3Becrnoro Merő/iá „KpumwiecKoeo nymu" MOIKHO oupe;iejtitTb TO, MTO tipit Kaxnx 3a.Mc4.ne1IU51X BpeMCÚH MOJKHO 0>KltflaTb Ita IIJiaCTblBaHUC BOJIH naBOÄKOB npHTOKOB ti Kor^e ner Tai<oií onacHOcrii. BbiBOAbi craTbii 11 ncpüvío oicpenb AJIH p. Tiicw ti AJISI tiaviemiH aHajiorniHbix pewiibix CCTCÍÍ MOPVT 6wTb ucIIOJIb30BaHW. Graph theory of river systems By Dr. Vágás, I. (Candidate of Techn. Science The fundamental problems related to the description of river systems by the graph theory have been considered. It is concluded on the one hand that river systems as binary trunk-configurations can be described in accordance with the theorems of information theory and that the concept of entropy may be applied to describe the coincidence of flood waves. Maximum entropy indicates the most critical situation for the confluence of flood waves from different watercourses. The graph representing the network of rivers, oil the other hand, may be completed — by interpeting an origin and edges started therefrom — into a flow-chart, or PERT-diagram. In this diagram the familiar "Critical path" method may be used in estimating the time delays at which the superimposement of flood waves from the tributaries is to be expected and the conditions where no such danger exists. The conclusions arrived at in the paper lend themselves primarily to the study of river systems similar to that of the Tisza River.
