Esercizio 21visita BFS e spanning forest

---

Parte A

Si applica la BFS (vedi Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →): si parte da $A$ e si visitano per livelli, esaminando per ogni vertice i vicini nell'ordine della lista.

Ordine di visita BFS: $A, B, C, D, E, F, G, H, I$.

Traccia completa (si esaminano i vertici nell'ordine di scoperta; ogni arco compare due volte, una per estremo, ma è etichettato la prima volta):

Gli archi del grafo sono $9$ (somma delle lunghezze delle liste $=18=2m$), $8$ nell'albero e $1$ cross.

Il BFS tree (archi discovery) è: $AB, AC, AD, BE, BF, CG, DH, FI$ (8 archi $= n - 1$ con $n = 9$, il grafo è connesso); gli archi cross sono $HI$ (entrambi estremi già visitati quando $H$ esamina $I$: $I$ era già stato scoperto da $F$). I livelli coincidono con le distanze da $A$: $d(A, I) = 3$ (cammino $A, B, F, I$). Per confronto, una DFS dallo stesso vertice con lo stesso ordine delle liste visita $A, B, E, F, I, H, D, C, G$ (scende in profondità prima di tornare indietro). (Entrambi gli ordini verificati eseguendo il codice.)

Parte B

(a) Definizione. Una spanning forest di $G$ è un sottografo di copertura di $G$ (contiene tutti i vertici di $V$) senza cicli (vedi Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →): una foresta di alberi liberi disgiunti, uno per ciascuna componente connessa (se è massimale).

(b) Massimo numero di archi. Una spanning forest ha al più un albero per ciascuna componente connessa. Un albero su $n_i$ vertici ha $n_i - 1$ archi (vedi la proprietà $m = n - 1$ per gli alberi), e per ciascuna componente connessa esiste uno spanning tree. Quindi il massimo numero di archi è

$$\sum_{i=1}^{3} (n_i - 1) = (5 - 1) + (6 - 1) + (8 - 1) = 4 + 5 + 7 = \mathbf{16} = n - k,$$

con $n = 19$ vertici e $k = 3$ componenti ($5+6+8=19$). Perché $n_i-1$ per componente: uno spanning tree di un grafo connesso con $n_i$ vertici è un albero libero, che ha $n_i-1$ archi (Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →, proprietà P3). I valori $m_i$ sono ridondanti: servono solo a controllare che le componenti siano possibili ($m_i \le \binom{n_i}{2}$: $10 = \binom52$, $15 = \binom62$, $8 \le \binom82=28$; Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali →) e connesse ($m_i \ge n_i - 1$). Più di $n - k$ archi creerebbe un ciclo (in una foresta $m \le n - k$).

Errori comuni

• Visitare i vicini in ordine alfabetico invece che nell'ordine delle liste: qui coincidono, ma in generale conta la lista.
• Confondere BFS e DFS: la BFS esaurisce un livello prima del successivo ($B, C, D$ prima di $E$).
• Rispondere $n - 1 = 18$ nel punto B: vale solo per grafi connessi; con $3$ componenti è $n - 3$.
• Rispondere $m_1 + m_2 + m_3$ o contare tutti gli archi: una spanning forest non può contenere cicli.