Lezione 20 (23 maggio 2001 h. 10.30-11.30)

Alberi

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

Figura 8: Un albero

Esercizio 20.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 20.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)$.

Figura 9: 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_0=u_0$ 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_0$ il minimo per cui ciò succede. Dato che $v_k=u_h$ esiste un $j>i_0$ tale che $v_j=u_s$ per qualche $s$, sia $j_0$ il minimo di tali $j$ ed $s_0$ tale che $v_{j_0}=u_{s_0}$. 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 9).

$(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_0$ e $u_{i+1}=v_1$. 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 10).

Figura 10: 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 20.3   Sia $G$ un grafo, un vertice $v\in V(G)$ tale che $\deg(v)=1$ sarà detto una foglia.

Esercizio 20.2   Si determinino le foglie dell'albero in figura 8
Soluzione

Lemma 20.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_0$ 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_0$ 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 20.5   Si osservi che il lemma precedente è falso se non si assume la finitezza dell'albero. Ad esempio l'albero $\big(\mathbb{N},\{\{n.n+1\}\mid n\in \mathbb{N}\}\big)$ ha una sola foglia (il vertice $0$), mentre l'albero $\big(\mathbb{Z},\{\{n.n+1\}\mid n\in \mathbb{Z}\}\big)$ non ha foglie.

Esercizio 20.3   Si provi che se $G$ è un grafo connesso e $v$ è una sua foglia, allora $G-v$ è ancora connesso.
Soluzione

Esercizio 20.4   Si provi che se $T$ è un albero e $v$ è una sua foglia, allora $T-v$ è un albero.
Soluzione

Esercizio 20.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 20.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-v$ è un albero ed inoltre $\left\vert V(T-v)\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-v)\right\vert-1=\left\vert E(T-v)\right\vert.$$

Ma dato che $\deg(v)=1$, $\left\vert E(T-v)\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 non esistessero foglie, ogni $v\in V(T)$ dovrebbe avere $\deg(v)\ge2$ (non possono esistere vertici di grado $0$ dato che $T$ è connesso ed ha almeno $2$ lati) e si otterrebbe subito un assurdo ( $2\left\vert V(T)\right\vert-2\ge2\left\vert V(T)\right\vert$). Pertanto 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. 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$ contraddicendo il fatto che $T-v$ è un albero.     $\square$

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