Lezione 19 (16 maggio 2000 h. 11-13)

   
Alberi

Definizione 19.1   Si dice albero un grafo connesso e senza cicli. Si dice una foresta un grafo senza cicli.

  

Figure 6: Un albero

Esercizio 19.1    Si provi che un grafo F è una foresta se e solo se ogni sua componente connessa è un albero.
Soluzione

   
Il teorema di caratterizzazione degli alberi

Teorema 19.2   Sia T=(V,E) un grafo. Sono equivalenti i seguenti fatti:

1.

T è un albero

2.

$\forall v,v'\in V$ esiste un unico cammino che congiunge v a v'

3.

T è connesso e $\forall e\in E$ il grafo T-e è sconnesso

4.

T non ha cicli e $\forall e\in {V \choose 2}$ il grafo T+e ha almeno un ciclo.

Dimostrazione.  Dimostriamo le implicazioni $(1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(4)\Rightarrow(1)$.

  

Figure: La costruzione del ciclo nella dimostrazione di $(1)\Rightarrow (2)$

$(1)\Rightarrow (2)$. Supponiamo per assurdo che esistano due diversi cammini in T che congiungono v e v'. Siano questi $(v_0,v_1,\dots,v_k)$, $(u_0,u_1,\dots,u_h)$ (i.e. v=v₀=u₀ e v'=v_k=u_h e per ogni i si ha che $\{v_i,v_{i+1}\}, \{u_i,u_i+1\}\in E$). Dato che i due cammini sono diversi esiste un i tale che $v_i\ne u_i$, sia quindi i₀ il minimo per cui ciò succede. Dato che v_k=u_h esiste un j>i₀ tale che v_j=u_s per qualche s, sia j₀ il minimo di tali j ed s₀ tale che v_j0=u_s0. Allora $(v_{i_0-1},v_{i_0}, \dots, v_{j_0},u_{s_0-1},\dots,u_{i_0+1},u_{i_0})$ è un ciclo (si veda figera 7).

$(2)\Rightarrow(3)$. Chiaramente T è connesso, dato che dati comunque due suoi vertici esiste (e per giunta è unico) un cammino che li congiunge.

Sia $e=\{v,v'\}\in E$, allora l'unico cammino in T tra v e v' è dato da (v,v'), quindi non esiste alcun cammino tra v e v' che non contenga il lato e, pertanto T-e è sconnesso.

$(3)\Rightarrow (4)$. Proviamo innanzitutto che T non ha cicli. Infatti se $(v_0,v_1,\dots,v_k,v_0)$ fosse un ciclo in T, allora detto $e=\{v_0,v_1\}$, il grafo T-e risulterebbe connesso. Infatti siano $v,v'\in V$, e sia $P=(u_0,\dots,u_h)$ un cammino che li congiunge. Allora o nessuno dei lati di tale cammino coincide con il lato e, ed in tal caso P è un cammino anche in T-e, oppure un lato è uguale a e. In questa evenienza esiste i tale che $\{u_i,u_{i+1}\}=\{v_0,v_1\}$ e, a meno di riordinare in ordine inverso i vertici del cammino, possiamo supporre cghe u_i=v₀ e u_i+1=v₁. Ma allora $(u_0,\dots,u_i,v_{k},v_{k-1},\dots,v_1,u_{i+2},\dots,u_h)$ risulta essere una passeggiata in T-e che congiunge v e v' (vedi figura 8).

  

Figure: La costruzione della passeggiata nella dimostrazione di $(3)\Rightarrow (4)$

Proviamo ora che T+e ha dei cicli. Siano $v,v'\in V$ tali che $e=\{v,v'\}\notin E$. Dato che T è connesso, esiste un cammino che congiunge v a v'. Sia questo $(v_0,v_1,\dots,v_k)$. Evidentemente allora $(v_0,v_1,\dots,v_k,v_0)$ è un ciclo in T+e.

$(4)\Rightarrow(1)$. Dobbiamo provare che T è connesso (sappiamo già che non ha cicli). Siano $v,v'\in V$. Se $\{v,v'\}\in E$ non c'è nulla da provare, dato che (v,v')è un cammino che congiunge v a v'. Se $e=\{v,v'\}\notin E$, allora sappiamo che il grafo T+e contiene un ciclo, sia questo $C=(v_0,v_1,\dots,v_k,v_0)$. Chiaramente uno dei lati del ciclo deve essere proprio e, dato che altrimenti il ciclo sarebbe in T (che non ha cicli!). Supponiamo quindi v_i=v e v_i+1=v'. Il cammino $(v_{i+1},\dots,v_k,v_0,v_1,\dots,v_i)$ è allora un cammino in T che congiunge v' a v.     $\square$

   
Il teorema di caratterizzazione degli alberi finiti

Definizione 19.3   Sia G un grafo, un vertice $v\in V(G)$ tale che $\deg(v)=1$ sarà detto una foglia.

Esercizio 19.2    Si determinino le foglie dell'albero in figura 6
Soluzione

Lemma 19.4   Ogni albero finito ha almeno due foglie

