Quanto può essere irregolare un albero? Scopri i limiti dell’indice di Albertson

In matematica, un "albero" è un grafo senza cicli, simile a un albero genealogico ma con rami che collegano i vertici. L’indice di Albertson, indicato con irr(G), misura quanto le connessioni di un grafo siano disomogenee: più le differenze tra i gradi dei vertici sono grandi, più l’indice sale. Recenti ricerche hanno scoperto dei limiti molto precisi per questo indice quando il grafo è un albero e la sequenza dei gradi è nota.

La sequenza dei gradi, scritta in ordine crescente (d₁ ≤ d₂ ≤ … ≤ dₙ), racconta quanti rami partono da ogni nodo. Gli autori hanno dimostrato che per gli alberi‑caterpillar, una forma di albero con un “corpo” centrale e foglie attaccate, l’indice di Albertson si calcola con una formula che combina termini quadrati, prodotti e differenze assolute tra gradi consecutivi.

Ma la novità più importante è la scoperta di due disuguaglianze che racchiudono tutti gli alberi con la stessa sequenza di gradi: una fornisce il valore minimo possibile di irr(G) e l’altra il valore massimo. Queste formule includono il numero totale di spigoli, la media dei gradi e combinazioni specifiche dei valori dᵢ.

Il risultato è più di un semplice calcolo: mostra come la struttura di un albero – la disposizione dei rami – influisce direttamente sulla sua irregolarità. Questo aiuta i ricercatori a capire meglio le proprietà topologiche dei grafi e a confrontare diversi indici basati sui gradi, aprendo la strada a nuove applicazioni in chimica, informatica e teoria delle reti.

L’indice di Albertson, introdotto da Michael Albertson nel 1997, è definito come irr(G)=∑_{uv∈E}|d(u)-d(v)|, dove la somma è presa su tutti gli spigoli del grafo G e d(v) indica il grado del vertice v. Per gli alberi, la somma delle differenze assolute può essere riscritta in termini della sequenza di gradi ordinata, sfruttando il fatto che gli alberi hanno n‑1 spigoli e una struttura aciclica.

Nel caso dei caterpillar, la struttura è particolarmente regolare: esiste un cammino centrale (il "corpo") di lunghezza k, a cui sono attaccate foglie di grado 1. La formula presentata nello studio, irr(G)=(d_n-1)^2+(d_1-1)^2+∑_{i=2}^{n-1}(d_i-1)(d_i-2)+∑_{i=1}^{n-1}|d_i-d_{i+1}|, combina tre contributi distinti. Il primo termine cattura l’effetto del vertice di grado massimo, il secondo quello del minimo, il terzo somma prodotti che riflettono la “densità” dei vertici interni, mentre l’ultimo termine misura la variazione locale della sequenza di gradi.

Le due disuguaglianze di estremi derivano da un’analisi di ottimizzazione combinatoria. Per il minimo, si dimostra che la distribuzione più uniforme dei gradi, soggetta ai vincoli di somma dei gradi (∑d_i=2(n-1)), minimizza le differenze assolute. Per il massimo, si costruiscono configurazioni estreme in cui i gradi alti e bassi si alternano lungo il cammino, massimizzando le differenze locali.

Queste tecniche si basano su principi di majorizzazione e su lemmi di rearrangiamento, che garantiscono che una sequenza più “disordinata” (in senso di maggior spread) produce un indice più grande. Inoltre, l’analisi introduce il concetto di "indice medio di irregolarità", definito come irr(G)/(n-1), utile per confrontare alberi di dimensioni diverse.

Le implicazioni vanno oltre la teoria pura: in chimica computazionale, gli indici basati sui gradi sono correlati a proprietà fisico‑chimiche di molecole rappresentate come grafi. Un bound più stretto per l’Albertson index permette previsioni più accurate di stabilità termodinamica o reattività. In informatica, la misura può guidare algoritmi di bilanciamento di reti, dove si desidera minimizzare le disparità di carico tra nodi. Infine, la metodologia sviluppata può essere estesa ad altri indici di irregolarità, come l’indice di Zagreb o quello di Randić, fornendo un quadro unificato per lo studio delle disomogeneità nei grafi.