Aller au contenu

Nombre de Strahler

😀 On considère ici des arbres non étiquetés.

Définition du nombre de Strahler d'un arbre

Le nombre de Strahler d'un arbre indique sa complexité de branchement ; il est défini pour chacun des nœuds.

Le nombre de Strahler d'un arbre est celui de sa racine.

  • Le nombre de Strahler d'une feuille est 1.
  • Pour tout autre nœud, on note i le maximum des nombres de Strahler de ses enfants (il y en a).
    • S'il y a un seul enfant dont le nombre de Strahler est i, alors le nombre de Strahler du nœud reste égal à i,
    • sinon, le nombre de Strahler du nœud est égal à i + 1.
Culture scientifique

Le paramètre « nombre de Strahler » fut introduit pour la première fois par Horton et Strahler en Hydrogéologie, pour l'étude de la forme des bassins fluviaux. Depuis il est réapparu dans l'étude des formes des structures arborescentes naturelles : arbres en botanique, éclairs en physique, molécules biologiques d'ARN, etc.

Exemple d'arbre ayant un nombre de Strahler égal à 2

graph TB
    R{ } --> N1{ }
    R    --> N3{ }
    N3   --> N4{ }
    N3   --> N5{ }
    N3   --> N6{ }
    N4   --> N7{ }
graph TB
    R(2) --> N1(1)
    R    --> N3(2)
    N3   --> N4(1)
    N3   --> N5(1)
    N3   --> N6(1)
    N4   --> N7(1)

Exercice

Coder une fonction nb_strahler qui prend un arbre non étiqueté en paramètre et qui renvoie un entier : le nombre de Strahler de sa racine.

Indice

Cet exercice s'apparente à une recherche de maximum, pour lequel on vérifie s'il est unique ou non. Ceci, de manière récursive.

