G-158

I grafi sono un mezzo per rappresentare relazioni binarie.

Teoria dei GrafiConcetti fondamentali

Ad esempio:• due città connesse da una strada• due calcolatori connessi in una rete telematica• due persone legate da una relazione di parentela (come, padre-

figlio)• due persone che condividono una stanza• il collegamento tra due componenti elettronici• un’operazione che deve essere eseguita da una certa macchina• ...

I grafi possono essere usati come strumento per modellare in manieraschematica un vastissimo numero di problemi decisionali.

Ad esempio:• determinare il percorso più breve che connette due città• determinare come connettere nella maniera più economica (più

efficiente) un insieme di calcolatori in una rete telematica• assegnare un insieme di operazioni ad un insieme di macchine• determinare il percorso più conveniente da far percorrere ad una

flotta di veicoli commerciali per effettuare delle consegne equindi rientrare al deposito

• ...

G-159

Argomenti trattati

• Definizioni fondamentali

• Problema dell’albero ricoprente (Spanning Tree)

• Problema del percorso minimo (Shortest Path)

• Formulazione di alcuni problemi con i grafi come problemi PLI

Definizioni fondamentali

Grafo non orientato

Un grafo non orientato G=(V,E) è dato da una coppia di insiemi finiti:

l V={v1,...,vm} l’insieme degli m Nodi di G

l E={e1,..,en}⊆VxV l’insieme degli n Archi non orientati di G

Ogni arco non orientato di G corrisponde ad una coppia non ordinata

di nodi di G ek=(vi,vj).

La presenza di un arco tra una coppia di nodi indica una relazione tra i

nodi stessi.

G-160

Un esempio: G=(V,E)

v1

v5

v3

v2

v4

e1

e2

e3

e4

e5

e6

e7

{ }V v v v v v= 1 2 3 4 5, , , , { }E e e e e e e e= 1 2 3 4 5 6 7, , , , , ,

( ) ( )e v v e v v1 1 5 2 1 2= =, , L

Definizioni di base:

• un arco (v,v) è detto loop

• due nodi u,v∈V sono detti adiacenti ⇔ (u,v)∈E

• due archi e,f∈E sono detti adiacenti ⇔ e=(v,w) ed f=(v,u)

• un arco f=(u,v)∈E si dice incidente su u e su v

• l’insieme di nodi N(v)={z∈V: z adiacente a v} è detto intorno di v

in G

• l’insieme di archi δ(v)={e∈E: e incide su v} è detto stella di v in G

• δ(v) è detto grado del nodo v

G-161

Grafi e Sottografi

• H=(W,F) è detto sottografo di G=(V,E) ⇔ W⊆V e F⊆E

• H=(W,F) è detto sottografo indotto da W in G=(V,E) ⇔ W⊆V e

(u,v)∈F implica che u,v∈W e (u,v)∈E

Esempio

v1

v5

v3

v2

e1

e2

sottografo di G

v1

v5

v3

v2

e1

e2

e3e6

sottografo indotto di G

v1

v5

v3

v2

v4

e1

e2

e3

e4

e5

e6

e7G=(V,E)

G-162

• G è detto completo ⇔ contiene tutti i possibili archi, ovvero

δ(v)=m-1 ∀v∈V

• il massimo numero di archi di un grafo completo è dato da

• G è detto grafo bipartito se esiste una partizione di V=V1∪V2 tale

che:

– V1∩V2=∅

– ∀e=(u,v)∈E se u∈V1 allora v∈V2 oppure se u∈V2 allora v∈V1

Esempio

m m m2

12

=

−( )

grafo completo

grafo non bipartitografo bipartito

Esempio

Grafi bipartiti e grafi completi

G-163

• w+(v)={e∈E: e uscente da v} è detto stella uscente di v

• w-(v)={e∈E: e entrante in v} è detto stella entrante di v

• w(v)= w+(v)∪w-(v) è detto stella di v

• le definizioni di sottografo e sottografo indotto di un grafo orientato

sono analoghe a quelle date per i grafi non orientati

• G=(V,E) è detto orientato se, dato V={v1,...,vm}, l’insieme degli

archi E={e1,..,en} è formato da coppie ordinate di nodi.

Per un grafo orientato si ha che ei=(vk,vh)≠ej=(vh,vk) ei,ej∈E

Esempio

Grafi orientati

vh vkeiCoda Testa

grafo orientato

L’arco ei si dice uscente da vh ed entrante in vk

v1

v4 v3

v2

e1 e2

e3

e6e4

e5

G-164

• Dato G=(V,E) non orientato si dice cammino (walk) in G un

