Albero, foglie (problema quasi noto)

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Talete
Messaggi: 744
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Albero, foglie (problema quasi noto)

Messaggio da Talete » 04 mag 2015, 23:39

Dato un albero (finito) $\mathcal{T}$, dimostrare che se non ci sono vertici con valenza $2$ in $\mathcal{T}$, allora il numero di foglie è maggiore del numero degli altri vertici.

Nota. Vabbè, tanto lo sapete. Comunque, un albero è un grafo connesso senza cicli e una foglia è un vertice di un albero con valenza $1$.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Albero, foglie (problema quasi noto)

Messaggio da Lasker » 05 mag 2015, 17:53

Allora, è abbastanza noto che un albero di $V$ vertici ha esattamente $V-1$ lati; ma con un double counting abbastanza standard sulla valenza totale del grafo (chiamato $f$ il numero di foglie) si ha
$$2(V-1)=\sum_{v} \deg(v)\Rightarrow 2(V-1)=f+\sum_{v\ne f} \deg(v)$$
Supponendo che non ci siano vertici di valenza $2$, al minimo ogni vertice che non è una foglia (sono $V-f$) avrà valenza $3$, da cui
$$2(V-1)=f+\sum_{v\ne f} \deg(v)\geq f+\sum_{v\ne f} 3= f+3(V-f)$$
Dunque, risolvendo la disequazione si ottiene
$$2f\geq V+2\Rightarrow f\geq \frac{V}{2}+1$$
Quindi le foglie sono sicuramente più della metà dei vertici totali e abbiamo dimostrato la tesi.
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!

Rispondi