Strahlerovo číslo

Strahlerovo číslo Klasifikace hydrografických sítí podle Strahlera. Prezentace
Typ Teorém

Počet Strahler of do stromu je numerická míra jeho větvení složitosti.

Tato vlastnost se používá například klasifikace říčních systémů z toků pro indikaci úrovně složitosti její sítě přítoků a dílčích přítoků a teorie překladu vypočítat počet registrů potřebných pro výpočet aritmetického výrazu.

První použití tohoto čísla jsou v pracích Roberta E. Hortona  (v) v roce 1945, stejně jako v dílech Arthura Newella Strahlera v letech 1952 a 1957.

Definice

Podle teorie grafů můžeme přiřadit číslo Strahler ke všem uzlům jednoho stromu , od konců do kořene , a to následovně:

  1. pokud je uzel pouze koncem hrany / oblouku, bez jakéhokoli jiného spojení (= list v teorii grafů nebo = bez dětí), jeho Strahlerovo číslo je 1;
  2. pokud má uzel rozvětvený oblouk s Strahlerovým číslem i a všechny ostatní rozvětvené oblouky mají Strahlerovy čísla menší než i , pak Strahlerovo číslo tohoto uzlu je opět i ;
  3. pokud má uzel alespoň dva rozvětvené oblouky se Strahlerovým číslem i a žádné rozvětvené oblouky s větším počtem, pak Strahlerovo číslo tohoto uzlu je i + 1.

Strahlerovo číslo stromu je celé číslo jeho kořenového uzlu. Je tedy bezrozměrný .

Každý uzel, který má Strahlerovo číslo i, proto musí mít alespoň:

Proto v stromu s n uzly, co největší počet Strahler je celá část z log 2 ( N ) . Pokud však strom nevytvoří úplný binární strom , Strahlerovo číslo bude menší než toto vázané . V binárním stromu n- uzlu, který je náhodně vybrán ze všech možných binárních stromů, je predikovaný index kořene s vysokou pravděpodobností velmi blízký log 4 ( n ) .

Příklady

V hydrografii

Strahlerovo číslo je 1 pro jakýkoli proud mezi jeho zdrojem a jeho prvním soutokem .

Kořen proudu je buď soutok kde tento proud ztrácí své jméno, nebo na řeku , její ústa . Pořadí povodí je pořadí jeho hlavního vodního toku. Klasifikace může záviset na měřítku použité mapy.

Klasifikace vodních toků podle Strahlerova čísla je tedy velmi významná pro zohlednění struktury a hustoty hydrografické sítě. Odráží variabilitu geografických situací (příklad: podle propustnosti podloží povodí) a srážky prostřednictvím jejího úzkého vztahu s množstvím vody transportované na povrch během období vysokého průtoku.

Strahlerovo číslo dosahuje:

Hodnota v ústí vodních toků
Příjmení Číslo
Řeka Strahler Shreve
Amazonka 12 Nejméně 29
Nil 10 Nejméně 22
Mississippi 10 Nejméně 23
Jenisej 8 Nejméně 18
Kongo 7 Nejméně 18
Mekong 7 Nejméně 19
Indus 7 Nejméně 19
Temže 5 Nejméně 11
Dunaj 6 Nejméně 15
Tiber 5 Nejméně 9
Rýn 7 Nejméně 18
Aar 6 Nejméně 17
Oise 6 Nejméně 16
Slín 5 Nejméně 14
Lot 5 Nejméně 13
Loire 8 Nejméně 16
Seina 7 Nejméně 16
Garonne 9 Nejméně 16
Dordogne 7 Nejméně 14
Adour 7 Nejméně 14
Meuse 7 Nejméně 14
Rhône 9 Nejméně 20

V počítačové vědě

Při sestavování programu na vysoké úrovni jazyk do assembleru , minimální počet registrů musí vyhodnotit výraz strom je přesně počet Strahler tohoto stromu.

Externí odkaz

Podívejte se také

Poznámky a odkazy

Poznámky

Reference

  1. Régis Caloz a Claude Collet , Prostorová analýza geografických informací , Lausanne, Presses polytechniques et universitaire romandes, kol.  "Věda o životním prostředí a technika",2011, 384  s. ( ISBN  978-2-88074-902-6 , číst online ) , s.  199.
  2. (in) Xavier Gérard Viennot , „  Strahlerova bijekce mezi Dyckovými cestami a rovinnými stromy  “ , Discrete Mathematics , sv.  246, n kost  1-3,6. března 2002, str.  317-329.
  3. (in) RE Horton , „  erozní vývoj toků a jejich povodí: hydrofyzikální přístup ke kvantitativní morfologii  “ , Geological Society of America Bulletin , sv.  56, n o  3,1945, str.  275-370.
  4. (in) Arthur Newell Strahler , „  hypsometrická (oblast-nadmořská výška) analýza erozní topologie  “ , Geological Society of America Bulletin , sv.  63, n o  11,1952, str.  1117-1142.
  5. (in) Arthur Newell Strahler , „  Kvantitativní analýza geomorfologie povodí  “ , Transaction of the American Geophysical Union , sv.  8, n O  6,1957, str.  913-920.
  6. .
  7. Denis Mercier , Geomorfologie Francie , Paříž, Dunod ,2013, 272  s. ( ISBN  978-2-10-059706-2 a 2-10-059706-X , číst online ) , s.  248.
  8. „  Hydrografická síť: řád vodních toků pro digitální hydrografickou síť Švýcarska 1:25 000  “ , na www.bafu.admin.ch .
  9. Typologie řek v kontinentální Francii [PDF] , s.  12 , Cemagref .
  10. (in) Colbert E. Cushing , Kenneth W. Cummins a Wayne G. Minshall , River and Stream , London, University of California Press, kol.  "Ekosystémy světa",2006, 825  s. ( ISBN  0-520-24567-9 , číst online ) , s.  390
  11. Andrei Ershov , „  O programování aritmetických operací  “, Komunikace ACM , sv.  1, n o  8, 1958, str.  36 ( DOI  10.1145 / 368892.368907 ).
  12. Philippe Flajolet , Jean-Claude Raoult a Jean Vuillemin, „  Počet registrů potřebných pro vyhodnocení aritmetických výrazů  “, Theoretical Computer Science , sv.  9, n o  1, 1979, str.  99-125 ( DOI  10.1016 / 0304-3975 (79) 90009-4 ).
(fr) Tento článek je částečně nebo zcela převzat z článku anglické Wikipedie s názvem „  Strahlerovo číslo  “ ( viz seznam autorů ) .