insieme ordinato di nodi W={v0,v1,...,vk} con k≥1 (cammino v0-vk in

G) se (vi-1,vi)∈E ∀i=1,...,k

• I nodi v0 e vk sono gli estremi del cammino W={v0,v1,...,vk}

• Se G è orientato, W={v0,v1,...,vk} con k≥1 dove (vi-1,vi)∈E

∀i=1,...,k si dice cammino orientato in G

• Il numero di archi di W si dice lunghezza di W

• La distanza tra due nodi u e v è pari alla lunghezza minima di un

cammino tra u e v

Esempio

Cammini e percorsi

cammino orientato

W’={v1,v4,v1,v4,v2,v3}

v1

v4 v3

v2

e1 e2

e3

e6e4

e5

W={v1,v4,v3,v2}

cammino

G-165

• Dato G=(V,E) non orientato si dice cammino semplice o percorso

(path) in G, P={v0,v1,...,vk} un cammino tale che tutti i nodi ed archi

che lo compongono sono distinti.

Esempio

v1

v4 v3

v2

e1 e2

e3

e6

percorso(cammino semplice)

e4

e5

P’

P’={v1,v4,v2,v3}

• Se esiste un cammino (orientato) tra u e v, allora esiste un cammino

semplice (orientato) tra u e v

• W={v0,v1,...,vk, v0} è detto cammino chiuso

• Un cammino semplice chiuso è detto ciclo (circuito)

cammino chiuso ciclo

1

2

34

5

6

ciclo orientato

Esempio

G-166

• Dato G=(V,E) un nodo v∈V si dice connesso ad un nodo z∈V se

esiste un cammino (orientato o non) tra v e z in G

• v∈V è connesso a v (riflessività)

• v∈V è connesso a z∈V ⇒ z∈V è connesso a v∈V (simmetria)

• se v∈V è connesso a z∈V e z∈V è connesso a u∈V ⇒ v∈V è

connesso a u∈V (transitività)

• L’insieme V può essere partizionato in sottinsiemi

Ci={v∈V:v è connesso a z, ∀z∈Ci}

• Il sottografo indotto da Ci in G è detto componente connessa di G

• Se G possiede una sola componente connessa si dice connesso

(∀v,z∈V v è connesso a z)

Grafi connessi e componenti connesse

componenticonnesse

grafo connesso

Esempio

G-167

• Dato G=(V,E) grafo orientato, v∈Vè fortemente connesso a z∈Vse

esistono due cammini orientati in G, il primo da v a z ed il secondo da

z a v

• Un grafo può essere partizionato in componenti fortemente connesse

in maniera analoga a quanto fatto per le semplici componenti

connesse

• In una componente fortemente connessa ogni nodo è connesso ad un

altro da un cammino orientato

• G è un grafo fortemente connesso se ha una sola componente

fortemente connessa

componentifortemente connesse

grafofortemente connesso

Esempio

G-168

Percorsi e circuiti hamiltoniani

• Un percorso hamiltoniano è un percorso che passa per tutti i nodi

del grafo una sola volta (tour)

• Un circuito hamiltoniano è un cammino hamiltoniano chiuso

circuito hamiltoniano

1

2

3

45

Problemi associati:• stabilire se un grafo ha un percorso hamiltoniano• determinare in un grafo completo il circuito hamiltoniano a peso

(costo) minimo (Travelling Salesman’s Problem, TSP)

Esempi di applicazioni:• problemi di trasporto (e.g., stabilire la rotta di un veicolo per la

distribuzione di beni ad un dato insieme di clienti)• minimizzare il costo di set-up per certi tipi di produzione

manifatturiera ciclica

Esempio

G-169

• Un cammino euleriano è un percorso che passa per ogni arco una

sola volta

• Un circuito euleriano è un cammino euleriano chiuso

circuito euleriano

Esempio

Cammini e circuiti euleriani

12

3

4

5

67

8

Esempi di applicazioni:• problemi di trasporto (e.g., stabilire la rotta di un veicolo postale in

modo da distribuire la posta in maniera efficiente - ChinesePostman’s Problem)

• problemi di ispezioni di sistemi distribuiti (e.g., reti elettriche,telefoniche, ferroviarie)

Il problema dei ponti di Konigsberg (Eulero, 1736)

A B

C

D

A B

C

D

G-170

Alberi

• Un grafo è aciclico se non contiene cicli (orientati o non)

• Un albero è un grafo connesso ed aciclico

• Ogni grafo aciclico è in generale l’unione di alberi e viene detto

foresta

