Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Nombre de Strahler
Résumé
Le nombre de Strahler d'une arborescence 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.
Les premières utilisations de ce nombre se trouvent dans les travaux de en 1945 ainsi que dans ceux d'Arthur Newell Strahler en 1952 et en 1957.
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 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 ;
2 « 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 log(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 log(n).
Le nombre de Strahler est de 1 pour tout cours d'eau entre sa source et sa première confluence.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.