Il centro di un albero Fabrizio Pugliese October 22, 2016

(1)

Il centro di un albero

Fabrizio Pugliese

October 22, 2016

Abstract

Esponiamo il teorema di Jordan sul centro di un albero.

1 Il teorema di Jordan

Innanzitutto, ricordiamo la definizione di centro e di raggio di un grafo. Sia

G = (VG, EG) un grafo (finito, semplice, non orientato) e sia v ∈ VG un suo

vertice. Ricordiamo che l’eccentricit`a di v `e

eccG(v) = max w∈VG

d(w, w)

e che v è centrale quando la sua eccentricità è minima. L’insieme dei vertici centrali si chiama centro di G e si denota con Center(G), e l’eccentricità comune ai vertici centrali è il raggio rad(G) di G:

rad(G) = min

v∈VG

eccG(v)

Sia T = (VT, ET) un albero (finito, non orientato), vogliamo dimostrare il

seguente risultato.

Theorem 1 (Teorema di Jordan). Il centro di T `e formato da un solo vertice

oppure da due vertici adiacenti.

Per la dimostrazione di questo teorema abbiamo bisogno di alcuni risultati preliminari, che riassumiamo nella seguente proposizione.

Proposition 2 Sia T = (VT, ET) un albero, con WT ⊂ VT insieme delle foglie

e centro Center(T ). Valgono le seguenti propriet`a:

1. Se v, w ∈ VT sono tali che eccT(v) = dT(v, w), allora w ∈ WT

2. WT e Center(T ) sono disgiunti

(2)

3. T \WT e T hanno lo stesso centro

Proof. Per ogni coppia di vertici v, w ∈ T , indichiamo con vT w l’unico cammino in T fra tali vertici: evidentemente, la lunghezza di tale cammino `e uguale alla distanza dT(v, w). Per la dimostrazione del punto 1, se w non fosse una foglia,

allora sarebbe adiacente, oltre che al penultimo vertice di vT w, anche a un altro vertice z; ma allora il cammino vT wz = vT z sarebbe l’unico cammino fra v e z e quindi varrebbe

dT(v, z) = l(vT wz) = l(vT w) + 1 = dT(v, w) + 1 = eccT(v) + 1,

il che `e impossibile, per definizione di eccentricit`a.

Per quanto riguarda il punto 2, sia w ∈ WT, mostriamo che w /∈ Center(T ).

In effetti, detto u ∈ VT l’unico vertice adiacente a w, si ha per il punto 1 che

eccT(u) = dT(u, z),

per un opportuno z ∈ WT; ma allora

rad(T ) ≤ eccT(u) = dT(u, z) = l(zT u)

= l(zT w) − 1 = dT(w, z) − 1 < dT(w, z) ≤ eccT(w),

cioè l’eccentricità di w è maggiore del raggio di T .

Passiamo al punto 3. Il grafo T0 _{= T \W `e ancora un albero (in quanto}

aciclico e connesso), dunque, `e possibile applicare ad esso i risultati dei due punti precedenti. Sia W0 _{= W}

T0 l’insieme delle foglie di T0. Sia z ∈ V_T0, allora per

quanto visto al punto 1, esiste un vertice u ∈ W0 _{tale che ecc}

T0(z) = d_T0(z, u);

`e evidente (sempre per l’unicit`a dei cammini fra i vertici di un albero) che su

T0 _{la distanza d}

T0 coincide con d_T, per cui

eccT0(z) = d_T(z, u) = d_T(z, w) − 1,

dove w ∈ W `e una foglia di T adiacente a u; mostriamo che

eccT(z) = dT(z, w) (1)

Infatti, se cos`ı non fosse, cio`e se fosse eccT(z) > dT(z, w), esisterebbe w2 ∈

W \{w} tale che eccT(z) = dT(z, w2); ma allora, detto u2 ∈ W0 l’unico vertice

adiacente a w2, varrebbe

eccT0(z) ≥ d_T0(z, u₂) = d_T(z, w₂) − 1

= eccT(z) − 1 > dT(z, w) − 1 = dT0(z, u) = ecc_T0(z),

il che `e assurdo, per cui vale la (1), cio`e

eccT(z) = eccT0(z) + 1, (2)

(3)

per ogni z ∈ VT0. Ma la (2) implica proprio l’asserto del punto 3: infatti, per

il punto 2, la funzione eccT : VT → N0 pu`o assumere valore minimo solo su

VT0, e quindi, per la (2), i punti di minimo di ecc_T (cio`e i vertici di Center(T ))