Guide
🐍 Script Python
def nb_strahler(arbre):
    "Renvoie le nombre de Strahler de l'arbre"
    enfants = arbre
    if ...:
        return 1
    else:
        n_max = ...
        for sous_arbre in enfants:
            n = ...
            if n == n_max:
                seul = False  # le maximum n'est pas unique
            elif n > n_max:
                n_max = ...
                seul = True
            else:
                ...

        if ...:
            n_max += 1
        return n_max
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.9888.128013x/.Tr;nbOylaeu)d63m(P+02@,59fq!7K8 _o=pcwgv4F1kRIéhtsSàCji:050r0o0#0n0+0m0$0K0P0m0n0$0$0N010#0+0O010406050$0p0u0u0n0g0l040%0M0m0p100M0i0K020n0u0O0h0K0X0o1a0g0F0p0o0$050d17191b1d150O04051I1B1L0d1I150r0+0S0^0`0|0~0!0+0R0!0m1Z0!0#13050:0j0m0o1U0{0}011Y1!1$1!0#1,1.1*0#0g1J0#0!1:1W010E0=0o0i1o0o010^1g0$0O0n0i0~0z1*2g2i241=271.2a0u2c040b0K0w0g0M0O0M0$0+1j1l0.2e0g0g0o0P2G1B2n0i1J0d222S1 21201+0r2p0~1$0i292D1*1R1T0_1;2$0+2(0i0M2,1*0O2L1J2Q2S2}162h1l2.252?0g1a0m130K0V2P3114302o331=3537390z3c2i3e2Q2#013j0n38040K0t3n2R153q3h0~3t3v0K0T3z3p313r3F390C3J3B3L3D3s0M363u390s3Q3f321V3i3V3k3w0H3!3C3%3E3)3X3w0J3-3S3/3U3W3G0D3^3g3`3N040V0y3 3$2/3{3*0V3b1C3d3R4048420V3m4d3o4f47343;3v0V3y4l3A3#3M4q130V3I4u3K4g4p3|4z3P4C4n4x4G433Z4J4w3T4i3,4P3.4h4y433@4U3_4W4M0V3~4!4E3(4M0z454C1M2{1B2,2V0r212!3T0P2@2v0-1S1J2`0o2|3d3J054}0.554+0~0W130.0E574V250Q395i4#340E130i0j0L0$1 0n1#0o0g5n5c0112040v5B4o3i131b0j2L5H3r5E0q0,3Q0K5U0K4Q3`0$2l04011t0i0S0M0+1/1.0K2?0u5M1/2I0%5w5y0g0K2I0m005L2L015T5V5X4h13290E2i0#1A4C5W5j1=0M130N3J6d5o5J045 0o625U64255e040+5h6c6s3i0j132s5O3T5E5G4:6e3E660i680i6a6E3`5Q6j6z0~6g040N6i6y6J010u0+134/2 6#5E5S4J5V6:6k5C6u2L0#0p0g0i6T6#6%4z3Q066:6U3s5r0L1a0c6}6l6V6h7a5C6 046*4e736#6u0E3V7e5I6K040$0M0p0$0L6o7p3r0M5l6v6|6!7b750467696b6+7G6-6q6;740i5r7z3T6W6Z2}6=7q7H5s5u5^1.5A6I7N136H7M5C7S7s7u7w7y7+5C6S6/6;6r7l136w7U417T7F5C7W7X3d7Z3M76786Q487O7|7}7k7G7;0$0o0p0m82487W8q6t0P130U3u8m7P8j6?661$6x7Y7R848G6#6W020R0#0h8t6m0i770n797_7!8g2}728i8B7!7;8S8d857!8s8+8b047E8Z8#8$8/8m8o8Q7c6X8{010W8v040f0g1y8A637 7I0?6p8W5P136.8=8?7~7G6u2h0|718@3T6u818.7V7C2?0#8~8l8n8p9c6F9e969i7:8c8U8~6W0x883o8a3T7g4c9g9F7!6@0/6`8;898H8:8T8V8Z1B59544;9+0d4@1B0#4_9:2Y2T0n1-9-4@1H5b7!2L0u0L680W0o0L0!0t131t1v1x1z0K9f561O3e0.0:0=0@3T0r2i0R5z133B181v1d0)4~0K682N3V0+0$0Z2Pau1F3e1I0k1l0O8n0#0K2;0#0Z0R2L5`1.0@0.0p0c0^0{0K290K0p1l8_0ma(1l0*7u692J2L2N1u29aP0n0S2M0K0`0K0S1b0+9_5-584~7s9z9)b91MaJ1J0+0u0R0K3u0#0~0a2d3T0#0Q1u0M0*6(0K0$0g0P1X1{0O0$0,0d0d0P0r0i0e0*0$0.1$0S0g0e2(0#0d1!0d0*0.0Pa40r2Tbs0ubu0+0A0V0C0e0V0e0y0d1;0/0$1C0S0R0d0z0s0n0y0e0$b{2d100#1.0~0,0Q1b0i2;0R0,010d3wax2I2?1la^0M1E0i0r0Z0K0(0K0Z0P0g0+2L0K1ra+0+ac2u6O0K2C6`bk2a0m0l8m0K0Gbe1Q1S3r1@1#1%1)9~3r2r292b132x0%cy11aP0w0l221k57539~2~569*c#9p5f0o8F566#7C5W9B415q8:5t5v0g5x7)8e256Gdf6m7^7/8X135R7P745Z135$295)5+b01/5/5;5{1/5@dc5_dBb05~0g5;618h9O837I6M7K9J7d9sdOdk4e8!9T8^bbdU8rdT8J9j918x9adp6#8(9$dS8}d$257g7i4m9o3`7m7od@6m7t7v7xdJ5Ne06V7C2;9x6L6N6Pd68f9DdMd|658:d=9M2RdNek7$dbdd5zdi0~dhef3413e27@e59bdl9d040q9Eep6t80d19N9!9YeO8K6hen3wePd;ey1=8Y7j9heKe1d#d)86d(9Z7ld+8yeEe#7}746u0o8Eebele7018L8N8Pe}d:8*eF9C04afd{e$eWf4e-7G8-e*8%8Ie=8?9!a-em8~90139395ei979j8D8zeYeweh9Sfk989l7LdXejeL6veNeo747B5r0M9wf2eAe)d27,f7eJfb9Ie}9KeUe%0~9Qd.fv046^9Xe{8)fZ9(bHbd1O4=9.51158o3e1$040w7u5`a+1/0E8n0=5-0,5Wc|a-0B5.9$0K0N0K0vd,8mge0yeIf?5acCcJa%2I0j7u0_0oge1k0K2L5(5*1/0y0xb:0K0k0I1Bf 150df}9}05bhbjblbnbp3`brbtbv2dbybA1?bCbEbGbIbKbMbO1SbRbTbV0!bXbZb#b%g#b+b-b/b;b?0|b^b`b|b~c0c2c40Kc6c801cacccecgci0K0Ya.0i001zaP9lgC2Mcp1acrct2I161 1k0R042`2@0pcAeEhB0ihD0^1/aq0icB2I9*gjcv2h0g0:aq0g0qgeb14}1p0g0Z0!292EgB0r0pa$aY1/0j0{1/hq5.0/0#a`cIh*h:2F0o0e0K0)hp5va*cdcGa{iaa(0c5z0P0+0P1/aRe_1.2N1y0m0ecT4?0/0;0?3e9.ival04.