Grafi - definizioni e proprietà

In questa pagina 5

Definizione (grafo). 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 (Insiemi e insieme delle parti, Operazioni tra insiemi) 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.

Esempio. Il grafo non diretto con $V=\{1,2,3\}$ e $E=\{(1,2),(2,3)\}$ ha $n=3$ vertici e $m=2$ archi.

In questo corso si studiano grafi semplici e non diretti (i grafi diretti sono in 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$ . Gli stessi oggetti compaiono in altre materie: il grafo di un circuito elettrico ha come vertici i nodi e come archi i bipoli (Grafo di una rete ed equazioni indipendenti; lì un albero di copertura serve a contare le equazioni di Kirchhoff indipendenti, $n-1$ per i nodi, in accordo con $m=n-1$ degli alberi più sotto), e la rete Internet è un grafo di router e collegamenti (Tipi di rete e topologie, Instradamento e inoltro).

Terminologia

Definizione (grado, cammino e componenti connesse)

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. Gradi: $u,v$ hanno grado $1$ ; $x,y,w$ hanno grado $2$ ciascuno (ognuno è su due archi del triangolo $x,y,w$ ); $z$ ha grado $0$ . Somma dei gradi $1+1+2+2+2+0=8=2\cdot4$ , con $m=4$ archi.

Esempio. Con $V=\{1,2,3,4\}$ e archi $(1,2),(2,3)$ : $\text{degree}(2)=2$ , il vertice $4$ è isolato e il grafo ha $2$ componenti connesse, $\{1,2,3\}$ e $\{4\}$ .

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

Proprietà (gradi, numero di archi e alberi). P1. $\sum_{v \in V} \text{degree}(v) = 2m$ . Dimostrazione: ogni arco è contato esattamente due volte, una per estremo (nella somma $\sum_v\text{degree}(v)$ l'arco $(u,v)$ compare una volta nel grado di $u$ e una volta in quello di $v$ ). Conseguenza: la somma dei gradi è pari, quindi il numero di vertici di grado dispari è pari (se ne avessi un numero dispari la somma sarebbe dispari).

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. Tali coppie sono $\binom n2=\frac{n(n-1)}{2}$ : si scelgono $2$ vertici su $n$ senza badare all'ordine (Fattoriale e coefficienti binomiali); equivalentemente, ogni vertice può essere unito a $n-1$ altri, e ogni coppia è stata contata due volte, da cui il fattore $\frac12$ . Con $n=5$ sono $10$ , con $n=6$ sono $15$ (grafi completi $K_5$ , $K_6$ ).

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, perché ogni cammino che usava quell'arco si può rifare percorrendo il resto del ciclo (il ciclo offre un percorso alternativo tra gli estremi dell'arco). 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, perché un ciclo che passasse per il nuovo arco $(a,b)$ richiederebbe un altro cammino da $a$ a $b$ , ma $a$ e $b$ stanno in componenti diverse e quindi non ce n'è nessuno. Alla fine $G$ è un albero con $m' = n - 1 \ge m$ archi.

Esempio. Con $n=5$ vertici si ha $m\le5\cdot4/2=10$ ; un albero libero ha $m=4$ archi e la somma dei gradi è $2m=8$ .

Il grafico riassume le proprietà P2, P3 e P4: un grafo semplice e connesso con $n$ vertici ha un numero di archi tra $n-1$ (alberi) e $\frac{n(n-1)}{2}$ (grafo completo). Un grafo è sparso se $m$ è vicino a $n$ e denso se è vicino a $n^2$ : la distinzione guida la scelta della rappresentazione (Rappresentazione dei grafi).

Grafico interattivo: Numero di archi di un grafo semplice connesso con n vertici: da n − 1 (albero) a n(n−1)/2 (grafo completo); a n = 20 sono 19 contro 190

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.

Esempio. Con componenti di $5$ , $6$ e $8$ vertici lo spanning forest ha $(5-1)+(6-1)+(8-1)=16=19-3$ 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 DFS, Cammini minimi e algoritmo di Dijkstra e 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$ ).

