Lezione 22 (29 maggio 2000 h. 9-11)

Il lemma di König

Domanda. È vero che in un albero infinito esiste un ramo infinito?

Per ramo infinito intendiamo un cammino infinito (i.e. un sottografo isomorfo a $P_\infty$).

In generale la risposta a questa domanda è negativa. Si consideri ad esempio il grafo $G=(\mathbb N,\{\{0,i\}\mid i\ge 1\}$ (vedi figura).

  

Figure 11: Un contresempio al Lemma di König, senza l'ipotesi dei gradi finiti

G è un albero. Infatti G è connesso dato che ogni vertice è congiungibile al vertice 0. Inoltre se $e=\{0,i\}$ è un lato, allora $G-e=(\mathbb N-\{0,i\},\varnothing)$ che è sconnesso. Quindi G è un albero per la terza delle proprietà caratterizzanti degli alberi.

D'altra parte i cammini più lunghi che si possono trovare sono i cammini del tipo (i,0,j) con $i\ne j$, che hanno lunghezza 2.

Il problema sta nel fatto che nell'albero dell'esempio c'è un vertice di grado infinito (su 0 arrivano infiniti lati). In effetti vale il seguente teorema:

Teorema 22.1 (Lemma di König)   Sia T un albero infinito tale che ogni vertice ha grado finito, allora T ha rami infiniti.

Dimostrazione.  Fissiamo una radice r per T e sia $\to$ la relazione di paternità indotta da tale radice. Costruiremo una funzione $f:\mathbb N\to V(T)$ con la seguente proprietà:

$$f(n-1) \to f(n) \hbox{\rm { e }} \big\{v\in V(T) \bigm \vert f(n)\to^* v\big\} \hbox{\rm { \\lq e infinito}}\forall n \ge 1$$

Chiaramente, una tale funzione risolve il problema.

Definiamo f ricorsivamente. Poniamo f(0)=r. Chiaramente i discendnti di f(0) sono infiniti (tutti i vertici sono discendenti della radice).

Supponiamo di aver definito f(n) (che sia figlio di f(n-1) e che abbia una discendenza infinita). Per ipotesi $\deg(f(n))$ è finito, siano quindi $v_1,\dots,v_k$ i figli di f(n) (i.e. $f(n)\to v_i$). Per ogni $i=1,\dots,k$sia

$$V_i=\big\{v\in V(T)\bigm\vert v_i\to^* v\}$$

Chiaramente

$$\big\{v\in V(T) \bigm \vert f(n)\to^* v\big\} = \{f(n)\} \cup V_1\cup\dots\cup V_k$$

Pertanto esiste un i tale che V_i è infinito. Basta allora porre f(n+1)=v_i. Chiaramente $f(n)\to f(n+1)$ e la discendenza di f(n+1), che è V_i, è infinita.     $\square$

Albero generatore di un grafo

Definizione 22.2   Sia G un grafo, diremo che un albero T è un albero generatore (in inglese spanning tree se T è un sottografo di G e V(T)=V(G).

Osservazione 22.3   Si osservi che se G possiede un albero generatore T, allora necessariamente è connesso, in quanto T è connesso.

Esistenza di alberi generatori: il caso finito

Teorema 22.4   Sia G un grafo finito connesso, allora G possiede un albero generatore.

Dimostrazione.  Procediamo per induzione su $\left\vert E{G}\right\vert$. Se $\left\vert E{G}\right\vert=0$ allora $\left\vert V(G)\right\vert=1$ (l'unico grafo connesso che non ha lati ha un solo vertice) e quindi $G\oldcong(\{0\},\varnothing\})$ è un albero.

Supponiamo che $\left\vert E{G}\right\vert>0$, allora o G è un albero e quindi lui stesso è un albero generatore di se stesso, oppure per la terza delle proprietà che caratterizzano gli alberi esiste un lato $e\in E(G)$ tale che G-e è ancora connesso. Ma allora $\left\vert E(G-e)\right\vert=\left\vert E(G)\right\vert-1$, quindi, per ipotesi di induzione, esiste un albero T che è un sottografo di G-e e tale che V(T)=V(G-e). Dato che V(G-e)=V(G), T è un albero generatore anche per G.     $\square$

Osservazione 22.5   Si osservi che la dimostrazione del teorema precedente, fornisce un algoritmo ricorsivo per la costruzione di un albero generatore di un grafo connesso finito. Un algoritmo più efficiente è dato nel seguenteesercizio.

Esercizio 22.1    Sia G un grafo connesso, finito e siano $e_1,\dots, e_n$ i suoi lati. Si ponga

$$\begin{eqnarray*}T_0 & = & \big(\{V(G)\},\varnothing\big)\\ T_{i+1} & = & \le... ... \\ T_i+e_{i+1} &\hbox{\rm {altrimenti}} \end{array} \right. \end{eqnarray*}$$

Si provi che T_n è un albero generatore per G.
Soluzione