Strahlerovo číslo

Schéma znázorňující Strahlerovu klasifikaci vodních toků Strahlerovo číslo (někdy také Horton-Strahlerovo číslo) se v matematice používá k označení jednotlivých větví ve stromových digramech.

Poprvé čísla použili Robert E. Horton a Arthur Newell Strahler pro označení vodních toků v hydrologii. +more Podle Strahlerovy klasifikace vodních toků jsou přítoky hierarchicky číslovany podle velikosti. Metoda se také využívá při analýze L-systémů a hierarchicky uspořádaných biologických struktur, jako jsou dýchací a oběhové soustavy živočichů, při alokaci registrů pro kompilaci vysokoúrovňových programovacích jazyků a při analýze sociálních sítí. Alternativní systémy klasifikace vodních toků vyvinuli R. L. Shreve a J. H. Hodgkinson a kol. J. S. Smart předložil statistické srovnání Strahlerova a Shreveho systému, spolu s analýzou délek toků a internetových odkazů.

Definice

Všechny stromové diagramy jsou v tomto kontextu orientované grafy větvené od kořene k listům. Stupeň vrcholu (uzlu) v diagramu odkazuje na počet jeho dceřiných větví. +more Strahlerovo číslo je uzlům v grafu přiřazeno ve vzestupném pořadí dle následujícího klíče:.

* Pokud je uzlem list (nemá žádné dceřiné větve), je jeho Strahlerovo číslo rovno jedné; * pokud má uzel jednu větev se Strahlerovým číslem i a všechny ostatní větve mají Strahlerovo číslo menší než i, pak Strahlerovo číslo uzlu je i; * pokud má uzel dvě nebo více větve se Strahlerovým číslem i a žádnou větev s vyšším číslem, pak Strahlerovo číslo uzlu je i+1.

Strahlerovo číslo stromového diagramu je číslo jeho kořenového uzlu.

Algoritmicky se čísla přiřazují metodou prohledávání do hloubky a následným procházením stromu. Stejná čísla mohou být také generována pomocí procesu prořezávání, během kterého dochází v několika fázích k zjednodušení stromu. +more V každé z fází jsou odstraněny všechny listové uzly a větve všech jednostupňových uzlů vedoucích k listům. Strahlerovo číslo uzlu je pořadí fáze, kterou by během tohoto procesu došlo k jeho odstranění. Číslo celého diagramu je počet fází potřebných k odstranění všech jeho uzlů. Strahlerovo číslo stromového diagramu je odpovídajícím způsobem možné definovat jako výšku největšího úplného binárního stromu, který může být homeomorficky vložen do daného stromu. Strahlerovo číslo uzlu ve stromovém diagramu obdobně odpovídá výšce největšího úplného binárního stromu, který lze vložit pod tento uzel.

Každý uzel se Stráhlerovým číslem i se musí skládat alespoň ze dvou uzlů s číslem i-1, čtyř uzlů s číslem i-2 atd. , a alespoň 2i−1 listů. +more Nejvyšší hodnota Strahlerova čísla pro stromový diagram s n uzly je proto log2 n + 1. Pokud však diagram nevytvoří úplný binární strom, bude číslo nižší. U náhodně vybraného binárního stromu s n uzly se předpokládaná hodnota indexu kořenu nejpravděpodobněji blíží log4n.

Aplikace

Říční sítě

V hydrologii se Strahlerovo číslo používá ke klasifikaci vodních toků. Každý tok v povodí je vnímán jako uzel stromového diagramu. +more Soutokem dvou toků prvního řádu vzniká tok druhého řádu. Dva toky druhého řádu tvoří po soutoku tok třetího řádu atd. Po soutoku toku vyššího s tokem nižšího řádu se řád hlavního (vyššího) toku nemění. Pokud se tedy do toku druhého řádu vlévá tok prvního řádu, je tok nadále označován je tok druhého řádu. Ke změně řádu dochází teprve po soutoku dvou toků druhého řádu. V hydrologii musí být stejně jako v případě stromových diagramů tok i-tého řádu napájen alespoň 2i−1 různými přítoky prvního řádu. R. L. Shreve vyslovil hypotézu, podle které lze Horton-Strahlerovu klasifikaci uplatnit na všechny toky na Zemi. Pozdějším potvrzením hypotézy bylo také dokázáno, že neexistuje vysvětlení pro vznik systémů povodí a skladbu vodních toků v nich.

