Teoria dei grafi alberi

[Leonardo202]

Salve, scusate ma non riesco a capire perchè queste tre definizioni sono equivalenti:

Sia G=(V,L) un grafo finito allora:
1)G è un albero
2)G è connesso e |V|=|L|+1
3)G è una foresta e |V|=|L|+1

ed in particolare come posso dimostrare che se T=(V,L) è un albero finito esso ha
|V|=|L|+1 ossia il numero dei vertici è uguale al numero dei lati +1??
grazie

[tuccio2]

"Leonardo20":Salve, scusate ma non riesco a capire perchè queste tre definizioni sono equivalenti:

Sia G=(V,L) un grafo finito allora:
1)G è un albero
2)G è connesso e |V|=|L|+1
3)G è una foresta e |V|=|L|+1

ed in particolare come posso dimostrare che se T=(V,L) è un albero finito esso ha
|V|=|L|+1 ossia il numero dei vertici è uguale al numero dei lati +1??
grazie

Dimostrare che se [tex]G(V,E)[/tex] è un grafo semplice connesso e [tex]$|V|=|E|+1$[/tex], allora G non ha cicli (e quindi è un albero), lo puoi fare per induzione su [tex]$|V|$[/tex]. Perché per [tex]$n=1$[/tex] esiste un solo grafo a meno di isomorfismi, e dunque è il tuo caso base, non avendo archi

nel passo induttivo, sai che per [tex]$n-1$[/tex] la proposizione è vera, dunque si può dimostrare che per [tex]$n>1$[/tex] esistono almeno due vertici di grado 1 (cioè, foglie).. dunque se consideri il sottoalbero indotto da [tex]$V=V-\left\{ x\right\}$[/tex], dove x è una foglia.. questo sottoalbero non ha cicli per l'ipotesi induttiva, dunque se a questo riaggiungi x e l'arco che hai tolto, questo non può chiudere un ciclo (essendo x di grado 1), dunque è vero per ogni n

questo dovrebbe rispondere alla 2, per quanto riguarda la 3 invece.. una foresta [tex]$F$[/tex] ha un insieme di componenti connesse, [tex]$\lambda(F)$[/tex]. Le componenti connesse di una foresta sono alberi (grafi connessi non aciclici). Dunque: [tex]$|V_{F}|=\sum\limits_{T\in\lambda(F)}|V_{T}|=\sum\limits _{T\in\lambda(F)}\left(|E_{T}|+1\right)=\lambda+\sum\limits _{T\in\lambda(F)}|E_{T}|=\lambda+|E_{F}|$[/tex], dove [tex]$\lambda = |\lambda(F)|$[/tex]

ora se per ipotesi hai che [tex]$|V_{F}|=1+|E_{F}|$[/tex], vuol dire che [tex]$\lambda=1$[/tex], cioè hai una sola componente connessa (cioè un grafo aciclico connesso, dunque un albero)