« Nombre de Strahler » : différence entre les versions
m Retrait du point après {{Traduction/Référence}}, désormais intégré au modèle |
m →Définition : lien sur Borne |
||
| Ligne 20 : | Ligne 20 : | ||
* 2{{exp|''i'' - 1}} "feuilles" descendantes. |
* 2{{exp|''i'' - 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 [[Logarithme binaire|log{{ind|2}}(''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 [[Logarithme|log{{ind|4}}(''n'')]]. |
Par conséquent, dans un arbre avec ''n'' nœuds, le plus grand nombre de Strahler possible est la [[partie entière]] de [[Logarithme binaire|log{{ind|2}}(''n'')]]. Cependant, à moins que l'arbre forme un [[arbre binaire]] complet, le nombre de Strahler sera inférieur à cette [[Borne supérieure et borne inférieure|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 [[Logarithme|log{{ind|4}}(''n'')]]. |
||
== Exemples == |
== Exemples == |
||
Version du 28 mai 2015 à 10:11
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
.svg)
Le nombre de Strahler d'une arborescence[1] est une mesure de sa complexité de branchement.
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 de 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 :
- 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 ;
- 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 ;
- Si le nœud a deux arcs ramifiés ou plus avec le nombre de Strahler i, et pas d'autre 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 :
- dans le monde, 12 pour l'Amazone[10] et 10 pour le Nil[10] et le Mississippi[10].
- en France, 8[11] pour la Loire[12], la Seine, 7[11] pour l'Oise et la Meuse et 6[11] pour le Lot et la Marne, mais selon d'autres auteurs[13], 10 pour la Loire, le Rhône et la Garonne[notes 1] et 7 en Corse.
- en Suisse, 9 pour l'Aar et le Haut Rhin[8].
Voir aussi
Notes et références
Notes
Références
- 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), p. 199.
- (en) Xavier Gérard Viennot, « A Strahler bijection between Dyck paths and planar trees », Discrete Mathematics, vol. 246, nos 1-3, , p. 317-329.
- (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.
- (en) Arthur Newell Strahler, « Hypsometric (area-altitude) analysis of erosional topology », Geological Society of America Bulletin, vol. 63, no 11, , p. 1117-1142.
- (en) Arthur Newell Strahler, « Quantitative analysis of watershed geomorphology », Transactions of the American Geophysical Union, vol. 8, no 6, , p. 913-920.
- 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 2880745462), p. 88 et 89.
- Denis Mercier, Géomorphologie de la France, Paris, Dunod, , 272 p. (ISBN 210059706X), p. 248.
- « 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.
- Typologie des cours d’eau de France métropolitaine, p. 12, Cemagref [PDF].
- François Anctil, L'eau et ses enjeux, Bruxelles, Presses de l'Université Laval - De Boeck, , 229 p. (ISBN 280415694X), p. 51.
- (en) Colbert E. Cushing, Kenneth W. Cummins et G. Wayne Minshall, River and Stream Ecosystems of the World, Berkeley, London, University of California press, , 825 p. (ISBN 0-520-24567-9), p. 398, 402.
- Eric Feunteun, Patrick Prouzet et Christian Rigau, L'anguille européenne : indicateurs d'abondance et de colonisation, Versailles, Quae, coll. « Savoir faire », , 393 p. (ISBN 275920085X), p. 105.
- D'après le MNT au pas de 250 m. Source : IGN. - Institut Géographique National (France), « Bassins versants - Niveaux Strahler des BV »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?) (consulté le ).