Hydrologie se zabývá stálými a občasnými vodními toky. Občasné vodní toky (také označované jako periodické) jsou takové, v jejichž přirozeném vodním režimu se vyskytuje období, ve kterém korytem neprotéká voda a tok není napájen podzemní vodou. +more Řád vodního toku může dosahovat hodnot od 1 (pro toky, které nemají přítoky) do 12 (ústí nejdelší a nejvodnatější řeky světa Amazonky). Největší řeky v České republice jsou sedmého až devátého řádu. Až 80 % všech světových řek spadá do skupin řek prvního až třetího řádu.

Stupeň rozvětvení říční sítě udává bifurkační poměr povodí. Pokud je jeho hodnota nízká, znamená to, že je voda koncentrována v jednom či několika málo korytech. +more V takovýchto povodích nastávají povodně s vyšší pravděpodobností než v povodích s vyšším bifurkačním poměrem, ve kterých je voda rovnoměrně rozložena do více koryt. Bifurkační poměr může také ukázat náchylnost k povodním v rámci jednoho povodí.

Jiné klasifikační systémy

Strahlerova klasifikace může být využita ve statistické analýze jakéhokoliv hierarchického systému: * Arenas a kol. (2004) popisují aplikaci Horton-Strahlerova čísla při analýze sociálních sítí; * Ehrenfeucht, Rozenberg & Vermeir (1981) použili variantu Strahlerova číslování, kterou nazvali stromová řada (listům je místo hodnoty jedna přiřazena nula), pro analýzu L-systémů; * Strahlerovo číslování je také používáno v biologii, například pro označení větvení stromů či dýchací a oběhové soustavy zvířat.

Alokace registrů

Minimální počet registrů procesoru nutných k vyhodnocení binárního stromu při překladu vyššího programovacího jazyka do jazyka symbolických adres, je roven Strahlerovu číslu daného stromu. V tomto kontextu je Strahlerovo číslo nazýváno také číslo registru.

V některých případech binární strom vyžaduje více registrů, než je k dispozici. K jeho překladu do sledu příkazů pak může být použit Sethi-Ullmanův algoritmus, který maximálně využívá registry a minimalizuje využívání hlavní paměti a celkový počet příkazů ve finálním kódu.

Související parametry

Bifurkační poměr

S použitím Strahlerova čísla pro označení větví ve stromovém diagramu souvisí bifurkační poměr, který udává vyváženost diagramu. Pro každý řád i v hierarchii diagramu lze i-tý bifurkační poměr určit dle vzorce: : \frac{n_{i}}{n_{i+1}}, kde ni označuje počet uzlů i-tého řádu.

V hydrologii poměr udává počet toků určitého řádu (n_i) ku počtu toků o řád vyšší (n_{i+1}).

Bifurkační poměr celého diagramu lze určit jako průměr bifurkačních poměrů jednotlivých řádů. Bifurkační poměr úplného binárního stromu je roven dvěma, u ostatních stromů je poměr menší. +more Bifurkační poměr je veličina bez jednotky.

Šířka cesty

Šířku cesty libovolného neorientovaného grafu G můžeme definovat jako nejmenší existující číslo w, pro které platí: neorientovaný podgraf G je podgrafem intervalového grafu H, jehož maximální klika má w+1 vrcholů.

Stromový diagram můžeme považovat za neorientovaný graf, pokud nebereme v potaz jeho kořeny a orientaci. Šířka cesty stromových diagramů se liší od jejich Strahlerova čísla, úzce s ním však souvisí. +more Pro šířku cesty w a Strahlerovo číslo s stromového diagramu platí nerovnost: : w ≤ s ≤ 2w + 2.

Na rozdíl od Strahlerova čísla se šířka cesty vztahuje i na cyklické grafy. Nelze ji však definovat pro jednotlivé uzly grafu, ale pouze pro graf jako celek.

Související články

binární strom * říční systém * strom (graf)

Reference

Literatura

. * . * . * * . * . * . * .. * . * LANGHAMMER, J. Vymezení typů vdních toků. Přírodovědecká fakulta Karlovy univerzity, Praha, 2009. * * . * . * .

Kategorie:Fyzická geografie Kategorie:Geomorfologie Kategorie:Hydrologie