Dato G=(V,E), le seguenti affermazioni sono equivalenti:

• G è un albero

• ogni coppia di nodi di G è connessa da un unico cammino

• G è aciclico eE=V-1

• G è aciclico e connettendo due nodi non adiacenti con un arco si

ottiene un grafo con un unico ciclo

• G è connesso eE=V-1

grafo aciclico(foresta)

grafo non aciclico albero

Esempio

G-171

• Dato un albero T=(V,E), si dice foglia v∈V tale cheδ(v)=1

(w(v)=1 )

• Se V≥2 allora esistono almeno due foglie

foglie di un albero

• Dato G=(V,E), si dice albero ricoprente (spanning tree) di G un

albero T=(W,F) con W=V ed F⊆E (è un sottografo di G)

un albero ricoprente

G-172

Il Problema del Minimo Albero Ricoprente(Minimum Spanning Tree)

• Si considera un grafo G=(V,E)

• Ad ogni arco ei, i=1,...,n di G è associato un costo ci, i=1,...,n

Il problema: determinare l’albero ricoprente di G con il minimo

costo associato.

Esempio7

14

4 109

178

13

2

11 12

6

13

16

155

Due algoritmi:• l’algoritmo di Kruskal (Greedy Algorithm)• l’algoritmo di Prim

Esempi di applicazioni:• determinare la rete di comunicazione più affidabile• determinare la connessione tra n centri a costo minimo (e.g.,

distribuzione del gas)

G-173

Algoritmo di Kruskal (Minimum Spanning Tree)

(1) E’ dato il grafo G=(V,E) con m nodi ed n archi.

Si ordinano gli archi e1, e2,..., en in modo che i costi associati

non siano decrescenti (c1≤c2≤... ≤cn ).

Si pone E0=∅, k=1 ed il grafo ST0=(V, ∅)

(2) Se (V, Ek-1∪{ek}) è un grafo aciclico allora STk=(V, Ek) con

Ek=Ek-1∪{ek}, altrimenti Ek=Ek-1 e STk= STk-1

(3) Se Ek=m-1 l’algoritmo si ferma ed STk è l’albero ricoprente

cercato, altrimenti k=k+1 e continuare col passo (2).

Esempio:m=9n=17

714

4 109

178

13

2

11 12

6

13

16

155

G-174

Algoritmo di Prim (Minimum Spanning Tree)

(1) E’ dato il grafo G=(V,E) con m nodi ed n archi.

Si sceglie un vertice arbitrario di G, V0={vs}, si pone E0=∅ e k=1

(2) Si connette un nodo vi∈Vk-1 con un nodo vh∈V- Vk-1 tale che il

costo dell’arco (vi,vh) sia

e si pone Vk=Vk-1∪ {vh} e Ek=Ek-1∪ {(vi,vh)}

(3) Se Ek=m-1 l’algoritmo si ferma e ST=(Vk,Ek) è l’albero

ricoprente cercato, altrimenti k=k+1 e continuare col passo (2).

Esempio:m=6n=12

7

17

10

10.5

9

7.5

11

8

12

16

9.5

19

L’algoritmo di Prim O(V2) è più efficiente di quello diKruskal (O(ElogE)).

[ ]c v v c v vi hv j Vk ve V Vk

v j ve E

j e( , ) min ( , ),

( , )

=∈ − ∈ − −

∈

1 1

G-175

Matrici di Incidenza dei Grafi

• Dato G=(V,E) grafo non orientato, AG=[aij], con i=1,...,m e j=1,...,n

è la matrice di incidenza di G, dove m=V ed n=E, e tale che

=altrimenti0

edicodaotestaèvse1a ji

ij

matrice di incidenza di un grafo non orientato

v1v2

v4v3

e1 e2 e3

e4

e5AG =

1 0 0 0 1

0 1 1 0 0

1 0 1 1 0

0 1 0 1 1

e e e e e1 2 3 4 5v

v

v

v

1

2

3

4

Esempio

G-176

• Dato G=(V,E) grafo orientato, AG=[aij], con i=1,...,m e j=1,...,n è la

matrice di incidenza di G, dove m=V ed n=E, e tale che

−=

altrimenti0

editestaèvse1

edicodaèvse1

a ji

ji

ij

matrice di incidenza di un grafo orientato

v1v2

v4v3

e1 e2 e3

e4

e5 AG =

−−

−− −

1 0 0 0 1

0 1 1 0 0

1 0 1 1 0

0 1 0 1 1

e e e e e1 2 3 4 5v

v

v

v

1

2

3

4

Esempio

Utilizzando la matrice di incidenza si possono ridefinire:

