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

   
Alberi radicati

Definizione 20.1   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 20.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 20.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 20.2   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 20.3   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 20.4   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$

   
Cenni sui grafi diretti

Definizione 20.5   Un grafo diretto è una coppia (V,E) dove V è un insieme e $E\subset V\times V$. Gli elementi di E vengono ancora chiamati lati e dati $v,w\in V(T)$ scriveremo $v\to_E w$, o più semplicemente $v\to w$ per dire che $(v,w)\in E$.

Osservazione 20.6   Intuitivamente un grafo diretto può essere pensato come un grafo, in cui sono specificati dei ``versi di percorrenza'' degli archi che congiungono due punti. Un po' come la mappa di una città in cui si tenga conto dei sensi unici.

Si osservi che, a differenza dei grafi dove tra due vertici cè soltanto un lato e non ci sono lati che vanno da un vertice a se stesso, tra due vertici v e w di un grafo diretto ci possono essere entrambi i lati $v\to w$ e $w\to v$, e si possono avere anche lati del tipo $v\to v$ (vedi figura 10).

  

Figure 10: Un grafo diretto

Si noti però che l'osservazione 14.2 mostra che dare un grafo è equivalente a dare un grafo diretto simmetrico (i.e. se $v\to w$ anche $w\to v$) e antiriflessivo (i.e. $v\not\to v$ per ogni v).

Osservazione 20.7   La proposizione 20.4 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.

Esercizio 20.2    Si diano le definizioni di passeggiata diretta, cammino diretto, ciclo diretto in un grafo diretto e si provi che due vertici sono congiungibili da una passeggiata diretta se e solo se sono congiungibili da un cammino diretto. Si usi questo fatto per provare che la relazione ``essere congiungibili da un cammino diretto'' è una relazione transitiva e riflessiva sull'insieme dei vertici di un grafo diretto. È vero che è una relazione d'equivalenza?
Soluzione

Composizione di relazioni

Ricordiamo la definizione di relazione tra insiemi:

Definizione 20.8   Se X e Y sono insiemi, una relazione tra X e Y è un sottinsieme ${\cal R}\subseteq X\times Y$, si usa la notazione $x{\cal R}y$ per dire che $(x,y)\in {\cal R}$.

Definizione 20.9   Siano ${\cal R}\subset X\times Y$ e ${\cal S}\subset Y\times Z$ si definisce la composizione di $\cal R$ con ${\cal S}$ la relazione ${\cal R}\circ{\cal S}\subseteq x\times Z$ definita da

$${\cal R}\circ{\cal S}= \{(x,z)\mid \exists y\in Y : x{\cal R}y \hbox{\rm { e }} y{\cal S}z\}$$

Esercizio 20.3    Si provi che se ${\cal R}\subseteq X\times Y$, ${\cal S}\subseteq Y\times Z$ e ${\cal T} \subseteq Z\times W$ allora

$${\cal R}\circ ({\cal S}\circ {\cal T})=({\cal R}\circ {\cal S}) \circ {\cal T}.$$

Soluzione

Definizione 20.10   Dato un insieme X si indica con I_X la relazione identica su X, ovvero $I_X=\{(x,x)\mid x\in X\}$.

Esercizio 20.4    Si provi che se $\cal R$ è una relazione tra X e Y, allora si ha che ${\cal R}\circ I_Y= I_X\circ {\cal R}={\cal R}$.
Soluzione