coincidono coi punti di minimo di eccT0, cio`e Center(T0).

A questo punto, la dimostrazione del teorema di Jordan `e banale. Basta infatti costruire la sequenza di alberi:

T ⊃ T0_{⊃ (T}0₎0

⊃ . . . , (3)

in cui ogni albero `e ottenuto dal precedente eliminandone le foglie; per il punto 3 della proposizione 2, tali alberi hanno tutti lo stesso centro, cio`e quello di

T ; d’altra parte, la (3) `e strettamente decrescente, per cui si arresta dopo un

numero finito di passi, e l’ultimo albero sar`a o un vertice isolato oppure l’albero formato da un solo lato.

La dimostrazione del teorema di Jordan fornisce anche un semplice algoritmo per determinare il centro di T :

1. Al primo passo, assegnare l’etichetta ”0” alle foglie di T ;

2. all’i-mo passo (per i ≥ 2), assegnare l’etichetta ”i − 1” ai vertici v non etichettati nei passi precedenti e che soddisfino le seguenti due condizioni: a) v è adiacente ad almeno un vertice già etichettato in uno dei passi precedenti (con un numero da 1 a i − 2); b) v è adiacente a un solo vertice non etichettato da 1 a i − 2.

3. Dopo un numero finito di passi, si verificherà uno dei seguenti due casi: o c’è un solo vertice con etichetta massima, o ce ne sono due adiacenti; in entrambi i casi, il centro di T è costituito dai vertici di etichetta massima. Sempre riguardo al centro di un albero, vale la seguente proposizione. Proposition 3 Il centro di un albero T è anche il centro di qualsiasi cammino

diametrale in T ; di conseguenza, T è centrale se diam(T ) è pari, mentre è invece bicentrale se diam(T ) è dispari.

Proof. La seconda parte dell’enunciato `e evidente, dimostriamo la prima. Sia

P ⊂ T un cammino diametrale (cio`e, l(P ) = diam(T )); allora, per il punto 1

della proposizione 2, gli estremi di P sono due foglie, w1 e w2 (quindi, con le

notazioni usate in precedenza, P = w1T w2); dunque, il cammino P `e

massi-male, cio`e non `e incluso in un cammino pi`u lungo. Sia z ∈ VT un vertice non

appartenente a P : vogliamo dimostrare che z non è centrale, cioè che la sua eccentricità non è la minima possibile. A questo scopo, osserviamo che (sem-pre per l’aciclicità di T e la conseguente unicità del cammino fra due vertici)

(4)

esiste su P un unico vertice u ∈ P ∩ (zT w1) ∩ (zT w2); per la massimalit`a di P ,

u 6= w1, w2. Vogliamo dimostrare che eccT(z) > eccT(u). In effetti, vale

eccT(u) = max {dT(u, w1), dT(u, w2)} ,

perch`e, se cos`ı non fosse, esisterebbe y ∈ VT\{w1, w2} tale che

eccT(u) = dT(u, y) > dT(u, wi),

per i = 1, 2, e risulterebbe

dT(w1, y) = l(w1T uT y) = dT(w1, u) + dT(u, y) >

> dT(w1, u) + dT(u, w2) = dT(w1, w2) = diam(T ),

il che `e impossibile. D’altra parte, se , per fissare le idee, eccT(u) = dT(u, w1),

si ha

eccT(z) ≥ dT(z, w1) = dT(z, u) + dT(u, w1)

= dT(z, u) + eccT(u) > eccT(u),

che era quello che volevamo dimostrare.

Resta da dimostrare che Center(T ) = Center(P ). Allo scopo, osserviamo che, per ogni u ∈ P vale

eccT(u) = eccP(u). (4)

Infatti, se cos`ı non fosse, allora sarebbe eccT(u) > dT(u, wi), i = 1, 2, per cui

esisterebbe un vertice y /∈ P tale che eccT(u) = dT(y, u); ma allora, supponendo,

per fissare le idee, che il cammino yT u incontri per la prima volta P in un punto fra u e w1, si avrebbe

dT(w1, y) = d(w1, u) + d(u, y) = d(w1, u) + eccT(u) >

> d(w1, u) + d(u, w2) = d(w1, w2) = diam(T ),

che `e impossibile (analogo ragionamento vale se la prima intersezione fra P e

yT u giace fra u e w2); ci`o dimostra la (4). A questo punto, la dimostrazione `e

immediata.Infatti, da (4) segue che se u è T -centrale, cioè è di minimo per eccT,

allora lo `e anche per eccP, e viceversa.