1.1 Grafi non orientati e orientati

Parte 1 · Grafi · Capitolo 1 · Capitolo 1: Grafi · Dispensa, volume 1 (PDF) · Esercizi: Grafi · App: Ricerca su grafo: BFS e DFS

Definizione 1.1: grafo non orientato

Un grafo non orientato \(G=(V,E)\) è formato da un insieme finito \(V\) di vertici e da un insieme \(E\) di lati, ciascuno dei quali è un sottoinsieme di \(V\) con due elementi:

\[ E \subseteq \big\{\, \{u,v\} : u,v \in V,~ u \neq v \,\big\}. \]

Scriviamo \(n=|V|\) e \(m=|E|\) e i vertici sono etichettati \(1,2,\dots,n\).

• I vertici \(u\) e \(v\) sono gli estremi del lato \(\{u,v\}\). Il lato è incidente a \(u\) e a \(v\); di conseguenza, \(u\) e \(v\) sono adiacenti.

• L'intorno di \(v\) è \(N(v)=\{\, u \in V : \{u,v\} \in E \,\}\); l'insieme dei lati incidenti a \(v\) è \(\delta(v)=\{\, \{u,v\} \in E : u \in V \,\}\) e il grado di \(v\) è \(\deg(v)=|\delta(v)|\).

Esempio 1.1: un grafo non orientato

Consideriamo il grafo \(G=(V,E)\) con \(n=6\) vertici e \(m=9\) lati:

\[ V=\{1,2,3,4,5,6\}, \qquad E=\big\{\{1,2\},\{1,3\},\{2,3\},\{2,4\},\{3,4\},\{3,5\},\{4,5\},\{4,6\},\{5,6\}\big\}. \]

L'intorno del vertice \(3\) è \(N(3)=\{1,2,4,5\}\), quindi \(\deg(3)=4\). I gradi dei sei vertici sono

\[ \deg(1)=2,\quad \deg(2)=3,\quad \deg(3)=4,\quad \deg(4)=4,\quad \deg(5)=3,\quad \deg(6)=2. \]

Proposizione 1.2: lemma della stretta di mano

Per ogni grafo non orientato \(G=(V,E)\) abbiamo

\[ \sum_{v \in V} \deg(v) = 2\,m . \]

Dimostrazione

La somma conta le coppie \((v,e)\) con \(v \in V\), \(e \in \delta(v)\). Ogni lato \(e=\{u,v\}\) appare esattamente in due coppie, \((u,e)\) e \((v,e)\), quindi il numero di coppie è \(2m\). □

• In Esempio 1.1 la somma dei gradi dà \(2+3+4+4+3+2=18=2\cdot 9\).

Definizione 1.3: grafo diretto

Un grafo orientato \(G=(N,A)\) è dato da un insieme finito \(N\) di nodi e un insieme \(A\) di archi, ogni arco essendo una coppia ordinata di nodi distinti:

\[ A \subseteq \big\{\, (i,j) : i,j \in N,~ i \neq j \,\big\}. \]

Scriviamo \(n=|N|\) e \(m=|A|\) e i nodi sono etichettati \(1,2,\dots,n\).

• L'arco \((i,j)\) va dalla sua coda \(i\) alla sua testa \(j\); \(j\) è un successore di \(i\) e \(i\) è un predecessore di \(j\).

• La stella uscente \(\delta^+(i)=\{\,(i,j) \in A\,\}\) contiene gli archi uscenti da \(i\); la stella entrante \(\delta^-(i)=\{\,(j,i) \in A\,\}\) contiene gli archi entranti in \(i\).

• Il grado uscente di \(i\) è \(\deg^+(i)=|\delta^+(i)|\) e il grado entrante è \(\deg^-(i)=|\delta^-(i)|\).

• Gli archi \((i,j)\) e \((j,i)\) sono diversi: si chiamano antiparallelo e possono appartenere entrambi a \(A\).

• Il grafo non orientato sottostante di \(G=(N,A)\) ha il lato \(\{i,j\}\) per ogni arco \((i,j)\) o \((j,i)\) di \(A\): si ottiene ignorando l'orientamento degli archi.

Esempio 1.2: il grafo di riferimento

Consideriamo il grafo diretto \(G=(N,A)\) con nodi \(n=6\) e archi \(m=9\):

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

Gli archi sono numerati \(a_1,a_2,\dots,a_9\) in questo ordine (lessicografo), come in figura.

I gradi uscenti e quelli entranti sono:

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

Il grafo non orientato sottostante è il grafo di Esempio 1.1. Chiameremo questo grafo il grafo di riferimento: tutti gli esempi del capitolo lo utilizzano.

• Ogni arco ha una coda e una testa, quindi \(\sum_{i \in N} \deg^+(i) = \sum_{i \in N} \deg^-(i) = m\). Nel grafo di riferimento entrambe le somme sono \(9\).