• w+(vi)={ej∈E: aij=-1} (stella uscente)

• w-(vi)={ej∈E: aij=1} (stella entrante)

G-177

Il Problema del Percorso Minimo(Shortest Path Problem)

• E’ dato un grafo orientato G=(V,E)

• Ad ogni arco ei, i=1,...,n di G è associato un peso wi, i=1,...,n, conwi≥0 oppure wi≤0

• Il peso di un cammino orientato P={v0,v1,...,vK} è definito come

Il problema: determinare il percorso orientato P* di G che unisce

due nodi dati s,t∈V e che abbia peso minimo.

{ }w P w dove E e v v i Kiei EP

P i i i( ) ( , ), ,...,= ∑ = = =∈

−1 1

Osservazioni:

• Se non esiste un cammino tra s e t il problema non èammissibile

• Se esiste un ciclo orientato C in G tale che w(C)<0 (pesonegativo), il problema è illimitato

• P* è sempre un percorso (cammino semplice) ⇔ non esistonocicli con peso negativo in G

Esempio

1

3

52 -5

ciclo con peso negativo

G-178

Algoritmo di Dijkstra (Shortest Path - pesi non negativi)

Algoritmo

(1) Porre g(s)=0, U={s},

h(i)=wsi e p(i)=s ∀(s,i)∈E, mentre h(j)=∞ e p(j) non definitoper ogni altro nodo tale che (s,j)∉E.

(2) Selezionare

e porre U=U∪{i}, e g(i)=h(i). Se U=V l’algoritmo termina ed il

percorso minimo s-t resta determinato dalla sequenza dei p(i).

(3) ∀j∉U connesso ad i ((i,j)∈E) aggiornare l’etichetta

h(j)=min{g(i)+wij, h(j)}. Se h(j)=g(i)+wij porre p(j)=i.

Andare al passo (2).

Notazione:

• g(i) peso del percorso minimo s-i

• h(i) etichetta del nodo i (valore attuale del percorso)

• wij peso dell’arco (i,j)∈E

• p(i) predecessore del nodo i lungo il percorso minimo

• U insieme dei nodi visitati

[ ]i h ii U

=∉

arg min ( )

G-179

Esempio: il percorso minimo tra B e D

7

2

81

G

23 E 2

4

1 47

2

10

F3

B

A

C

D

A B C D E F G

Notazione• (h(i),p(i))• *(g(i),p(i))

(7,B) *(0,B) (1,B) (∞,-) (∞,-) (∞,-) (∞,-)

*(1,B)

(4,C) (5,C) (4,C)

(4,C) *(0,B) *(1,B) (∞,-) (5,C) *(4,C) (∞,-)

(7,B) *(0,B) (∞,-) (∞,-) (∞,-) (∞,-)

*(1,B)*(0,B) (∞,-) (∞,-)

(4,C) *(0,B) *(1,B) (14,F) (5,C) *(4,C) (11,F)

*(4,C) *(0,B) *(1,B) (14,F) (5,C) *(4,C) (11,F)

*(4,C) *(0,B) *(1,B) (12,A) (5,C) *(4,C) (11,F)

*(4,C) *(0,B) *(1,B) (12,A) *(5,C) *(4,C) (7,F)

*(4,C) *(0,B) *(1,B) (9,G) *(5,C) *(4,C) *(7,E)

*(4,C) *(0,B) *(1,B) *(9,G) *(5,C) *(4,C) *(7,E)

il percorso minimo è B-C-E-G-D

G-180

4

3

-2

B

A

C

Osservazioni:• l’algoritmo determina tutti i percorsi minimi tra un nodo iniziale

e gli altri• l’algoritmo può fallire se esistono archi con peso negativo

A B C

*(0,A) (∞,-) (∞,-)

*(0,A) (4,A) (3,A)

*(0,A) (4,A) *(3,A)

*(0,A) *(4,A) (2,B)L’algoritmo si contraddice!

Esempio

G-181

Algoritmo di Bellman-Ford(Shortest Path - pesi non vincolati)

Algoritmo

(1) Porre h0(s)=0, h0(j)=∞ ∀j∈V-{s}, p(j)=j ∀j∈V e k=1

(2) ∀j∈V calcolare

Se hk(j)=hk-1(i)+wij porre p(j)=i.

(3) Se hk(j)=hk-1(j) ∀ j∈V allora g(j)= hk(j) ∀ j∈V e l’algoritmo

termina ed il percorso minimo s-t resta determinato dalla

sequenza dei p(i) Altrimenti, se k<m porre k=k+1 ed andare al

