Lezione 21 (28 maggio 2001 h. 9.30-10.30)

Albero di copertura

Definizione 21.1   Sia G un grafo, un sottografo T di G si dirà un albero di copertura di G se

• T è un albero;
• V(T)=V(G).

Osservazione 21.2   Chiaramente, se G è un grafo che possiede un albero di copertura, allora G è connesso.

Teorema 21.3   Sia G un grafo connesso finito allora G ha un albero di copertura.

Osservazione 21.4   Il teorema precedente è vero anche senza l'ipotesi di finitezza, del grafo G, la sua dimostrazione nel caso infinito, richiede però degli strumenti un po' più sofisticati (il lemma di Zorn).

   
Alberi radicati

Definizione 21.5   Un albero con radice è una coppia (T,r) con T un albero e $r\in V(T)$ un vertice fissato che sarà detto radice. Se (T,r) e (T',r') sono due alberi radicati, si dirà che sono isomorfi (come alberi radicati) se esiste un isomorfismo di grafi f tra T e T' tale che f(r)=r', e si scriverà $(T,r)\oldcong(T'.r')$.

Esercizio 21.1      Si considerino i grafi in figura 9. Si provi che $T\oldcong T'$ ma $(T,r)\not\oldcong(T',r')$.

  

Figure 9: Gli alberi radicati dell'esercizio 21.1

Soluzione

   
La relazione $\to$ di ``paternità'' in un albero radicato

Dato un albero radicato, (T,r) per ogni vertice $v\in V(T)$ indichiamo con P_v l'unico cammino che congiunge r con v.

Proposizione 21.6   Sia (T,r) un albero radicato e sia $\{v,w\}\in E(T)$, allora vale una e una sola delle seguenti:

1.

v è un vertice di P_w

2.

w è un vertice di P_v.

Dimostrazione.  Proviamo che ne vale almeno una. Se non vale la (1), allora $P_w=(v_0,\dots,v_k)$ con v₀=r, v_k=w e $v_i\ne v$ per ogni i. Ma allora, dato che $\{v,w\}\in E(T)$, $(v_0,\dots,v_k,v)$ è un cammino che congiunge r a v, per l'unicità di tale cammino $P_v=(v_0,\dots,v_k,v)$, e quindi vale la (2).

Proviamo ora che non possono valere contemporaneamente. Se vale la (1), allora $P_w=(v_0,\dots,v_k)$ con v₀=r, v_k=w ed esiste un i tale che v_i=v. Ma allora $P_v=(v_0,\dots,v_i)$. Dato che, $\{v,w\}\in E(T)$, $w\ne v$, quindi i<k, e dato che P_w è un cammino $w=v_k\ne v_j$ per ogni j<k, quindi w non compare in $P_v=(v_0,\dots,v_i)$.     $\square$

Definizione 21.7   Sia (T,r) un albero radicato, e siano $v,w\in V(T)$, diremo che v è padre di w, o che w è figlio di v, e lo indicheremo con $v\to w$, se $\{v,w\}\in E(T)$ e v è un vertice di P_w.

Proposizione 21.8   Sia (T,r) un albero radicato, e sia $\{v,w\}\in E(T)$ allora o $v\to w$ o $w\to v$. Inoltre per ogni $v,w\in V(T)$, se $v\to w$ allora $w\not\to v$.

Dimostrazione.  È semplicemente la proposizione precedente tradotta in termini della relazione $\to$.     $\square$

Osservazione 21.9   La proposizione 21.8 può essere interpretata dicendo che ogni albero radicato può essere dotato in modo naturale di una struttura di grafo diretto, in modo che ad ogni lato dell'albero corrisponda uno ed un solo lato del grafo diretto.