Versione ripasso

Grafo $G=(V,E)$ : diretto (coppie ordinate) o non diretto. $E$ è una collezione perché ammette archi multipli; un self loop è un arco $(u,u)$ . Semplice = niente archi multipli né self loop. Qui si studiano grafi semplici non diretti, con $n=\lvert V\rvert$ e $m=\lvert E\rvert$ (per i diretti vedi Grafi diretti e ordinamento topologico).
Termini: arco incidente su $u,v$ ; $u,v$ adiacenti; grado = numero di archi incidenti; vertice isolato = grado $0$ . Cammino $u_1,\dots,u_k$ , di lunghezza $k-1$ (somma dei pesi nei grafi pesati); ciclo con $u_k=u_1$ , semplice se i vertici sono distinti.
Sottografo $G'=(V',E')$ con $V'\subseteq V$ ed $E'\subseteq E$ ; di copertura se $V'=V$ . $G$ è connesso se ogni coppia di vertici è collegata da un cammino.
Componenti connesse: partizione unica in sottografi connessi massimali, senza archi tra componenti diverse. $G$ connesso $\Leftrightarrow k=1$ .
Esempio: archi $uv$ , $xy$ , $yw$ , $wx$ e vertice $z$ isolato: $3$ componenti, $\{u,v\}$ ( $1$ arco), $\{x,y,w\}$ ( $3$ archi), $\{z\}$ ( $0$ ). Gradi $1,1,2,2,2,0$ , somma $8=2\cdot4$ .
Alberi: albero libero = connesso e senza cicli semplici; ogni albero radicato lo è, e ogni albero libero diventa radicato scegliendo una radice (vedi Alberi). Foresta = grafo senza cicli, cioè insieme di alberi liberi disgiunti.
Spanning tree: sottografo di copertura connesso e senza cicli; esiste solo se $G$ è connesso. Spanning forest: sottografo di copertura senza cicli, con un albero per componente.
P1 $\sum_v \text{degree}(v) = 2m$ : ogni arco è contato due volte; quindi il numero di vertici di grado dispari è pari.
P2 $m \le \binom n2 = \frac{n(n-1)}{2}$ , quindi $m\in O(n^2)$ : le coppie di vertici distinti sono $\binom n2$ (con $n=5$ sono $10$ , con $n=6$ sono $15$ ).
P3 albero: $m=n-1$ , perché ogni vertice non radice ha un solo padre.
P4 connesso: $m\ge n-1$ : si tolgono archi dai cicli finché non ce ne sono più, e si ottiene un albero con $n-1$ archi.
P5 foresta: $m\le n-1$ : si aggiungono archi tra componenti diverse senza creare cicli, fino a ottenere un albero.
Corollario (spanning forest): con $k$ componenti di $n_1,\dots,n_k$ vertici, la spanning forest ha $\sum(n_i-1)=n-k$ archi. Esempio $n_i=5,6,8$ : $4+5+7=16$ , indipendentemente dagli archi delle componenti.
Densi e sparsi: $m$ vicino a $n$ oppure a $n^2$ ; questa distinzione guida la scelta della rappresentazione (vedi Rappresentazione dei grafi).
Problemi tipici: visita, connettività, componenti, cammini minimi, minimum spanning tree (vedi Visite di grafi - BFS e DFS, Cammini minimi e algoritmo di Dijkstra, Minimum spanning tree).
Errori tipici: $m=n-1$ per ogni grafo connesso (vale solo per gli alberi); $n-1$ archi per la spanning forest di un grafo sconnesso (sono $n-k$ con $k$ componenti); un vertice isolato rende disconnesso il grafo con $n\ge2$ ; lunghezza del cammino contata in vertici.