passo (2); se invece k=m, il grafo contiene un ciclo di peso

negativo, l’algoritmo termina ed il problema è illimitato.

Notazione:

• g(i) peso del percorso minimo s-i

• hk(i) etichetta del nodo i al passo k (valore attuale del percorso)

• wij peso dell’arco (i,j)∈E

• p(i) predecessore del nodo i lungo il percorso minimo

[ ]h j h j w h ik k

i i j Eij

k( ) min ( ), min ( ):( , )

= +

−∈

−1 1

G-182

Esempio: il percorso minimo tra A e G

8

2-1 G

3

-3

E

1

-44 4

12

-2

10

FB

A

C

D

m=7, n=12

il percorso minimo è A-C-E-G

A B C D E F G

(0,A) (∞,B) (∞,C) (∞,D) (∞,E) (∞,F) (∞,G)

(4,A)

(3,C)

(7,E) (5,E)

(0,A) (8,A)

(14,C)

(10,F) (6,G)

(9,F)

(7,D)

(∞,D) (∞,E) (∞,F) (∞,G)

(4,A)(0,A) (8,A) (∞,F) (∞,G)

(3,C)(14,C)(4,A)(0,A) (8,A)

(5,E)(3,C)(4,A)(0,A) (8,A)

(6,G) (5,E)(3,C)(4,A)(0,A) (8,A)

(9,F) (6,G) (5,E)(3,C)(4,A)(0,A)

1

k

2

3

4

5

6

0

G-183

Formulazione di problemi combinatorici su grafi

Il Problema del Percorso Minimo (Shortest Path).

Dato un grafo orientato G=(V,E) tale che ad ogni arco èassociato un peso wij.Fissati due nodi s, t , trovare il percorso P da s a t con pesominimo.

Le variabili:

( , )i j E∈

∈V

xse i j P

se i j P

i j E

ij =∈∉

∀ ∈

1

0

( , )

( , )

( , )

{ }

{ }

min

,

, ( , )

( , )

( , ) ( ) ( , ) ( )

( ,s) ( ) ( , ) ( )

( , ) ( ) ( , ) ( )

w x

x x j V s t

x x

x x

x i j E

ij iji j E

iji j w j

iji j w j

isi w s

sjs j w s

iti t w t

tjt j w t

ij

∈

∈ − ∈ +

∈ − ∈ +

∈ − ∈ +

∑

−∑ =∑ ∀ ∈ −

−∑ = −∑

−∑ =∑

∈ ∀ ∈

0

1

1

0 1

dove w-(j) è la stella entrante di j, e w+(j) è la stella uscente di j

G-184

Data la matrice di incidenza AG del grafo, il problema si puòscrivere come

min w x

A x b

x

T

GE

=

∈B

dove x è il vettore di incidenza degli archi di G e b è un vettore di mcostanti.

b =−

0

0

1

1

M

G-185

Il Problema del Commesso Viaggiatore (Traveling Salesman Problem).

E’ dato un grafo G=(V,E). L’insieme dei nodi V={1,...,n} corrispondead un insieme di città, mentre l’insieme degli archi E corrisponde allepossibili strade che collegano coppie di città.Ad ogni strada , è associato un costo cij (che, ad es., puòrappresentare una distanza o un tempo).

Il problema: determinare un percorso chiuso che passi per tutte le cittàuna sola volta (un tour di G), in modo che il suo costo sia minimo(se G è completo il problema ammette sempre soluzione).

Le variabili:

xse la città j segue immediatamente i nel tour

altrimenti

x

ij

E

=

∈

1

0

B| |

I vincoli:

( , )i j E∈

x i Vkik k E:( ,i)∈

∑ = ∀ ∈1

Ogni città deve essere visitata una sola volta

x i Vijj i j E:( , )∈

∑ = ∀ ∈1

i(1) (2)

G-186

Questi vincoli non sono sufficienti ad escludere la formazione disub-tour:

1

2

3

4

5

6

7

x x x x

x x x12 23 34 41

57 76 65

1

1

= = = == = = è una scelta che soddisfa i vincoli (1) e (2)

Una possibilità per escludere la formazione di sub-tour:in ogni sottografo composto da un sottinsieme di nodi taleche non deve contenere cicli.

U V⊆2 2≤ ≤ −| | | |U V

x Uiji j E i j U

≤ −∑∈ ∈

| |( , ) : ,

1

Questa condizione corrisponde ad imporre che gli archi selezionatinel sottografo U formino al più un albero.

Il numero di questi vincoli è molto elevato, poichè è dell’ordine di 2| |V