Esercizi · Grafi¶

Esercizi · Capitolo 1 · ogni soluzione si apre con un clic · Capitolo 1: Grafi · Eserciziario, volume 1 (PDF)

Regole utilizzate in questi esercizi

Le definizioni e gli algoritmi del capitolo «Grafi», per un grafo orientato $G=(N,A)$ con $n=|N|$ e $m=|A|$.

(G1) Matrice di incidenza. Gli archi sono numerati $a_1,a_2,\dots,a_m$ in ordine lessicografo e

\[ b_{ik}=\begin{cases} +1 & \text{se $i$ è la coda di } a_k,\\ -1 & \text{se $i$ è la testa di } a_k,\\ 0 & \text{altrimenti.} \end{cases} \]
(G2) Liste. La lista di adiacenze $L(i)$ contiene i successori di $i$, per indice crescente.
(G3) Componenti. $R(i)$ è l'insieme dei nodi raggiungibili da $i$, $R'(i)$ lo stesso insieme nel grafo invertito e il componente fortemente connesso di $i$ è $S(i)=R(i)\cap R'(i)$.
(G4) Alberi e rango. $n-1$ archi formano uno albero ricoprente se e solo se sono aciclici (o connessi tutti i nodi); con componenti collegati $k$, $\rank(\mat{B})=n-k$.
(G5) Cerca. Un nodo viene etichettato quando entra in $\mathit{LIST}$. Il BFS seleziona il primo nodo di $\mathit{LIST}$, il DFS l'ultimo; il nodo selezionato $i$ etichetta il primo nodo senza etichetta $j$ di $L(i)$, con $\mathit{pred}(j)=i$, oppure lascia $\mathit{LIST}$ se non ce n'è.

Esercizio 1.1: Rappresentazioni di un grafo

Esercizio

Consideriamo il grafo orientato $G=(N,A)$ con $N=\{1,2,\dots,5\}$ e gli archi $7$

\[ A=\{(1,2),(1,3),(2,3),(2,4),(5,1),(5,3),(5,4)\}, \]

disegnato qui sotto.

Figura 1

Domande

Numerare gli archi come in (G1) e scrivere la matrice di incidenza nodo-arco $\mat{B}$.
Scrivi le liste di adiacenza e la lista degli archi di $G$.
Calcola il grado esterno e quello interno di ogni nodo e il vettore $\mat{B}\vet{x}$ per $x_{ij}=1$ su ogni arco.
Quante voci memorizzano la matrice di adiacenza, la matrice di incidenza, la lista di archi e le liste di adiacenza?

Soluzione

Usiamo le regole (G1)–(G5) del riquadro all'inizio di questi esercizi.

Gli archi in ordine lessicografo sono $a_{1}=(1,2)$, $a_{2}=(1,3)$, $a_{3}=(2,3)$, $a_{4}=(2,4)$, $a_{5}=(5,1)$, $a_{6}=(5,3)$, $a_{7}=(5,4)$. Ogni colonna ha $+1$ nella riga della coda e $-1$ nella riga della testa:

\[ \begin{array}{c|rrrrrrr} & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} & a_{6} & a_{7}\\ \hline 1 & 1 & 1 & 0 & 0 & -1 & 0 & 0\\ 2 & -1 & 0 & 1 & 1 & 0 & 0 & 0\\ 3 & 0 & -1 & -1 & 0 & 0 & -1 & 0\\ 4 & 0 & 0 & 0 & -1 & 0 & 0 & -1\\ 5 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\ \end{array} \]
Le liste di adiacenza e la lista di archi sono:

$i$ $L(i)$

$1$ $2,~3$

$2$ $3,~4$

$3$ (vuoto)

$4$ (vuoto)

$5$ $1,~3,~4$

arco $a_{1}$ $a_{2}$ $a_{3}$ $a_{4}$ $a_{5}$ $a_{6}$ $a_{7}$

coda $1$ $1$ $2$ $2$ $5$ $5$ $5$

testa $2$ $3$ $3$ $4$ $1$ $3$ $4$
I gradi sono i numeri di $+1$ e di $-1$ in ciascuna riga di $\mat{B}$:

nodo $i$ $1$ $2$ $3$ $4$ $5$

$\deg^+(i)$ $2$ $2$ $0$ $0$ $3$