Esercizio 20.5    Siano ${\cal R}_1,{\cal R}_2$ delle relazioni tra X e Y e sia ${\cal S}$ una relazione tra Y e Z. Si provi che $({\cal R}_1\cup{\cal R}_2)\circ {\cal S}=(({\cal R}_1\circ {\cal S})\cup ({\cal R}_2\circ {\cal S})$.
Soluzione

Potenza di una relazione

Definizione 20.11   Data una relazione $\cal R$ su un insieme X, per ogni $n\in\mathbb N$, indicheremo con ${\cal R}^n$ la relazione su X definita ricorsivamente da:

$$\left\{ \begin{array}{ll} {\cal R}^0=I \\ {\cal R}^{n+1}=... ...}^n\circ{\cal R}&\forall n \in \mathbb N \end{array} \right.$$

${\cal R}^n$ è detta la potenza n-esima di $\cal R$.

Chiusura transitiva di una relazione

Definizione 20.12   Sia $\cal R$ una relazione su X, diremo che una relazione ${\cal T}$ è una chiusura transitiva di $\cal R$ se

1.

${\cal T}$ è transitiva

2.

${\cal T}\supseteq{\cal R}$

3.

per ogni relazione transitiva su X che estende $\cal R$ si ha ${\cal S}\supseteq {\cal T}$.

Teorema 20.13   Sia X un insieme e $\cal R$ una relazione su X, allora esiste una unica chiusura transitiva di $\cal R$, che è data da:

$${\cal R}^+=\bigcup_{n=1}^\infty {\cal R}^n.$$

Definizione 20.14   Sia $\cal R$ una relazione su X, diremo che una relazione ${\cal T}$ è una chiusura transitiva e riflessiva di $\cal R$ se

1.

${\cal T}$ è transitiva e riflessiva

2.

${\cal T}\supseteq{\cal R}$

3.

per ogni relazione transitiva e riflessiva su X che estende $\cal R$ si ha ${\cal S}\supseteq {\cal T}$.

Teorema 20.15   Sia X un insieme e $\cal R$ una relazione su X, allora esiste una unica chiusura transitiva e riflessiva di $\cal R$, che è data da:

$${\cal R}^*=\bigcup_{n=0}^\infty {\cal R}^n = I\cup {\cal R}^+.$$

Osservazione 20.16   I due teoremi precedenti (20.13 e 20.15) permettono di sostituiore l'articolo indeterminativo nelle definizioni 20.12 e 20.14 con l'articolo determinativo. Si parlerà quindi della chiusura transitiva e della chiusura transitiva e riflessiva di una relazione $\cal R$, che saranno denotate rispettivamente con ${\cal R}^+$ e ${\cal R}^*$. I teoremi già citati danno anche un modo costruttivo per trovare ${\cal R}^+$ e ${\cal R}^*$.

Esercizio 20.6    Sia $\cal R$ una relazione su X e sia ${\cal S}_n$ la successione di relazioni definite ricorsivamente da:

$$\left\{ \begin{array}{ll} {\cal S}_1 = I\cup {\cal R}\\ {... ...\cal S}_n\circ {\cal R}& \forall n \ge 1 \end{array} \right.$$

Si provi che ${\cal R}^*=\bigcup_{n=1}^\infty {\cal S}_n$.
Soluzione

Esercizio 20.7    Si provi che $x {\cal R}^n y$ se e solo se esistono $x_0,x_1,\dots,x_n\in X$ tali che $x_i {\cal R}x_{i+1}$ per ogni $i=0,\dots,n-1$ e x₀=x, x_n=y.
Soluzione

Esercizio 20.8    Si provi che se $\{{\cal R}_j\}_{j\in J}$ è un insieme di relazioni transitive su X allora $\bigcap _{i\in I} {\cal R}_i$ è ancora una relazione transitiva su X.

Si usi questo fatto per mostrare che

$${\cal R}^+=\bigcap_{{\cal S}\in S}{\cal S}$$

essendo $S=\{{\cal S}\subseteq X\times X\mid {\cal S}\supseteq {\cal R}\hbox{\rm { e }} {\cal S}\hbox{\rm { \\lq e transitiva}}\}$.
Soluzione

Esercizio 20.9    Si provi che se $\{{\cal R}_j\}_{j\in J}$ è un insieme di relazioni riflessive su X allora $\bigcap _{i\in I} {\cal R}_i$ è ancora una relazione riflessiva su X.

Si usi questo fatto per mostrare che

$${\cal R}^*=\bigcap_{{\cal S}\in S}{\cal S}$$

essendo $S=\{{\cal S}\subseteq X\times X\mid {\cal S}\supseteq {\cal R}\hbox{\rm { e }} {\cal S}\hbox{\rm { \\lq e transitiva e riflessiva}}\}$.
Soluzione