Paola Festa » 17.Richiami di Teoria dei Grafi: definizioni e notazioni

Introduzione

Gli alberi e le reti sono particolari grafi.
Dal momento che gli alberi, le reti ed i grafi sono strutture dati fondamentali per lo studio della maggior parte dei problemi di ottimizzazione combinatoria, in quanto segue saranno brevemente richiamate alcune definizioni dalla teoria dei grafi ed alcune proprietà dei grafi che risulteranno utili ai fini della comprensione delle prossime lezioni.

Grafi non orientati, 1

Un grafo non orientato è una coppia G=(V,E), in cui

V è un insieme finito di n elementi detti nodi o vertici del grafo. Tipicamente, l’insieme dei nodi V viene rappresentato come V={1,…,n};
E è una famiglia di m coppie non ordinate di elementi di V (dunque, anche E è un insieme finito). Gli elementi di E sono chiamati archi del grafo e tipicamente sono rappresentati come [i,j], i,j=1,…,n.

Dal momento che G non è orientato, E è un insieme di coppie non ordinate, per cui [i,j]=[j,i], i,j=1,…,n.
Se [i,j] e [j,i] sono entrambi elementi di E, si parla di arco multiplo o parallelo e grafi senza archi multipli sono detti grafi semplici.
Archi del tipo [i,i], i=1,…,n, sono detti self-loops o cappi e generalmente nei problemi di ottimizzazione che studieremo la loro presenza non sarà consentita.

Grafi non orientati, 2

Si definisce grado di un nodo i=1,…,n e si indica con deg(i) il numero di archi incidenti in i.
Se deg(i)=0, allora il nodo i si dice isolato; se, invece, deg(i)=1, allora i è detto pendente.
E’ banale osservare che
$\mbox{DEG}=\displaystyle{\sum_{i\in V}\deg(i)=2\cdot\vert E\vert},$
per cui DEG è sempre un numero pari.

Per ogni nodo i=1,…,n definiamo il seguente insieme
$\mbox{star}(i)=\{j\in V\ \vert\ [i,j]\in E\}$
e risulta che $\vert\mbox{star}(i)\vert=\deg(i)$ .

In quanto segue, si considereranno già note le definizioni di grafo non orientato completo, grafo non orientato connesso, cammino e ciclo in un grafo non orientato.

Grafi non orientati, 3

Dato un sottoinsieme S di V, si definisce taglio di G rispetto ad S il seguente sottoinsieme di E:
$\delta_G(S)=\{[i,j]\in E\ \vert\ i\in S,\ j\in V\setminus S\}.$

Un grafo G=(V,E) si dice bipartito, se esiste una partizione (V1,V2) di V tale che ogni arco [i,j] in E collega i in V1 a j in V2.

Un grafo senza cicli è detto aciclico.

Un grafo aciclico e connesso è detto albero ed è di solito indicato con T=(V,E).
I nodi di un albero T che hanno grado uguale ad 1 sono detti foglie di T.

Un grafo aciclico e non connesso è detto foresta.

Esempio di grafo bipartito. Disegnata da Paola Festa

Grafi non orientati, 4

Alcune proprietà degli alberi:
→ ogni albero con più di un nodo ha almeno una foglia;
→ un grafo non orientato G=(V,E) è un albero sse G è connesso ed ha |V|-1 archi;
→ per ogni coppia di nodi i e j di un albero, esiste un unico cammino che li collega;
→ se si aggiunge un arco ad un albero, il grafo risultante contiene esattamente un ciclo.

Dato un grafo non orientato e connesso G=(V,E), sia E’ un sottoinsieme non proprio di E tale che T=(V,E’) sia un albero, allora T è detto albero ricoprente G o spanning tree di G.

Grafi orientati, 1

Un grafo orientato è una coppia G=(V,A), in cui
V è un insieme finito di n elementi detti nodi o vertici del grafo. Tipicamente, l’insieme dei nodi V viene rappresentato come V={1,…,n};
A è una famiglia di m coppie ordinate di elementi di V (dunque, anche E è un insieme finito). Gli elementi di A sono chiamati archi del grafo e tipicamente sono rappresentati come (i,j), i,j=1,…,n.
Dal momento che G è orientato, A è un insieme di coppie ordinate, per cui (i,j) è diverso da (j,i), i,j=1,…,n.

Molte definizioni date per i grafi non orientati si estendono anche ai grafi orientati. Si parla, dunque, di grafi orientati semplici, di self-loops, di cammini orientati, di cicli orientati Euleriani ed Hamiltoniani, eccetera.
La presenza di self-loops o cappi generalmente nei problemi di ottimizzazione che studieremo non sarà consentita.

Esempio di grafo orientato. Disegnata da Paola Festa

Grafi orientati, 2

Per ogni nodo i in V definiamo i seguenti insiemi:
$FS(i)=\{j\in V\ \vert\ (i,j)\in A\}$ , detto stella uscente di i;
$BS(i)=\{j\in V\ \vert\ (j,i)\in A\}$ , detto stella entrante di i.

Si definisce grado entrante del nodo i e si indica con indeg(i) il numero di archi entranti in i (i.e. |BS(i)|).
Si definisce grado uscente del nodo i e si indica con outdeg(i) il numero di archi uscenti da i (i.e. |FS(i)|).
Si definisce grado del nodo i, la quantità deg(i)=indeg(i)+ outdeg(i).

Grafi orientati, 3

Dato un sottoinsieme S di V, si definiscono taglio positivo di G rispetto ad S e taglio negativo di G rispetto ad S i seguenti sottoinsiemi di A:
$\delta^+_G(S)=\{(i,j)\in A\ \vert\ i\in S,\ j\in V\setminus S\}. \] \[ \delta^-_G(S)=\{(i,j)\in A\ \vert\ i\in V\setminus S,\ j\in S\}.$
Facendo riferimento alla Figura, ad esempio si ha
$\delta^+_G(\{1,2,3\})=\{(1,4),(2,5)\}, \] \[ \delta^-_G(\{1,2,3\})=\{(4,3),(4,2)\}, \] \[ \delta^+_G(\{6\})=\delta^-_G(\{6\})=\emptyset.$
Si noti che $\delta^+_G(S)=\delta^-_G(V\setminus S)$ .