Lezione 21

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. Dato che due vertici di $G$, essendo vertici di $T$ saranno congiunti da un cammino in $T$, e dato che $T$ è un sottografo di $G$ tale cammino sarà un cammino anche in $G$.

Esercizio 21.1   Si dia una dimostrazione formale di quanto appena osservato. E si provi che se $G$ è un grafo e $G'$ è un suo sottografo connesso tale che $V(G')=V(G)$ allora $G$ è connesso.
Soluzione

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

Dimostrazione.  Diamo due dimostrazioni di questo teorema, entrambe costruttive: una che costruisce un albero di copertura ``partendo dal basso'' ed una che lo costruisce ``partendo dall'alto''.

Prima dimostrazione. Si consideri l'insieme

$${\cal T}=\{T\mid T$$    è sottografo di $$G$$    e $$T$$ è un albero$$\}$$

${\cal T}\ne\varnothing$, infatti se $v\in\vee (G)$ allora $(\{v\},\varnothing )\in{\cal T}$ (i.e. è un sottografo che è un albero). Dato che $G$ è finito, esiste $\overline{T}\in{\cal T}$ con massimo numero di vertici, ossia tale che

$$\left\vert V(T)\right\vert \le \left\vert V(\overline{T})\right\vert \quad \forall T\in {\cal T}.$$

Se proviamo che $V(\overline{T})=V(G)$ avremo trovato un albero di copertura. Supponiamo che esista $v\in V(G) \setminus V(\overline{T})$, allora, usando la connessione di $G$ con la stessa tecnica usata nella dimostrazione del teorema 19.8, è possibile determinare un vertice $w\in V(G)\setminus V(\overline{T})$ ed un vertice $u\in V(T)$ tali che $\{u,w\}\in E(G)$ (si congiunge $v$ ad un vertice di $\overline{T}$ e si prendono il primo vertice del cammino che arriva in $\overline{T}$ ed il suo predecessore). Ma allora $T'=(V(\overline{T})\cup\{w\},E(\overline{T})\cup\{\{u,w\}\})$ è evidentemente un sottografo di $G$ ed è un albero. Quest'ultimoa asserzione si prova esattamente come nella seconda parte della dimostrazione del teorema di caratterizzazione degli al;beri finiti). In altri termini $T'\in{\cal T}$, d'altra parte $\left\vert V(T')\right\vert=\left\vert V(\overline{T})\right\vert+1$ e questo è in contraddizione con la massimalità di $\overline{T}$. Questo conclude la prima dimostrazione.

Seconda dimostrazione.  Si consideri l'insieme

$${\cal C}=\{C\mid C$$    è sottografo connesso di $$G$$ e $$V(C)=V(G)\}$$

${\cal C}\ne \varnothing$ dato che $G\in{\cal C}$. Data la finitezza di $G$ esisterà un grafo $\overline{C}\in{\cal C}$ con il minor numero di lati, ovvero

$$\left\vert E(\overline{C})\right\vert\le\left\vert E(C)\right\vert \quad \forall C\in{\cal C}$$

Proviamo che $\overline{C}$ è un albero. Infatti se non lo fosse, per la proprietà (3) del teorema di caratterizzazione degli alberi esisterebbe un lato $e\in E(\overline{C})$ tale che $\overline{C}-e$ è connesso. Ma $V(\overline{C}-e)=V(C)=V(G)$, quindi $C\in {\cal C}$, e d'altra parte $\left\vert E(\overline{C})-e\right\vert=\left\vert E(\overline{C})\right\vert-1=$, che contraddice la minimalità di $\overline{C}$. Questo conclude la seconda dimostrazione.     $\square$

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 (si veda teorema 23.4).

Esercizio 21.2   Si traducano le due dimostrazioni del teorema precedente in due algoritmi per la determinazione di un albero di copertura di un grafo finito.
Soluzione

Esercizio 21.3   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

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.4   Si considerino i grafi in figura 12. Si provi che $T\oldcong T'$ ma $(T,r)\not\oldcong (T',r')$.

Figura 12: Gli alberi radicati dell'esercizio 21.4

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_0=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_0=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.