Grafi - definizioni e proprietà

Un grafo $G = (V, E)$ ha un insieme $V$ di vertici (o nodi) e una collezione $E$ di archi (coppie di vertici). È diretto se ogni arco $(u, v)$ è una coppia ordinata ($u \to v$), non diretto se la coppia è non ordinata ($u - v$). $E$ è una collezione e non un insieme perché si ammettono archi multipli tra due vertici; un self loop è un arco $(u, u)$. Un grafo semplice non ha archi multipli né self loop; un grafo pesato associa pesi a archi e/o vertici.

In questo corso si studiano grafi semplici e non diretti (i grafi diretti sono in Grafi diretti e ordinamento topologicoGrafi diretti (archi orientati, grado entrante e uscente, cammini e cicli diretti), visite su grafi diretti e tipi di archi; DAG; ordinamento topologico con l'algoritmo basato sui gradi entranti e con la DFS (reverse postorder), correttezza e costo Theta(n+m); esempio svolto.Grafi diretti e ordinamento topologico →). Esempi: reti sociali, reti stradali, reti di comunicazione (Internet, P2P), web graph, reti biologiche (interazioni tra proteine), molecole, reti di sensori. Il numero di vertici si indica con $n$ e quello degli archi con $m$.

Terminologia

• Un arco $e = (u, v)$ è incidente su $u$ e $v$, che sono adiacenti; i vicini di $v$ sono i vertici $u$ con $(v, u) \in E$.
• Il grado $\text{degree}(v)$ è il numero di archi incidenti su $v$. Un vertice di grado $0$ è isolato.
• Un cammino è una sequenza di vertici $u_1, \dots, u_k$ con $(u_i, u_{i+1}) \in E$; la lunghezza è il numero di archi, $k - 1$ (nei grafi pesati, la somma dei pesi). Un ciclo è un cammino con $u_k = u_1$; è semplice se i vertici sono tutti distinti (a parte primo e ultimo).
• Un sottografo $G' = (V', E')$ ha $V' \subseteq V$, $E' \subseteq E$ e gli archi di $E'$ incidono solo su $V'$. È di copertura (spanning) se $V' = V$.
• $G$ è connesso se per ogni coppia $u, v$ esiste un cammino da $u$ a $v$; altrimenti è disconnesso.
• Le componenti connesse sono una partizione di $G$ in sottografi $G_1, \dots, G_k$ ($G_i = (V_i, E_i)$) con: ogni $G_i$ connesso; $V = V_1 \cup \dots \cup V_k$ e $E = E_1 \cup \dots \cup E_k$ (partizioni); nessun arco tra $V_i$ e $V_j$ per $i \ne j$. Sono i sottografi connessi massimali; la partizione è unica; $G$ connesso $\Leftrightarrow$ $k = 1$. Esempio: vertici $u, v, w, x, y, z$ con archi $uv$, $xy$, $yw$, $wx$ hanno tre componenti: $\{u, v\}$ con 1 arco, $\{x, y, w\}$ con 3 archi, $\{z\}$ senza archi.

Alberi, foreste, spanning tree

• Un albero radicato è un grafo con un vertice radice $r$, un unico padre $p(u)$ per ogni $u \ne r$, $E = \{(u, p(u))\}$ e radice raggiungibile risalendo da ogni vertice (vedi AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).Alberi →).
• Un albero libero è un grafo connesso e senza cicli semplici. Ogni albero radicato è un albero libero; ogni albero libero diventa radicato scegliendo una radice e orientando i legami padre-figlio di conseguenza.
• Una foresta è un grafo senza cicli: un insieme di alberi liberi disgiunti.
• Uno spanning tree di $G$ è un sottografo di copertura connesso e senza cicli (un albero libero); esiste solo se $G$ è connesso. Una spanning forest è un sottografo di copertura senza cicli: ha un albero per ogni componente connessa.

Proprietà

Sia $G$ non diretto e semplice con $n$ vertici e $m$ archi.

P1. $\sum_{v \in V} \text{degree}(v) = 2m$. Dimostrazione: ogni arco è contato esattamente due volte, una per estremo.

P2. $m \le \binom{n}{2} = \frac{n(n-1)}{2}$, quindi $m \in O(n^2)$. Dimostrazione: $G$ è semplice, perciò $E$ è un sottoinsieme delle coppie non ordinate di vertici distinti.

P3. Se $G$ è un albero, $m = n - 1$. Dimostrazione: si vede $G$ come albero radicato; $E$ coincide con le relazioni padre-figlio, che sono $n - 1$ (ogni vertice non radice ha un solo padre).

P4. Se $G$ è connesso, $m \ge n - 1$. Dimostrazione: finché esiste un ciclo si elimina un suo arco: $G$ resta connesso. Alla fine è connesso e senza cicli, cioè un albero libero con $m' = n - 1 \le m$ archi.

P5. Se $G$ è una foresta, $m \le n - 1$. Dimostrazione: finché $G$ non è connesso si aggiunge un arco tra due componenti diverse $G_1, G_2$: non può creare cicli. Alla fine $G$ è un albero con $m' = n - 1 \ge m$ archi.

Corollario (spanning forest). Un grafo con $k$ componenti connesse di $n_1, \dots, n_k$ vertici ha spanning forest con $\sum (n_i - 1) = n - k$ archi (ogni componente contribuisce con uno spanning tree di $n_i - 1$ archi, per P3). Esempio d'esame: $n_1 = 5$, $m_1 = 10$; $n_2 = 6$, $m_2 = 15$; $n_3 = 8$, $m_3 = 8$: il numero massimo di archi in una spanning forest è $(5-1) + (6-1) + (8-1) = 16$, indipendentemente dai valori $m_i$ (le prime due componenti sono grafi completi $K_5$ e $K_6$, la terza ha $8$ archi su $8$ vertici e quindi contiene almeno un ciclo). Ogni spanning forest che non si può più estendere ha esattamente $n - k$ archi.

Problemi tipici su grafi

Visita (traversal) e crawling, connettività, componenti connesse, cammini minimi (navigatore), minimum spanning tree (broadcast efficiente), stima di distanza media/massima (social network). 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 →, Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra → e Minimum spanning treeMinimum spanning tree di un grafo pesato connesso; proprietà del taglio (cut property) con dimostrazione; algoritmo di Kruskal con partizioni (union-find) e algoritmo di Prim con coda con priorità; esempio svolto sullo stesso grafo di Dijkstra; complessità O(m log n).Minimum spanning tree →.

Errori comuni

• Applicare $m = n - 1$ a un grafo connesso qualsiasi: è vero solo per gli alberi; per i connessi vale $m \ge n - 1$.
• Contare $n - 1$ archi nella spanning forest di un grafo non connesso: sono $n - k$ con $k$ componenti.
• Dimenticare che un grafo con un vertice isolato è disconnesso (se $n \ge 2$).
• Confondere lunghezza del cammino (archi) con numero di vertici ($k$).