Nombre de Strahler

Nombre de Strahler
Flussordnung (Strahler).svg
Classification des réseaux hydrographiques d'après Strahler.
Présentation
Type

Le nombre de Strahler d'une arborescence[1] est une mesure numérique de sa complexité de branchements.

Cette propriété est utilisée, par exemple, en classification des réseaux hydrographiques des cours d'eau pour indiquer le niveau de complexité de son réseau d'affluents et de sous-affluents et en théorie de la compilation pour calculer le nombre de registres nécessaires au calcul d'une expression arithmétique[2].

Les premières utilisations de ce nombre se trouvent dans les travaux de Robert E. Horton (en) en 1945[3] ainsi que dans ceux d'Arthur Newell Strahler en 1952[4] et en 1957[5].

Définition

Selon la théorie des graphes, on peut attribuer un nombre de Strahler à tous les nœuds d'un arbre, depuis les extrémités vers la racine, comme suit :

  1. Si le nœud n'est que l'extrémité d'une arête / d'un arc, sans autre connexion, (= une feuille dans la théorie des graphes, ou = sans enfant), son nombre de Strahler est 1 ;
  2. Si le nœud a un arc ramifié avec le nombre de Strahler i, et que tous les autres arcs ramifiés ont des nombres de Strahler inférieurs à i, alors le nombre de Strahler de ce nœud est i à nouveau ;
  3. Si le nœud a au moins deux arcs ramifiés avec le nombre de Strahler i, et aucun arc ramifié ayant un plus grand nombre, le nombre de Strahler de ce nœud est alors i + 1.

Le nombre de Strahler de l'arborescence est le nombre entier de son nœud racine. Il est donc adimensionnel.

Tout nœud ayant le nombre de Strahler i doit donc avoir au moins :

  • deux arcs ramifiés descendants avec un nombre de Strahler i - 1 ;
  • quatre descendants avec un nombre de Strahler i - 2, etc. ;
  • 2i - 1 « feuilles » descendantes.

Par conséquent, dans un arbre avec n nœuds, le plus grand nombre de Strahler possible est la partie entière de log2(n). Cependant, à moins que l'arbre forme un arbre binaire complet, le nombre de Strahler sera inférieur à cette borne. Dans un arbre binaire à n nœuds, choisi uniformément au hasard parmi tous les arbres binaires possibles, l'indice prévu de la racine est, avec une forte probabilité, très proche de log4(n).

Exemples

En hydrographie

Le nombre de Strahler est de 1 pour tout cours d'eau entre sa source et sa première confluence[6].

La racine du cours d'eau est soit la confluence où ce cours d'eau perd son nom, soit pour un fleuve, son embouchure. L'ordre d'un bassin versant est celui de son cours d'eau principal[6]. La classification peut dépendre de l'échelle de la carte utilisée[7],[8].

La classification des cours d'eau par le nombre de Strahler est ainsi très significative pour prendre en compte la structure et la densité du réseau hydrographique[9]. Elle reflète la variabilité des situations géographiques (exemple : selon la perméabilité du substrat rocheux du bassin versant) et pluviométriques par son lien étroit avec la quantité d’eau transportée en surface pendant les périodes de forts débits[9].

Le nombre de Strahler atteint :

Valeur à l'embouchure du cours d'eau
NomNombre
FleuveStrahler[10]Shreve
Amazone12Au moins 29
Mississippi10Au moins 23
Nil10Au moins 22
Rhône9Au moins 20
Garonne9Au moins 16
Ienissei8Au moins 18
Danube8Au moins 15
Loire8Au moins 16
Congo7Au moins 18
Indus7Au moins 19
Mékong7Au moins 19
Rhin7Au moins 18
Seine7Au moins 16
Adour7Au moins 14
Dordogne7Au moins 14
Meuse7Au moins 14
Aar6Au moins 17
Oise6Au moins 16
Tamise5Au moins 11
Tibre5Au moins 9
Marne5Au moins 14
Lot5Au moins 13

En informatique