$\deg^-(i)$ $1$ $1$ $3$ $2$ $0$

Entrambe le righe si sommano a $m=7$. La riga $i$ di $\mat{B}\vet{x}$ è $\deg^+(i)-\deg^-(i)$:

\[ \mat{B}\vet{x}=(1,\,1,\,-3,\,-2,\,3)' . \]

Il nodo $5$ non ha un arco in entrata e i nodi $3,4$ non hanno un arco in uscita.
La matrice di adiacenza memorizza le voci $n^2=25$, la matrice di incidenza $n\,m=35$, l'elenco di archi $2\,m=14$ e gli elenchi di adiacenza $n+m=12$.

Ogni colonna di $\mat{B}$ ha uno $+1$ e uno $-1$, quindi la somma delle sue righe dà zero; gli elenchi di adiacenza sono la rappresentazione più piccola, con voci $12$.

Esercizio 1.2: Componenti connessi e fortemente connessi

Esercizio

Consideriamo il grafo orientato $G=(N,A)$ con $N=\{1,2,\dots,8\}$ e gli archi $11$

\[ A=\{(1,7),(2,3),(2,7),(3,1),(3,6),(4,5),(6,2),(6,7),(6,8),(7,8),(8,1)\}, \]

disegnato qui sotto.

Figura 2

Domande

Trova le componenti connesse di $G$ (del suo grafo non orientato sottostante). $G$ è debolmente connesso?
Calcola $R(1)$ e $R'(1)$ e il componente fortemente connesso $S(1)$.
Trova tutti i componenti fortemente connessi di $G$. $G$ è fortemente connesso?

Soluzione

Usiamo le regole (G1)–(G5) del riquadro all'inizio di questi esercizi.

Trascurando l'orientamento, i vertici si dividono nelle componenti $\{1,2,3,6,7,8\}$, $\{4,5\}$: nessun lato ne unisce due. $G$ ha componenti $k=2$, quindi non è debolmente connesso.
Seguendo gli archi da $1$ si ottiene $R(1)=\{1,7,8\}$; seguendoli a ritroso (nel grafo invertito) otteniamo $R'(1)=\{1,2,3,6,7,8\}$. Quindi

\[ S(1)=R(1)\cap R'(1)=\{1,7,8\}. \]
Per un nodo $h$ di ciascun componente (il più piccolo non ancora assegnato), da (G3):

\[ \begin{array}{cccc} \hline {h} & {R(h)} & {R'(h)} & {S(h)} \\ \hline {1} & {\{1,7,8\}} & {\{1,2,3,6,7,8\}} & {\{1,7,8\}} \\ {2} & {\{1,2,3,6,7,8\}} & {\{2,3,6\}} & {\{2,3,6\}} \\ {4} & {\{4,5\}} & {\{4\}} & {\{4\}} \\ {5} & {\{5\}} & {\{4,5\}} & {\{5\}} \\ \hline \end{array} \]

I componenti $4$ fortemente connessi sono $\{1,7,8\}$, $\{2,3,6\}$, $\{4\}$, $\{5\}$. Ce n'è più di uno, quindi $G$ non è fortemente connesso.

$G$ dispone di componenti $2$ collegati e componenti $4$ fortemente connessi; ogni componente fortemente connessa si trova all'interno di una componente connessa.

Esercizio 1.3: Alberi e rango della matrice di incidenza

Esercizio

Consideriamo il grafo orientato $G=(N,A)$ con $N=\{1,2,\dots,6\}$ e gli archi $9$

\[ A=\{(1,2),(2,5),(2,6),(3,5),(4,2),(5,1),(5,4),(6,1),(6,3)\}, \]

disegnato di seguito e i due set di archi $5$

\[ F_1=\{(1,2),(3,5),(5,4),(6,1),(6,3)\}, \qquad F_2=\{(2,5),(2,6),(3,5),(4,2),(6,3)\}. \]

Figura 3

Domande

Calcola il rango della matrice di incidenza nodo-arco $\mat{B}$ di $G$, senza scrivere la matrice.
Decidere se $F_1$ e $F_2$ sono albero ricoprente di $G$.
Per l'insieme che non è uno albero ricoprente, trovare un ciclo e una combinazione lineare delle sue colonne di $\mat{B}$ uguali a $\vet{0}$.
Trovare il ciclo fondamentale dell'arco $(2,5)$ rispetto allo albero ricoprente $F_1$ e ai suoi archi all'indietro.
Togliere da $G$ tutti gli archi incidenti al nodo $6$. Qual è il rango della nuova matrice di incidenza?

Soluzione

Usiamo le regole (G1)–(G5) del riquadro all'inizio di questi esercizi.

Il grafo non orientato sottostante è connesso ($k=1$): da (G4), $\rank(\mat{B})=6-1=5$.
$F_1$ ha archi $5$ e nessun ciclo, quindi è uno albero ricoprente di (G4); i suoi lati collegano tutti i nodi.

$F_2$ ha archi $5$, ma i suoi lati hanno le componenti $\{1\}$, $\{2,3,4,5,6\}$: non collega tutti i nodi, quindi contiene un ciclo e non è uno albero ricoprente.
Gli archi di $F_2$ contengono il ciclo $2,5,3,6,2$. Percorrendolo gli archi $(2,5)$ avanti, $(3,5)$ indietro, $(6,3)$ indietro, $(2,6)$ indietro danno, con $+1$ per gli archi avanti e $-1$ per quelli indietro,

\[ \mat{B}_{a_{2}} -\mat{B}_{a_{4}} -\mat{B}_{a_{9}} -\mat{B}_{a_{3}}=\vet{0}, \]

con gli archi numerati come in (G1). Le colonne di $F_2$ sono linearmente dipendenti.
Nell'albero $F_1$ il percorso da $5$ a $2$ è $5,3,6,1,2$. Il ciclo fondamentale, scritto dalla coda di $(2,5)$, è $2,5,3,6,1,2$; i suoi archi all'indietro sono $(3,5)$, $(6,3)$.
Senza gli archi incidenti su $6$, il nodo $6$ è isolato e il grafo ha i componenti $k=2$ $\{1,2,3,4,5\}$, $\{6\}$; quindi il rango è $6-2=4$.

$\rank(\mat{B})=5$; $F_1$ è uno albero ricoprente, $F_2$ no, e le sue colonne soddisfano una relazione lineare data dal suo ciclo.

Esercizio 1.4: Ricerca in ampiezza

Esercizio

Consideriamo il grafo orientato $G=(N,A)$ con $N=\{1,2,\dots,7\}$ e gli archi $11$

\[ A=\{(1,4),(1,5),(2,1),(2,6),(3,1),(3,6),(5,3),(5,4),(5,7),(6,1),(7,6)\}, \]

disegnato qui sotto.

Figura 5

Domande

Scrivi le liste di adiacenza di $G$.
Esegui la ricerca in ampiezza da $s=1$: fornisci $\mathit{LIST}$ dopo ogni iterazione e l'ordine di etichettatura.
Disegna l'albero precedente e assegna, per ogni nodo etichettato $j$, il numero $d(j)$ di archi del percorso dell'albero da $1$ a $j$.
Quali nodi non sono raggiungibili da $1$? Fornire un percorso diretto con il numero minimo di archi da $1$ a $6$.

Soluzione

Usiamo le regole (G1)–(G5) del riquadro all'inizio di questi esercizi.

I successori di ciascun nodo, per indice crescente:

$i$ $L(i)$

$1$ $4,~5$

$2$ $1,~6$

$3$ $1,~6$

$4$ (vuoto)

$5$ $3,~4,~7$

$6$ $1$

$7$ $6$

La ricerca seleziona il primo nodo di $\mathit{LIST}$:

iterazione e $i$ selezionato e azione	$\mathit{LIST}$
$1$	$1$	etichetta $4$, $\mathit{pred}(4)=1$	$1,4$
$2$	$1$	etichetta $5$, $\mathit{pred}(5)=1$ ($4$ è etichettato)	$1,4,5$
$3$	$1$	rimuovi $1$ ($4$, $5$ sono etichettati)	$4,5$
$4$	$4$	rimuovi $4$	$5$
$5$	$5$	etichetta $3$, $\mathit{pred}(3)=5$	$5,3$
$6$	$5$	etichetta $7$, $\mathit{pred}(7)=5$ ($3$, $4$ sono etichettati)	$5,3,7$
$7$	$5$	rimuovi $5$ ($3$, $4$, $7$ sono etichettati)	$3,7$
$8$	$3$	etichetta $6$, $\mathit{pred}(6)=3$ ($1$ è etichettato)	$3,7,6$
$9$	$3$	rimuovi $3$ ($1$, $6$ sono etichettati)	$7,6$
$10$	$7$	rimuovi $7$ ($6$ è etichettato)	$6$
$11$	$6$	rimuovi $6$ ($1$ è etichettato)	(vuoto)

L'ordine di etichettatura è $1,4,5,3,7,6$.

Gli archi $(\mathit{pred}(j),j)$ sono $(1,4)$, $(1,5)$, $(5,3)$, $(5,7)$, $(3,6)$ (blu); accanto a ciascun nodo il valore $d(j)$:
Il nodo $2$ non è etichettato, quindi non è raggiungibile da $1$ per la correttezza della ricerca. Il BFS fornisce il numero minimo di archi: il percorso dell'albero $1,5,3,6$ ha archi $d(6)=3$ e nessun percorso diretto da $1$ a $6$ è più breve.

Il BFS etichetta i nodi nell'ordine $1,4,5,3,7,6$, in ordine non decrescente di $d$; $R(1)=\{1,3,4,5,6,7\}$.

Esercizio 1.5: Ricerca in profondità

Esercizio

Consideriamo il grafo orientato $G=(N,A)$ con $N=\{1,2,\dots,7\}$ e gli archi $11$

\[ A=\{(1,2),(1,5),(2,3),(2,7),(3,6),(3,7),(4,1),(4,3),(6,1),(6,2),(7,5)\}, \]

disegnato qui sotto.

Figura 7

Domande

Esegui la ricerca approfondita da $s=1$: fornisci $\mathit{LIST}$ dopo ogni iterazione e l'ordine di etichettatura.
Disegna l'albero precedente del DFS.
Confrontare il percorso da $1$ a $5$ nell'albero DFS con il numero minimo di archi da $1$ a $5$.

Soluzione

Usiamo le regole (G1)–(G5) del riquadro all'inizio di questi esercizi.

Gli elenchi di adiacenza sono $L(1)=\{2,5\}$, $L(2)=\{3,7\}$, $L(3)=\{6,7\}$, $L(4)=\{1,3\}$, $L(5)=\emptyset$, $L(6)=\{1,2\}$, $L(7)=\{5\}$. La ricerca seleziona l'ultimo nodo di $\mathit{LIST}$:

iterazione e $i$ selezionato e azione	$\mathit{LIST}$
$1$	$1$	etichetta $2$, $\mathit{pred}(2)=1$	$1,2$
$2$	$2$	etichetta $3$, $\mathit{pred}(3)=2$	$1,2,3$
$3$	$3$	etichetta $6$, $\mathit{pred}(6)=3$	$1,2,3,6$
$4$	$6$	rimuovi $6$ ($1$, $2$ sono etichettati)	$1,2,3$
$5$	$3$	etichetta $7$, $\mathit{pred}(7)=3$ ($6$ è etichettato)	$1,2,3,7$
$6$	$7$	etichetta $5$, $\mathit{pred}(5)=7$	$1,2,3,7,5$
$7$	$5$	rimuovi $5$	$1,2,3,7$
$8$	$7$	rimuovi $7$ ($5$ è etichettato)	$1,2,3$
$9$	$3$	rimuovi $3$ ($6$, $7$ sono etichettati)	$1,2$
$10$	$2$	rimuovi $2$ ($3$, $7$ sono etichettati)	$1$
$11$	$1$	rimuovi $1$ ($2$, $5$ sono etichettati)	(vuoto)

L'ordine di etichettatura è $1,2,3,6,7,5$.

Gli archi $(\mathit{pred}(j),j)$ sono $(1,2)$, $(2,3)$, $(3,6)$, $(3,7)$, $(7,5)$ (blu); accanto a ciascun nodo la sua posizione $o(j)$ nell'ordine di etichettatura:
L'albero DFS raggiunge $5$ lungo $1,2,3,7,5$, con archi $4$, mentre il BFS da $1$ dà $d(5)=1$: l'albero DFS non fornisce percorsi con il numero minimo di archi.

Il DFS etichetta gli stessi nodi del BFS, $R(1)=\{1,2,3,5,6,7\}$, ma nell'ordine $1,2,3,6,7,5$ e con un albero predecessore diverso.

\(i\)	\(L(i)\)
\(1\)	\(2,~3\)
\(2\)	\(3,~4\)
\(3\)	(vuoto)
\(4\)	(vuoto)
\(5\)	\(1,~3,~4\)

arco	\(a_{1}\)	\(a_{2}\)	\(a_{3}\)	\(a_{4}\)	\(a_{5}\)	\(a_{6}\)	\(a_{7}\)
coda	\(1\)	\(1\)	\(2\)	\(2\)	\(5\)	\(5\)	\(5\)
testa	\(2\)	\(3\)	\(3\)	\(4\)	\(1\)	\(3\)	\(4\)

nodo \(i\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
\(\deg^+(i)\)	\(2\)	\(2\)	\(0\)	\(0\)	\(3\)
\(\deg^-(i)\)	\(1\)	\(1\)	\(3\)	\(2\)	\(0\)

\(i\)	\(L(i)\)
\(1\)	\(4,~5\)
\(2\)	\(1,~6\)
\(3\)	\(1,~6\)
\(4\)	(vuoto)
\(5\)	\(3,~4,~7\)
\(6\)	\(1\)
\(7\)	\(6\)

iterazione e \(i\) selezionato e azione	\(\mathit{LIST}\)
\(1\)	\(1\)	etichetta \(4\), \(\mathit{pred}(4)=1\)	\(1,4\)
\(2\)	\(1\)	etichetta \(5\), \(\mathit{pred}(5)=1\) (\(4\) è etichettato)	\(1,4,5\)
\(3\)	\(1\)	rimuovi \(1\) (\(4\), \(5\) sono etichettati)	\(4,5\)
\(4\)	\(4\)	rimuovi \(4\)	\(5\)
\(5\)	\(5\)	etichetta \(3\), \(\mathit{pred}(3)=5\)	\(5,3\)
\(6\)	\(5\)	etichetta \(7\), \(\mathit{pred}(7)=5\) (\(3\), \(4\) sono etichettati)	\(5,3,7\)
\(7\)	\(5\)	rimuovi \(5\) (\(3\), \(4\), \(7\) sono etichettati)	\(3,7\)
\(8\)	\(3\)	etichetta \(6\), \(\mathit{pred}(6)=3\) (\(1\) è etichettato)	\(3,7,6\)
\(9\)	\(3\)	rimuovi \(3\) (\(1\), \(6\) sono etichettati)	\(7,6\)
\(10\)	\(7\)	rimuovi \(7\) (\(6\) è etichettato)	\(6\)
\(11\)	\(6\)	rimuovi \(6\) (\(1\) è etichettato)	(vuoto)

iterazione e \(i\) selezionato e azione	\(\mathit{LIST}\)
\(1\)	\(1\)	etichetta \(2\), \(\mathit{pred}(2)=1\)	\(1,2\)
\(2\)	\(2\)	etichetta \(3\), \(\mathit{pred}(3)=2\)	\(1,2,3\)
\(3\)	\(3\)	etichetta \(6\), \(\mathit{pred}(6)=3\)	\(1,2,3,6\)
\(4\)	\(6\)	rimuovi \(6\) (\(1\), \(2\) sono etichettati)	\(1,2,3\)
\(5\)	\(3\)	etichetta \(7\), \(\mathit{pred}(7)=3\) (\(6\) è etichettato)	\(1,2,3,7\)
\(6\)	\(7\)	etichetta \(5\), \(\mathit{pred}(5)=7\)	\(1,2,3,7,5\)
\(7\)	\(5\)	rimuovi \(5\)	\(1,2,3,7\)
\(8\)	\(7\)	rimuovi \(7\) (\(5\) è etichettato)	\(1,2,3\)
\(9\)	\(3\)	rimuovi \(3\) (\(6\), \(7\) sono etichettati)	\(1,2\)
\(10\)	\(2\)	rimuovi \(2\) (\(3\), \(7\) sono etichettati)	\(1\)
\(11\)	\(1\)	rimuovi \(1\) (\(2\), \(5\) sono etichettati)	(vuoto)