Numero di Strahler
Il numero di Strahler (o anche il grado di Strahler) di un'arborescenza[1] è una misura numerica della sua complessità di ramificazione.
Questa proprietà è utilizzata, per esempio, nella classificazione delle reti idrografiche dei corsi d'acqua per indicare il livello di complessità delle loro reti di affluenti e dei loro subaffluenti e in informatica, nella teoria della compilazione, per calcolare il numero di registri necessari al calcolo di un'espressione aritmetica[2].
Le prime utilizzazioni di questo numero si trovano nelle opere di Robert E. Horton del 1945[3], così come in quelli di Arthur Newell Strahler del 1952[4] e del 1957[5].
Definizione
Secondo la teoria dei grafi, si può attribuire un numero di Strahler a tutti i nodi di un albero, dalle estremità verso la radice, come segue:
- se il nodo non è che l'estremità di uno spigolo/di un arco, senza altre connessioni (una foglia nella teoria dei grafi, o senza figli), il suo numero di Strahler è 1;
- se il nodo ha un arco ramificato con numero di Strahler i e tutti gli altri archi ramificati con numero di Strahler inferiore a i, allora il numero di Strahler di questo nodo è ancora i;
- se il nodo ha almeno due archi ramificati con numero di Strahler i e nessun arco ramificato con un numero più grande, allora il numero di Strahler di questo nodo è i + 1.
Il numero di Strahler di un'arborescenza è un numero puro ed è il numero di Strahler del suo nodo radice.
Tutti i nodi aventi il numero di Strahler i devono dunque avere almeno:
- due archi ramificati discendenti con un numero di Strahler i - 1;
- quattro discendenti con un numero di Strahler i - 2 (etc.);
- 2(i - 1) «foglie» discendenti.
Di conseguenza, in un albero con n nodi, il più grande numero di Strahler possibile è la parte intera di log2 (n). Tuttavia, a meno che l'albero non formi un albero binario completo, il numero di Strahler sarà inferiore a questo massimo. In un albero binario a n nodi, scelto uniformemente a caso tra tutti gli alberi binari possibili, l'indice previsto della radice è, con elevata probabilità, molto vicino al log4 (n).
Esempi
In idrografia
Il numero di Strahler è 1 per tutti i corsi d'acqua tra la loro sorgente e la loro prima confluenza[6]. La radice dei corsi d'acqua è sia la confluenza ove questi corsi d'acqua perdono il loro nome, sia la loro foce. L'ordine di un bacino versante è quello del suo corso d'acqua principale[6]. La classificazione può dipendere dalla scala della carta utilizzata[7][8].
La classificazione dei corsi d'acqua con il numero di Strahler è molto significativa per stabilire la struttura e la densità della rete idrografica[9]. Essa riflette la variabilità delle situazioni geografiche (esempio: secondo la permeabilità del substrato roccioso del bacino versante) e pluviometriche per il suo stretto legame con la quantità d'acqua trasportata in superficie durante i periodi di grande portata[9].
Il numero di Strahler riguarda:
| Nome | Numero | |
|---|---|---|
| Fiume | Strahler[10] | Steven E. Shreve |
| Rio delle Amazzoni | 12 | Almeno 29 |
| Nilo | 10 | Almeno 22 |
| Mississippi | 10 | Almeno 23 |
| Ienissei | 8 | Almeno 18 |
| Congo | 7 | Almeno 18 |
| Mekong | 7 | Almeno 19 |
| Indo | 7 | Almeno 19 |
| Tamigi | 5 | Almeno 11 |
| Danubio | 6 | Almeno 15 |
| Tevere | 5 | Almeno 9 |
| Reno | 7 | Almeno 18 |
| Aar | 6 | Almeno 17 |
| Oise | 6 | Almeno 16 |
| Marna | 5 | Almeno 14 |
| Lot | 5 | Almeno 13 |
| Loira | 8 | Almeno 16 |
| Senna | 7 | Almeno 16 |
| Garonna | 9 | Almeno 16 |
| Dordogna | 7 | Almeno 14 |
| Adour | 7 | Almeno 14 |
| Mosa | 7 | Almeno 14 |
| Rodano | 9 | Almeno 20 |
In informatica
Nella compilazione di un programma d'un linguaggio di elevato livello in assemblatore, il numero minimo di registri necessari per valutare l'albero d'una espressione, è esattamente il numero di Strahler di quest'albero.[11][12]
Note
- ↑ (FR) Régis Caloz e Claude Collet, Analyse spatiale de l'information géographique, Science et ingénierie de l'environnement, Lausanne, Presses polytechniques et universitaires romandes, 2011, p. 199, ISBN 978-2-88074-902-6.
- ↑ (EN) Xavier Gérard Viennot, A Strahler bijection between Dyck paths and planar trees, in Discrete Mathematics, vol. 246, n. 1-3, 6 marzo 2002, pp. 317-329.
- ↑ (EN) R. E. Horton, Erosional development of streams and their drainage basins: hydro-physical approach to quantitative morphology, in Geological Society of America Bulletin, vol. 56, n. 3, 1945, pp. 275-370.
- ↑ (EN) Arthur Newell Strahler, Hypsometric (area-altitude) analysis of erosional topology, in Geological Society of America Bulletin, vol. 63, n. 11, 1952, pp. 1117-1142..
- ↑ (EN) Arthur Newell Strahler, Quantitative analysis of watershed geomorphology, in Transactions of the American Geophysical Union, vol. 8, n. 6, 1957, pp. 913-920.
- 1 2 (FR) André Musy e Christophe Higy, Une science de la nature, in Hydrologie, Gérer l'environnement, Losanna, Presses polytechniques et universitaires romandes, 2004, p. 314 e pp. 88-89, ISBN 2-88074-546-2.
- ↑ (FR) Denis Mercier, Géomorphologie de la France, Parigi, Dunod, 2013, p. 248, ISBN 978-2-10-059706-2.
- ↑ Réseau hydrographique : ordre des cors d'eau pour il réseau hydrographique numérique au 1:25 000 de la Suisse, su bafu.admin.ch.
- 1 2 Typologie des corses d’eau de France métropolitaine (PDF), p. 12, Cemagref.
- ↑ (EN) Colbert E. Cushing, Kenneth W. Cummins e G. Wayne Minshall, River and Stream, Ecosystems of the world, Londra, University of California press, 2006, p. 390, ISBN 0-520-24567-9.
- ↑ (EN) Andreï Ershov, On programming of arithmetic operations, in Communications of the ACM, vol. 1, n. 8, 1958, p. 36, DOI:10.1145/368892.368907.
- ↑ (EN) Philippe Flajolet, Jean-Claude Raoult e Jean Vuillemin, The number of registers required for evaluating arithmetic expressions, in Theoretical Computer Science, vol. 9, n. 1, 1979, pp. 99-125, DOI:10.1016/0304-3975(79)90009-4.
Collegamenti esterni
- Javier Esparza, Michael Luttenberger et Maximilian Schlund, A Brief History of Strahler Numbers (PDF), su Università tecnica di Monaco, 2014. URL consultato il 14 giugno 2021 (archiviato dall'url originale il 21 marzo 2020).