Lors de la compilation d'un programme d'un langage de haut niveau en assembleur, le nombre minimum de registres nécessaires pour évaluer l'arbre d'une expression est exactement le nombre de Strahler de cet arbre[11],[12].

Lien externe

Voir aussi

  • la classification des réseaux hydrographiques
  • le Lexique de la théorie des graphes
  • l'ordre des cours d'eau

Notes et références

Notes

Références

  1. Régis Caloz et Claude Collet, Analyse spatiale de l'information géographique, Lausanne, Presses polytechniques et universitaires romandes, coll. « Science et ingénierie de l'environnement », , 384 p. (ISBN 978-2-88074-902-6, lire en ligne), p. 199.
  2. (en) Xavier Gérard Viennot, « A Strahler bijection between Dyck paths and planar trees », Discrete Mathematics, vol. 246, nos 1-3,‎ , p. 317-329.
  3. (en) R. E. Horton, « Erosional development of streams and their drainage basins: hydro-physical approach to quantitative morphology », Geological Society of America Bulletin, vol. 56, no 3,‎ , p. 275-370.
  4. (en) Arthur Newell Strahler, « Hypsometric (area-altitude) analysis of erosional topology », Geological Society of America Bulletin, vol. 63, no 11,‎ , p. 1117-1142.
  5. (en) Arthur Newell Strahler, « Quantitative analysis of watershed geomorphology », Transactions of the American Geophysical Union, vol. 8, no 6,‎ , p. 913-920.
  6. André Musy et Christophe Higy, Hydrologie : Une science de la nature, Lausanne, Presses polytechniques et universitaires romandes, coll. « Gérer l'environnement », , 314 p. (ISBN 2-88074-546-2, lire en ligne), p. 88 et 89.
  7. Denis Mercier, Géomorphologie de la France, Paris, Dunod, , 272 p. (ISBN 978-2-10-059706-2 et 2-10-059706-X, lire en ligne), p. 248.
  8. « Réseau hydrographique : ordre des cours d’eau pour le réseau hydrographique numérique au 1:25 000 de la Suisse », sur www.bafu.admin.ch.
  9. Typologie des cours d’eau de France métropolitaine[PDF], p. 12, Cemagref.
  10. (en) Colbert E. Cushing, Kenneth W. Cummins et G. Wayne Minshall, River and Stream, Londres, University of California press, coll. « Ecosystems of the world », , 825 p. (ISBN 0-520-24567-9, lire en ligne), p. 390
  11. Andreï Ershov, « On programming of arithmetic operations », Communications of the ACM, vol. 1, no 8,‎ , p. 36 (DOI 10.1145/368892.368907).
  12. Philippe Flajolet, Jean-Claude Raoult et Jean Vuillemin, « The number of registers required for evaluating arithmetic expressions », Theoretical Computer Science, vol. 9, no 1,‎ , p. 99-125 (DOI 10.1016/0304-3975(79)90009-4).
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Strahler number » (voir la liste des auteurs).

Médias utilisés sur cette page

Max-cut.svg
Auteur/Créateur: Miym, Licence: CC BY-SA 3.0
Maximum cut
Flussordnung (Strahler).svg
Auteur/Créateur: Kilom691, Licence: CC BY-SA 3.0
nombres de Strahler (utile pour décrire fleuves et arbres)
Circle-icons-water.svg
Auteur/Créateur: Elegant Themes, Licence: GPL
Water drop icon / symbol: One white drop in a (light) blue, round disc. We’ve designed a 192 piece set of flat icons, and they are all yours, for free! The icons come in two versions: full color and single color, for a total of 384 variations. This download includes .ai, .eps, .pdf, and .png (64px and 128px). Below is the full set in both styles. These icons are completely free and Open Source under the GPL, so feel free to use them in your personal and commercial projects alike. We are on a mission to create the best collection of Open Source graphics on the web, so that the WordPress ecosystem can use and enjoy them alongside the freedoms they have become accustomed to. Stay tuned for more great stuff!