Dimostrazione.  Sia $P=(v_0,v_1,\dots,v_k)$ un cammino di lunghezza massima, proviamo che v₀ e v_k sono due foglie. Se per assurdo $\deg(v_0)>1$ allora esisterebbe $v'\in V$ tale che $\{v',v_0\}\in E$ e $v'\ne v_1$. Osserviamo che allora non potrebbe essere v'=v_i per qualche i>1, perché in tal caso, detto i₀ il minimo di tali i si avrebbe che $(v',v_0,\dots,v_i)$ sarebbe un ciclo, contro l'ipotesi che T sia un albero. Ma allora $(v',v_0,\dots,v_k)$ sarebbe un cammino di lunghezza maggiore di quella di P, che è assurdo.

In modo analogo si prova che anche v_k è una foglia. (Oppure ci si riconduce al caso precedente, prendendo il cammino $P'=(v_k,\dots,v_1,v_0)$).     $\square$

Osservazione 19.5   Si osservi che il lemma precedente è falso se non si assume la finitezza dell'albero. Ad esempio l'albero $(\mathbb N,\{\{n.n+1\}\mid n\in \mathbb N\}$ ha una sola foglia (il vertice 0), mentre l'albero $(\mathbb Z,\{\{n.n+1\}\mid n\in \mathbb Z\}$ non ha foglie.

Esercizio 19.3      Si provi che se G è un grafo connesso con almeno due vertici e v è una sua foglia, allora G-v è ancora connesso.
Soluzione

Esercizio 19.4      Si provi che se T è un albero con almeno due vertici e v è una sua foglia, allora T-v è un albero.
Soluzione

Esercizio 19.5    Quante foglie può avere al massimo un grafo connesso con n vertici? Si determini un grafo con il massimo numero di foglie possibili.
Soluzione

Teorema 19.6   Sia T=(V,E) un grafo finito. Sono fatti equivalenti:

1.

T è un albero

5.

T è connesso e $\left\vert V\right\vert - 1 = \left\vert E\right\vert$

Dimostrazione.  $(1)\Rightarrow(5)$. Procediamo per induzione su $\left\vert V(T)\right\vert$. Se $\left\vert V(T)\right\vert=1$la tesi è vera. Supponiamo che $\left\vert V(T)\right\vert\ge 2$, e sia $v\in V(T)$ una sua foglia (che esiste per il lemma precedente, ora T-e è un albero ed inoltre $\left\vert V(T-e)\right\vert=\left\vert V(T)\right\vert-1$. Per ipotesi di induzione si ha allora che

$$\left\vert V(T)\right\vert-1-1=\left\vert V(T-e)\right\vert-1=\left\vert E(T-e)\right\vert.$$

Ma dato che $\deg(v)=1$, $\left\vert E(T-e)\right\vert=card{E(T)}-1$ e quindi la tesi.

$(5)\Rightarrow(1)$. Dobbiamo provare che T non ha cicli. Procediamo ancora per induzione su $\left\vert V(T)\right\vert$. Se $\left\vert V(T)\right\vert=1$ la tesi è vera. Supponiamo che $\left\vert V(T)\right\vert\ge 2$. Proviamo innanzitutto che T ha una foglia. Dalla relazione tra numero di vertici e numero di lati, e dalla relazione che lega il numero di lati con i gradi dei vertici, si ottiene

$$2\left\vert V(T)\right\vert-2=2\left\vert E(T)\right\vert=\sum_{v\in V(T)}\deg(v)$$

se per ogni v si avesse che $\deg(v)\ge2$ si otterrebbe subito un assurdo ( $2\left\vert V(T)\right\vert-2\ge2\left\vert V(T)\right\vert$) e quindi almeno un vertice deve avere grado 1. Sia quindi v una foglia di T, e si consideri il grafo T-v.

Dato che T è connesso e $\deg(v)=1$, anche T-v è connesso (un cammino in T che congiunge due vertici diversi da v non può passare per v, in quanto i vertici di un cammino, eccetto al più il primo e l'ultimo, hanno grado almeno 2). Inoltre, poiché $\left\vert V(T-v)\right\vert=\left\vert V(T)\right\vert-1$ e $\left\vert E(T-v)\right\vert=\left\vert E(T)\right\vert-1$, si ha che $\left\vert V(T-v)\right\vert-1=\left\vert E(T-v)\right\vert$. Per ipotesi di induzione allora T-v è un albero. Ma allora T non ha cicli, in quanto i vertici di un ciclo hanno tutti grado almeno 2 e quindi un ciclo in T non potrebbe passare per v, ossia sarebbe contenuto in T-v e ciò contraddice il fatto che T-v è un albero.     $\square$

Esercizio 19.6    Se F=(V,E) è una foresta allora $\left\vert V\right\vert-\left\vert E\right\vert=k$, essendo k il numero di componenti connesse di F.
Soluzione

Esercizio 19.7    Si provi che ogni grafo connesso finito G, ha un sottografo che è un albero e contiene tutti i vertici di G.

Un tale albero si chiama un albero generatore di G.
Soluzione

Esercizio 19.8    Si provi che se G=(V,E) è un grafo connesso finito, allora $\left\vert E\right\vert\ge\left\vert V\right\vert-1$.
Soluzione