1.1.1 Passeggiate, percorsi e cicli

Definizione 1.4: passeggiata, cammino e ciclo

Sia \(G=(V,E)\) un grafo non orientato.

• Una passeggiata da \(v_0\) a \(v_k\) è una sequenza \(v_0, e_1, v_1, e_2, \dots, e_k, v_k\) di vertici e lati con \(e_t=\{v_{t-1},v_t\} \in E\) per tutti i \(t \in \{1,2,\dots,k\}\); la sua lunghezza è \(k\).

• La passeggiata è chiusa se \(v_0=v_k\). È un cammino semplice se i vertici \(v_0,v_1,\dots,v_k\) sono distinti.

• Un ciclo è una passeggiata chiusa con \(k \ge 3\) i cui vertici \(v_0,v_1,\dots,v_{k-1}\) sono distinti.

Un grafo senza cicli è aciclico. In un grafo semplice una passeggiata è identificata dai suoi vertici \(v_0,v_1,\dots,v_k\).

Definizione 1.5: passeggiata, cammino e ciclo diretto

Sia \(G=(N,A)\) un grafo diretto.

• Una passeggiata diretta da \(i_0\) a \(i_k\) è una sequenza di nodi \(i_0,i_1,\dots,i_k\) con \((i_{t-1},i_t) \in A\) per tutti gli \(t \in \{1,2,\dots,k\}\): ogni arco viene percorso dalla coda alla testa.

• È un cammino semplice diretto se i suoi nodi sono distinti, e un ciclo diretto se \(k \ge 2\), \(i_0=i_k\) e i nodi \(i_0,i_1,\dots,i_{k-1}\) sono distinti.

• Una passeggiata, un cammino semplice o un ciclo del grafo non orientato sottostante è rispettivamente una passeggiata, un cammino semplice o un ciclo di \(G\): gli archi possono essere attraversati in entrambe le direzioni. Un arco è percorso in avanti se si va dalla coda alla testa e all'indietro altrimenti.

Esempio 1.3: passeggiate, percorsi e cicli nel grafo di riferimento

Nel grafo di riferimento:

• \(1,3,2,4,3,5\) è una passeggiata diretta di lunghezza \(5\); non è un cammino semplice perché il nodo \(3\) compare due volte;

• \(1,3,5,6\) è un cammino semplice diretto di lunghezza \(3\) (in blu nella figura);

• \(2,4,3,2\) è un ciclo diretto di lunghezza \(3\) (rosso in figura);

• \(1,2,3\) è un cammino semplice del grafo sottostante, ma non un cammino diretto: l'arco \((1,2)\) è percorso in avanti e \((3,2)\) all'indietro.

Lemma 1.6: ogni passeggiata contiene un cammino semplice

Se in un grafo esiste una passeggiata (diretta) da \(u\) a \(v\), allora esiste anche un cammino semplice (diretto) da \(u\) a \(v\), i cui vertici appartengono alla passeggiata.

Dimostrazione

Tra i cammini da \(u\) a \(v\) che utilizzano solo i vertici del cammino dato, sia \(v_0,v_1,\dots,v_k\) uno dei minimi lunghezza. Se due gli indici \(s<t\) avevano \(v_s=v_t\), l'eliminazione di \(v_{s+1},\dots,v_t\) darebbe il cammino \(v_0,\dots,v_s,v_{t+1},\dots,v_k\) da Da \(u\) a \(v\), più corto di \(t-s \ge 1\). Quindi i vertici sono distinti e la passeggiata è un percorso. Vale lo stesso argomento per passeggiate guidate, poiché la cancellazione mantiene ogni arco percorso dalla coda alla testa. □

• In Esempio 1.3, eliminando il pezzo chiuso \(3,2,4,3\) dalla passeggiata \(1,3,2,4,3,5\) esce il percorso diretto \(1,3,5\).

1.1.2 Grafi semplici e multigrafi

• Un grafo è semplice se non ha cappi (lati \(\{v,v\}\) o archi \((i,i)\)) né lati o archi paralleli (due copie della stessa coppia). I grafi di Definizioni 1.1 e Definizione 1.3 sono semplici, perché \(E\) e \(A\) sono insiemi di coppie di elementi distinti.

• Un multigrafo ammette cappi e lati o archi paralleli. In questo modulo tutti i grafi sono semplici e ogni arco è identificato dalla coppia \((i,j)\) formata dalla sua coda e dalla sua testa.

Un grafo non orientato \(G=(V,E)\) ha lati \(\{u,v\}\); un grafo diretto \(G=(N,A)\) ha archi \((i,j)\) dalla coda \(i\) a la testa \(j\). Un percorso ha vertici distinti e ogni passeggiata contiene un percorso con gli stessi punti finali.

---

Avanti: 1.2 Rappresentazioni di un grafo