Universit`a degli Studi di Roma “Tor Vergata” · 6.2 Problemi di massimo ﬂusso su grafo ......

Universita degli Studi di Roma

“Tor Vergata”

Dispense per il corso di

GRAFI E RETI DI FLUSSO

Antonio Iovanella

Ottobre 2006

I

Indirizzo dell’autore:

Antonio Iovanella

Dipartimento di Ingegneria dell’Impresa,

Universita di Roma “Tor Vergata”

Via del Politecnico 1, 00133 Roma - Italia

Email: [email protected]

Web Page: http://www.disp.uniroma2.it/Users/iovanella/

Home page della didattica: http://www.uniroma2.it/didattica/grfbis

Indice

1 Introduzione 1

1.1 Definizioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.1 Sottografi, ordine, dimensione e densita di un grafo . . . . . . . . . 4

1.1.2 Vicinati, gradi e regolarita . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.3 k-Fattorizzazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2 Grafi e modelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2.1 Relazioni e sottografi . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2.2 Assegnamento di lavori . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2.3 Scheduling di team in una azienda . . . . . . . . . . . . . . . . . . 11

1.2.4 Percorsi su rete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Algoritmi 17

2.1 Breve tassonomia dei problemi decisionali . . . . . . . . . . . . . . . . . . 17

2.2 Algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1 Algoritmi di ricerca . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 Crescita di funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3.1 Notazione Big-O . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3.2 Crescita di combinazioni di funzioni . . . . . . . . . . . . . . . . . . 24

2.4 Complessita degli algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.5 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

II

INDICE III

3 Proprieta e strutture dei grafi 32

3.1 Strutture dati per la rappresentazione di grafi . . . . . . . . . . . . . . . . 32

3.2 Isomorfismo tra grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.3 Connessione, cicli e grafi bipartiti . . . . . . . . . . . . . . . . . . . . . . . 39

3.4 Alberi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.5 Cammini Euleriani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.6 Cammini Hamiltoniani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.7 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Grafi Planari 50

4.1 Grafi sul piano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.2 Grafi duali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.2.1 Proprieta dei grafi planari e Formula di Eulero . . . . . . . . . . . . 54

4.2.2 Caratterizzazione dei grafi planari . . . . . . . . . . . . . . . . . . . 58

4.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5 Algoritmi di ricerca su grafo 60

5.1 Algoritmi di ricerca su grafo . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.2 Algoritmo di ordinamento topologico . . . . . . . . . . . . . . . . . . . . . 66

5.3 Algoritmi di ricerca di alberi ricoprenti minimi . . . . . . . . . . . . . . . . 69

5.3.1 Algoritmo di Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.3.2 Algoritmo di Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

5.4 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6 Problemi di flusso su grafo 79

6.1 Algoritmi di ricerca del cammino minimo su di un grafo . . . . . . . . . . . 80

6.1.1 L’algoritmo di Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.2 Problemi di massimo flusso su grafo . . . . . . . . . . . . . . . . . . . . . . 88

6.2.1 L’algoritmo di Ford e Fulkerson . . . . . . . . . . . . . . . . . . . . 93

6.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

Elenco delle figure

1.1 L’attuale mappa dell’area dei ponti del problema di Konisberg [1]. . . . . . 2

1.2 Grafo corrispondente al Problema di Konisberg. . . . . . . . . . . . . . . . 2

1.3 Grafo dell’Esempio 1.1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Un sottografo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.5 Un sottografo indotto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.6 Un sottografo ricoprente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.7 Esempi di grafi 3-regolari . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.8 Le fattorizzazioni di K4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.9 Grafo rappresentante le relazioni di conoscenza tra i cinque membri del gruppo 10

1.10 Grafo rappresentante le relazioni di non conoscenza tra i cinque membri del

gruppo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.11 Grafo bipartito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.12 Una istanza del problema dei team . . . . . . . . . . . . . . . . . . . . . . 12

1.13 Un cammino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.14 Un ciclo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.15 Alcuni esempi di path e cicli . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.16 Grafo per l’Esempio 1.2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1 Grafico delle funzioni piu comunemente usate nella stima Big-O . . . . . . 26

3.1 Grafo non orientato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.2 Grafo orientato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3 Lista di adiacenza per il grafo di Figura 3.2. . . . . . . . . . . . . . . . . . 36

IV

ELENCO DELLE FIGURE V

3.4 Esempio di due grafi isomorfi . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.5 Due grafi isomorfi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.6 I grafi bipartiti completi K2,3 e K3,3. . . . . . . . . . . . . . . . . . . . . . 39

3.7 Un grafo con quattro componenti connesse. . . . . . . . . . . . . . . . . . . 40

3.8 Componente connessa di x . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.9 Un circuito con un nodo ripetuto. . . . . . . . . . . . . . . . . . . . . . . . 41

3.10 Una foresta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.11 Un albero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.12 Come spostare i quattro cavalli. . . . . . . . . . . . . . . . . . . . . . . . . 47

4.1 Il problema dei tre nemici. . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.2 Connessioni per il problema dei tre nemici. . . . . . . . . . . . . . . . . . . 51

4.3 K5 e K3,3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.4 La facce di un grafo planare. . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.5 Costruzione del duale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.6 Un esempio di grafo G e del suo duale G∗. . . . . . . . . . . . . . . . . . . 54

4.7 Esempio di due embedding planari con duali non isomorfi. . . . . . . . . . 55

4.8 Il ciclo C evidenziato per la dimostrazione del teorema. . . . . . . . . . . . 57

4.9 Contrazione dell’arco e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.1 L’algoritmo di ricerca su grafo. . . . . . . . . . . . . . . . . . . . . . . . . 62

5.2 Grafo per gli Esempi 5.1.1 e 5.1.2. . . . . . . . . . . . . . . . . . . . . . . 63

5.3 Albero dei cammini e valori dei vettori pred(i) e ordine(i) nel caso FIFO. . 64

5.4 Albero dei cammini e valori dei vettori pred(i) e ordine(i) nel caso LIFO. . 66

5.5 L’algoritmo di ordinamento topologico. . . . . . . . . . . . . . . . . . . . . 67

5.6 Grafo per l’Esempio 5.2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.7 Contenuto del vettore ordine(i) dopo l’ordinamento topologico. . . . . . . 69

5.8 Tagli e path per le condizioni di ottimalita. . . . . . . . . . . . . . . . . . . 70

5.9 Grafo per l’Esempio 5.3.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.10 Evoluzione dell’algoritmo di Kruskal sul grafo di Figura 5.9. . . . . . . . . 75

ELENCO DELLE FIGURE VI

5.11 Evoluzione dell’algoritmo di Prim sul grafo di Figura 5.9. . . . . . . . . . . 77

6.1 Cammini da s a k. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.2 L’algoritmo di Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.3 Grafo per l’Esempio 6.1.1 e corrispondente tabella degli archi. . . . . . . . 85

6.4 Evoluzione delle etichette dei nodi e lista di adiacenza per il grafo di Figura 6.3. 87

6.5 Disegno per la correttezza di Dijkstra . . . . . . . . . . . . . . . . . . . . . 88

6.6 Costruzione del grafo residuo. . . . . . . . . . . . . . . . . . . . . . . . . . 90

6.7 Un grafo G con un flusso assegnato x ed il corrispondente grafo residuo G(x). 91

6.8 Un taglio s-t per il grafo di Figura 6.7. . . . . . . . . . . . . . . . . . . . . 91

6.9 L’algoritmo di Ford e Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . 95

6.10 Grafo per l’Esempio 6.2.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

6.11 Il grafo residuo dopo la prima iterazione. . . . . . . . . . . . . . . . . . . . 96

6.12 Il grafo residuo dopo la seconda iterazione. . . . . . . . . . . . . . . . . . . 97

6.13 Il grafo residuo dopo la terza iterazione. . . . . . . . . . . . . . . . . . . . 97

6.14 Il grafo residuo dopo la quarta iterazione. . . . . . . . . . . . . . . . . . . . 98

6.15 Il taglio minimo del grafo di Figura 6.10. . . . . . . . . . . . . . . . . . . . 98

6.16 Istanza patologica per l’algoritmo di Ford e Fulkerson. . . . . . . . . . . . 99

PREFAZIONE VII

Prefazione

Queste dispense nascono per essere affiancate ai testi adottati per i corsi di Grafi e Reti di

Flusso, previsti per gli studenti di Ingegneria Gestionale e per quelli di Ingegneria Online

della Facolta di Ingegneria dell’Universita di Roma Tor Vergata. Esse costituiscono inoltre

un utile strumento di approfondimento per gli studenti del corso di Teoria dei Grafi e Reti

di Flusso del Master di II livello in Ingegneria dei Sistemi a Rete della Facolta di Ingegneria

dell’Universita di Roma Tor Vergata.

Essendo questa la primissima versione delle dispense, conterra sicuramente degli er-

rori. Inoltre i miei sforzi non saranno stati di certo sufficienti a creare uno strumento

chiaro e completo. Per questo confido nella collaborazione dei lettori nel segnalarmi ogni

imprecisione che rileveranno e le parti poco chiare o incomplete.

In queste pagine sono presenti tutti gli argomenti che saranno trattati nei moduli di-

dattici. I testi originali dai quali ho tratto ispirazione per la redazione di queste note sono

raccolti nella bibliografia, e pertanto invito tutti gli studenti a tenerli in considerazione

come riferimento ufficiale in caso di dubbi o imprecisioni.

Gli argomenti trattati in queste dispense seguono fedelmente quelli svolti in aula. In

dettaglio, nel Capitolo 1 verranno introdotti i concetti e le definizioni di base della teoria

dei grafi che possono essere approfonditi su [9], [2], [4], [7] e [14]; nel Capitolo 2

verra introdotto il concetto di algoritmo e vedremo i metodi di misura della loro efficienza,

argomenti che possono essere studiati su [8], [11] e [12]. I testi [10], [2], [7] e [14]

possono essere usati come riferimento per il Capitolo 3 nel quale verranno illustrate alcune

importanti caratteristiche dei grafi come l’isomorfismo e l’eulerianita, mentre [14], [7],

[11] sono stati usati per il Capitolo 4 dove tratteremo i grafi planari. I testi [10], [7]

e [3] sono invece alla base dei Capitoli 5 e 6 dove verranno illustrati rispettivamente gli

algoritmi di ricerca su grafo e gli algoritmi di flusso.

Ottobre 2006

Capitolo 1

Introduzione

Ognuno di noi su questo pianeta e separato dagli altri solo da sei persone.

Sei gradi di separazione fra noi e tutti gli altri su questo pianeta: il presidente

degli Stati Uniti, un gondoliere veneziano... Non solo nomi importanti, chiunque:

un indigeno australiano, uno della Terra del Fuoco, un eschimese.

Io sono legato a chiunque sul pianeta da una catena di sei persone.

E’ un pensiero profondo... ognuno di noi e una porta spalancata su altri mondi.

John Guare

Per definire il concetto di grafo si fa spesso ricorso ad un episodio che viene associato

alla nascita stessa della Teoria dei Grafi, ovvero alla formulazione del famoso Problema dei

Ponti di Konisberg da parte di Eulero in un suo lavoro del 1736.

Nella citta di Konisberg (all’epoca appartenente alla Prussia, attualmente situata in

Russia con il nome di Kaliningrad) ci sono, oggi come allora, delle aree abitative insediate

su alcune isole del fiume Pregel ed altre che sorgono lungo le sue rive, per un totale di

quattro aree. Queste zone sono unite tra di loro da sette ponti, cosı come si puo vedere

nell’attuale mappa della zona, riportata in Figura 1.1. Il problema posto da Eulero si puo

formulare nel seguente modo: e possibile trovare un percorso chiuso che, a partire da una

qualunque area, permetta di attraversare i ponti una ed una sola volta e ritornare al punto

di partenza?

La zona presa in esame puo essere schematizzata come in Figura 1.2 dove i punti in

grassetto rappresentano le aree (le due isole, indicate con le lettere a e d e le due rive

1

Introduzione 2

Figura 1.1: L’attuale mappa dell’area dei ponti del problema di Konisberg [1].

del fiume, indicate con le lettere b e c) e gli archi rappresentano i ponti tra le diverse

aree. Cercando di risolvere il problema ci si convince abbastanza presto che questo non

ha soluzione e che non ha soluzione anche se vogliamo passare per ogni ponte una ed una

sola volta, ma accettiamo di non ritornare esattamente nella stessa area. Eulero dimostro

che la forma delle suddette aree non ha alcuna influenza, ma che la soluzione dipende solo

dalle proprieta di connessione. La soluzione a questo problema sara data nel Capitolo 3.

a

b

d

c

a1a5

a4

a6

a7a2

a3

Figura 1.2: Grafo corrispondente al Problema di Konisberg.

Introduzione 3

1.1 Definizioni

In questa sezione verranno esposte le definizioni di base della Teoria dei Grafi. Il lettore

deve pero essere allertato del fatto che non esiste una notazione universalmente accettata,

ma che spesso per gli stessi concetti possono trovarsi in letteratura notevoli differenze1.

Per quanto possibile, verra data segnalazione lungo le pagine di queste note.

Definizione 1.1.1 Un grafo G e una tripla costituita da un insieme di vertici V (G) (det-

ti anche nodi), un insieme di archi E(G) e una relazione, detta relazione di incidenza,

che associa con un arco una coppia di vertici, detti estremi.

Un grafo puo essere rappresentato graficamente mediante dei punti per indicare i nodi

e da linee e curve per gli archi.

Esempio 1.1.1 In Figura 1.2 e disegnato il grafo G rappresentante il Problema di Koni-

sberg, dove l’insieme dei vertici e V (G) = {a, b, c, d} (le quattro regioni) e l’insieme degli

archi e E(G) = {a1, a2, a3, a4, a5, a6, a7} (i ponti). L’insieme degli archi puo rappresentarsi

anche come E(G) = {ab, ac, ad, bd, db, cd, dc} ed in questo modo risulta esplicitata mag-

giormente la relazione di incidenza. Notare che i nodi b e d (e anche c e d) hanno piu di

un arco in comune.

Gli esempi di problemi che possono essere descritti come un grafo sono molteplici. Per

esempio e possibile descrivere la rete stradale come un grafo dove i nodi sono gli incroci e

gli archi sono le strade che li congiungono; analogamente, un circuito elettrico puo essere

visto come un grafo i cui nodi sono le connessioni e gli archi i componenti del circuito

stesso.

Definizione 1.1.2 Un loop (o laccio) e un arco i cui estremi coincidono. Si chiamano

archi multipli gli archi i cui estremi sono gli stessi.

Definizione 1.1.3 Si definisce grafo semplice un grafo privo di loop ed archi multipli.

1Nel luglio del 2006, Douglas West ha proposto un sondaggio su Internet rivolto alla comunita di coloroche si occupano di Teoria dei Grafi per cercare di uniformare almeno alcune notazioni principali. Perquanto possibile, l’esito di tale sondaggio e stato preso in considerazione in queste note

Introduzione 4

Individueremo un grafo semplice mediante i suoi insiemi di nodi e di archi, considerando

l’insieme degli archi come un insieme di coppie non ordinate di vertici e scrivendo e = ab

(o egualmente e = ba) per un arco con estremi a e b.

Si possono dare ulteriori definizioni sui nodi e sugli archi:

Definizione 1.1.4 Se ab ∈ E(G) allora a e b si dicono adiacenti e si indica con a ∼ b.

I vertici a e b si dicono incidenti sull’arco ab.

Due archi si dicono adiacenti se hanno un vertice in comune.

Definizione 1.1.5 Un grafo G si dice finito se gli insiemi V (G) ed E(G) sono finiti.

In gran parte delle applicazioni i grafi sono finiti e privi di loop ed archi multipli. Di

conseguenza, in seguito faremo riferimento quasi esclusivamente a grafi semplici e sempre

a grafi finiti. Per evitare confusione, inoltre, non considereremo il grafo nullo, ovvero il

grafo con l’insieme dei vertici e degli archi vuoti.

Per semplicita di notazione, nel seguito indicheremo con V o N l’insieme dei vertici

V (G) e con E l’insieme degli archi E(G).

1.1.1 Sottografi, ordine, dimensione e densita di un grafo

Definizione 1.1.6 Dato un grafo G = (V,E), G′ = (V ′, E ′) e un sottografo di G se

V ′ ⊂ V ed E ′ ⊂ E e posso scrivere G′ ⊂ G. Se il sottografo G′ contiene tutti gli archi di G

che congiungono due vertici in G′, allora G′ e chiamato sottografo indotto e si indica

con G[V ′]. Se il sottografo G′ ha V ′ ≡ V , allora G′ e chiamato sottografo ricoprente.

Per indicare un sottografo scriveremo genericamente G′ ⊆ G e diremo che G contiene G′.

Esempio 1.1.2 Si consideri il grafo G = ({1, 2, 3, 4, 5, 6}, {12, 14, 16, 25, 34, 36, 45, 56}),rappresentato in Figura 1.3. In Figura 1.4 e rappresentato un suo generico sottogra-

fo con G′ = ({1, 2, 3, 4, 6}, {12, 14, 16, 36}), in Figura 1.5 il sottografo indotto G′ =

({1, 2, 3, 4, 6}, {12, 14, 16, 34, 36}) ed infine in Figura 1.6 il sottografo ricoprente G′ =

({1, 2, 3, 4, 5, 6}, {12, 14, 16, 36, 56}).

Introduzione 5

1

2

3

6

5

4

Figura 1.3: Grafo dell’Esempio 1.1.2

1

2

3

6

4

Figura 1.4: Un sottografo1

2

3

6

4

Figura 1.5: Un sottografo indotto

1

2

3

6

5

4

Figura 1.6: Un sottografo ricoprente

Spesso e possibile costruire nuovi grafi a partire da un grafo assegnato G cancellando

oppure aggiungendo vertici ed archi. Se V ′ ⊂ V , allora G−V ′ = G[V \V ′] e il sottografo di

G ottenuto cancellando tutti i vertici V ′ e tutti gli archi su di loro incidenti. Analogamente,

se E ′ ⊂ E, allora G − E ′ = (V,E\E ′). Se V ′ = {v} oppure E ′ = {xy}, allora la notazione

si semplifica in G− v e G−xy. Infine, se x ed y sono due vertici non adiacenti di G, allora

G + xy e ottenuto congiungendo x ed y con un arco.

Definizione 1.1.7 Si definisce ordine di un grafo G il numero dei suoi vertici, ovvero

|G| = |V (G)|; si definisce dimensione di un grafo il numero dei sui archi, ovvero e(G) =

|E(G)|.

Introduzione 6

Per indicare l’ordine di un grafo arbitrario si puo utilizzare inoltre la notazione Gn men-

tre attraverso la notazione G(n,m) si indica un grafo arbitrario di ordine n ed dimensione

m. Nell’esempio 1.1.2 il grafo ha ordine 6 e dimensione 8 e potremo indicarlo per esempio

come G(6, 8).

Dato un grafo semplice arbitrario di ordine n, ci chiediamo in quale campo di valori

possa variare il numero di archi m. Chiaramente, tali valori possono variare tra 0 (in

corrispondenza del grafo nullo) e tra il numero corrispondente al caso in cui tutti i nodi

sono mutualmente adiacenti, numero pari a tutte le possibili combinazioni di n oggetti

presi due a due. Quindi:

0 ≤ m ≤(

n

2

)

=n(n − 1)

2(1.1)

Nel caso specifico il coefficiente binomiale si scrive attraverso la formula che compare

nell’ultimo membro della Formula 1.1. Quindi un grafo d’ordine 6 potra, per esempio,

avere dimensione compresa tra 0 e 15.

Spesso il numero di archi di un grafo viene espresso in modo proporzionale rispetto al

massimo numero di archi possibile. A tale misura viene data il nome di densita di un

grafo e si calcola come:

D(G) =m

n(n − 1)/2(1.2)

chiaramente, tale misura varia da 0 a 1. In generale, diremo sparso un grafo che abbia

un numero di archi molto basso, ovvero una densita bassa (per esempio D(G) ≈ 0, 1÷0, 3);

viceversa, diremo che e denso un grafo che ha un alto numero di archi, quindi una densita

alta (per esempio D(G) ≈ 0, 7 ÷ 0, 9).

I grafi che hanno tutti i nodi mutualmente adiacenti rivestono una importanza parti-

colare e sono chiamati grafi completi (o clique) e sono indicati con Kn, dove n indica la

sua cardinalita. Dato che un grafo puo contenere sottografi completi, possiamo dare la

definizione piu generale:

Definizione 1.1.8 Un grafo completo (o clique) in un grafo G e un insieme di nodi

Introduzione 7

mutualmente adiacenti. Dato l’insieme di tutte le clique di G, la cardinalita della clique

massima viene chiamata numero di clique ed e indicato con ω(G).

1.1.2 Vicinati, gradi e regolarita

Passiamo ora a dare altre definizioni sui grafi.

Definizione 1.1.9 L’insieme dei vertici adiacenti ad un assegnato vertice x ∈ G e

chiamato vicinato di x e si indica con Γ(x).

Con il simbolo Γ(x) spesso ci si riferisce al vicinato aperto, mentre per indicare il vicinato

chiuso si usa scrivere Γ(x) ∪ {x}. Notare che se y ∈ Γ(x) e x ∈ Γ(y), allora significa che

x ∼ y e y ∼ x, ovvero xy e un arco del grafo.

Definizione 1.1.10 Si definisce grado d(x) di un nodo x ∈ G la cardinalita del suo

vicinato, ovvero, d(x) = |Γ(x)|. Se un vertice ha d(x) = 0, allora si definisce vertice

isolato.

Anche in questo caso il simbolismo non e univocamente definito, perche possiamo tro-

vare indicato il vicinato ed il grado rispettivamente con ΓG(x) e dG(x), in modo da non

sottintendere il grafo G.

Dato un grafo G, si usa indicare il suo grado minimo con δ(G) ed il suo grado massimo

con ∆(G)

L’introduzione del concetto di grado di un vertice ci permette di introdurre un primo

importante risultato generale, che viene chiamato spesso Lemma Handshaking 2:

Lemma 1.1.1 In ogni grafo, il numero di vertici di grado dispari e pari.

Dimostrazione: Sommando i gradi di ogni vertice, ogni arco e contato esattamente due

volte (una volta per ogni vertice). Quindi avremo che:

∑

∀i∈V

d(i) = 2m (1.3)

2La ragione del nome del lemma deriva dal fatto che in un ricevimento, se tutti gli invitati si salutanotra loro allora la somma totale delle strette di mano (in inglese, handshaking) e sempre pari.

Introduzione 8

Dato che il secondo membro e positivo, anche il primo deve esserlo; quest’ultimo e

composto da due contributi, la somma dei gradi pari e la somma dei gradi dispari. E

quindi chiaro che il contributo dei vertici di grado dispari deve essere pari e questo accade

solo se sono in numero pari.

Definizione 1.1.11 Dato un grafo G, se δ(G) = ∆(g) = k allora G si dice k-regolare.

Un grafo G si dice regolare se e k-regolare per un certo k.

Figura 1.7: Esempi di grafi 3-regolari

Per esempio, tutte le clique Kn sono (n − 1)-regolari; ancora, se k = 3 si ha un grafo

3-regolare (vedi Figura 1.7), detto anche cubico.

1.1.3 k-Fattorizzazioni

Definizione 1.1.12 Un k-fattore e un sottografo ricoprente k-regolare.

Se l’insieme degli archi puo essere diviso in k-fattori ho una decomposizione che prende

il nome di k-fattorizzazione . Se ho una decomposizione in 1-fattori allora la decom-

posizione prende il nome di fattorizzazione ed ha ovviamente senso solo se il grafo ha un

numero pari di nodi. In Figura 1.8 sono rappresentate (con gli archi in grassetto) le tre

possibili fattorizzazioni di K4.

Introduzione 9

2

3 4

1 2

3 4

1 2

3 4

1

Figura 1.8: Le fattorizzazioni di K4

1.2 Grafi e modelli

In questa sezione verranno mostrate alcune applicazioni pratiche che possono essere rap-

presentate mediante dei grafi. Gli esempi illustrati ci serviranno soprattutto per introdurre

nuove definizioni e termini della teoria dei grafi.

1.2.1 Relazioni e sottografi

Supponiamo sia assegnato un gruppo di cinque persone; come e possibile rappresentare

le relazioni di conoscenza tra i membri del gruppo? Se indichiamo con le prime cinque

lettere dell’alfabeto i cinque membri del gruppo, possiamo costruire un grafo nel quale i

nodi rappresentano i membri, ed un arco esiste se due membri si conoscono. Supponiamo

sia assegnata un’istanza di tale problema come in Figura 1.9.

Supponiamo di voler studiare ora il problema complementare: dato ancora lo stesso

gruppo di persone, come rappresentare le relazioni di non conoscenza tra i membri?

Definizione 1.2.1 Il grafo complemento G di un grafo semplice G e un grafo semplice

avente insieme dei nodi V (G) ≡ V (G) ed insieme degli archi tale che un arco ab esiste in

G se e solo se ab /∈ E(G).

Definizione 1.2.2 Un insieme indipendente (o insieme stabile) W in un grafo e un

insieme di vertici mutuamente non adiacenti, ovvero se e soltanto se il sottografo indotto

G[W ] = ∅.

Introduzione 10

a

b

c

e d

Figura 1.9: Grafo rappresentante lerelazioni di conoscenza tra i cinquemembri del gruppo

a

b

c

e d

Figura 1.10: Grafo rappresentante lerelazioni di non conoscenza tra i cinquemembri del gruppo

La definizione di complementarieta ci permette di legare tra di loro i due problemi

introdotti e di ottenere il grafo rappresentante il secondo attraverso tale definizione, come

si puo vedere in Figura 1.10. Possiamo notare inoltre che nel grafo G, il sottografo {a, b, c}e una clique di ordine 3 e {c, e} e un insieme indipendente di cardinalita 2. Corrisponden-

temente, nel grafo G, i nodi {a, b, c} sono un insieme indipendente di cardinalita 3 e {c, e}e una clique di ordine 2. Quindi gli insiemi indipendenti di un grafo diventano clique nel

suo grafo complementare cosı come le clique in un grafo diventano insiemi indipendenti nel

suo grafo complemento.

L’insieme indipendente, oltre che alla clique, e legato ad un altro concetto, ovvero quello

del vertex covering:

Definizione 1.2.3 Un vertex covering di un grafo G e un sottoinsieme V ′ di V tale

che ogni arco di G e incidente con almeno un vertice in V ′.

Si puo dimostrare [14] che, se α e il valore della cardinalita del massimo insieme indi-

pendente di G e β la cardinalita del piu piccolo V ′ tale che sia un vertex covering di G,

allora α + β = n, dove n e l’ordine di G. Infatti, ogni insieme indipendente di cardinalita

massima e il complemento di un vertex cover minimo.

1.2.2 Assegnamento di lavori

Si supponga che un’azienda debba effettuare n compiti diversi, da assegnare ognuno ad

m dipendenti, che pero non sono interscambiabili perche ognuno di essi possiede delle

Introduzione 11

specializzazioni. In che modo assegnare i compiti ai dipendenti?

Per risolvere questo problema possiamo costruire un grafo nel quale i vertici sono gli

n compiti e gli m dipendenti, mentre un arco ij esiste se il compito i puo essere svolto

dal dipendente j. In Figura 1.11 e disegnato un grafo corrispondente al caso in cui n =

m = 4 e si puo notare come in realta l’insieme dei nodi sia partizionato in due sottoinsiemi

(indipendenti) V1 (corrispondenti ai compiti) e V2 (corrispondenti ai dipendenti).

V1

V2

Figura 1.11: Grafo bipartito

Per questa particolare categoria di grafi possiamo dare la seguente definizione:

Definizione 1.2.4 Un grafo G si dice bipartito se l’insieme dei suoi nodi V (G) e l’unione

di due insiemi indipendenti disgiunti V1 e V2 chiamati insiemi partizione ed ogni suo arco

va da V1 a V2.

Un grafo bipartito e anche chiamato 2-partito, perche puo essere visto come un parti-

colare caso dei grafi r-partiti, ovvero di quei grafi nei quali l’insieme dei nodi e costituito

dall’unione di r insiemi partizione e gli archi vanno da una delle partizioni verso una

qualunque delle altre.

1.2.3 Scheduling di team in una azienda

Una azienda ha la necessita di schedulare3 un certo numero di riunioni dei vari team, ma

ha il vincolo che alcuni manager appartengono a team differenti e quindi non e possibile

indire due riunioni contemporaneamente se hanno un manager in comune.

3Il termine inglese scheduling indica un problema decisionale che considera l’allocazione di risorse scar-se ad attivita, con l’obiettivo di ottimizzare una o piu misure di prestazione. Siccome tale parola eintraducibile in italiano, viene di solito adattata, ottenendo i termini schedulare, schedulato, ecc.

Introduzione 12

a b e

dc

1

1 2 1

3

Figura 1.12: Una istanza del problema dei team

Per rappresentare tale problema posso disegnare un grafo nel quale i nodi sono i team,

ed esiste un arco se i due team hanno un membro in comune, come in Figura 1.12. Per

risolverlo, invece, posso usare un algoritmo che, partendo da un nodo, assegni ad ognuno

di essi una etichetta (colore) in modo che due nodi adiacenti non abbiano stessa etichet-

ta. Associando l’etichetta ad un istante temporale, e considerando che nodi che hanno

stessa etichetta non hanno membri in comune, ne consegue che per risolvere il problema

e sufficiente schedulare i team nell’ordine dato dalle etichette. Per esempio, considerando

le etichette assegnate al grafo in Figura 1.12 una possibile sequenza e {a, c, e}, {b} e {d}(notare come l’ordine delle etichette corrisponda agli istanti di attuazione).

Generalizzando il problema, ci si puo chiedere quale sia, tra tutte le etichettature

ammissibili, quella che implica il minor numero di etichette possibili.

Definizione 1.2.5 Si definisce numero cromatico di un grafo G e si indica con χ(G),

il minimo numero di colori necessari per etichettare i vertici in modo che vertici adiacenti

ricevano colori diversi.

Il termine colore deriva dal famoso Problema dei quattro colori, posto da Francis e

Frederick Guthrie nel 1852 e da A. Cayley nel 1878, nel quale si ci si chiedeva quale fosse il

minimo numero di colori necessari per colorare una mappa geografica politica. Nel 1890 P.

J. Heawood congetturo che bastassero quattro colori, ma tale congettura e stata dimostrata

definitivamente solo nel 1976 da K. Appel e W. Haken. Per altri aspetti storici sul problema

dei quattro colori rimandiamo il lettore a [9].

Introduzione 13

1.2.4 Percorsi su rete

Uno dei campi nel quale la teoria dei grafi trova grande applicazione e quello della rap-

presentazione delle reti stradali. Infatti, possiamo associare un vertice del grafo ad ogni

incrocio stradale ed unire tra di loro tali vertici con un arco in corrispondenza del tratto di

strada che unisce i due incroci. Inoltre possiamo iniziare ad introdurre dei nuovi elementi

che possiamo associare agli archi ed ai nodi, ovvero dei pesi; in questo caso, un peso asso-

ciato agli archi puo rappresentare la lunghezza del tratto stradale, oppure la sua capacita

in termini di auto per ora, ecc.

Questa rappresentazione fa nascere alcuni quesiti, per esempio, dati due vertici qua-

lunque a e b, e possibile individuare sulla rete il cammino piu breve tra questi due punti?

Oppure, se i vertici rappresentano delle citta e gli archi la rete autostradale, e possibile

individuare un percorso che partendo da una generica citta visiti tutte le restanti con un

percorso di distanza minima?

Vedremo nel seguito come risolvere il primo problema (vedi Capitolo 6) mentre per il

secondo rimandiamo alla bibliografia, invitando il lettore ad approfondire gli argomenti

riguardanti il cosiddetto Problema del commesso viaggiatore o TSP, Travelling Salesman

Problem per esempio in [7] o [14].

Definizione 1.2.6 Un cammino (o anche path) e un grafo semplice i cui vertici possono

essere ordinati in una lista in modo che due vertici sono consecutivi se e soltanto se sono

consecutivi nella lista medesima.

Quindi, P = (V (P ) = {x0, x1, . . . xl}, E(P ) = {x0x1, x1x2 . . . xl−1xl}) e un cammino

che indicheremo con x0x1 . . . xl. Chiameremo i vertici x0 e xl terminali del cammino.

Inoltre, se indichiamo con di la lunghezza associata ad ogni arco, allora l =∑

∀xixj∈E(P ) di

e la lunghezza del cammino.

Definizione 1.2.7 Un ciclo e un cammino con egual numero di vertici ed archi e con i

terminali coincidenti.

A titolo di esempio, in Figura 1.13 e rappresentato il cammino x0x1x3x2x4x5, mentre

in Figura 1.14 e rappresentato il ciclo x0x1x3x2x4x5x0.

Introduzione 14

x2 x1 x0

x3 x4 x5

Figura 1.13: Un cammino

x2 x1 x0

x3 x4 x5

Figura 1.14: Un ciclo

C4

C5

P3

P4

Figura 1.15: Alcuni esempi di path e cicli

Per indicare path e cicli arbitrari si usa aggiungere alla nomenclatura un pedice che

indica il numero di archi di cui sono composti. Quindi, per esempio, P4 indica un path

di lunghezza 4, mentre C5 indica un ciclo di lunghezza 5 (alcuni esempi sono dati in

Figura 1.15). Inoltre, un path con terminali x e y viene spesso indicato come “{x, y}-path”.

Un cammino od un ciclo possono essere identificati come sottografi in un grafo arbitrario

e questo ci porta a generalizzare le definizioni appena date.

Definizione 1.2.8 Dato un grafo arbitrario G = (V,E), allora:

• un walk W in un grafo e una sequenza alternata di vertici ed archi, x0e1x1e2 . . . elxl,

con ei = xi−1xi e 0 < i ≤ l;

• un trail T e un walk con tutti gli archi distinti;

• un path P e un trail con tutti i vertici distinti;

• un trail chiuso (o anche circuito) e un trail con x0 ≡ xl;

Introduzione 15

• un ciclo C e un walk composto da piu di tre archi, ha x0 ≡ xl ed ogni vertice distinto.

Definizione 1.2.9 Dato un grafo G, un insieme di cammini {P 1, P 2, . . . P k} si dice indi-

pendente (o internamente disgiunto) se per ogni coppia di cammini, gli unici vertici

in comune sono i terminali, ovvero sono dei {x, y}-path se V (P i)∩V (P j) = {x, y}, ∀i 6= j.

Esempio 1.2.1 Dato il grafo in Figura 1.16, un walk e {abcebc}, un trail e {abcebf}, un

trail chiuso e {abcebfea}, un path e {abcdef} ed, infine, un ciclo e {abcdefa}.

a

b

c

d

e

f

Figura 1.16: Grafo per l’Esempio 1.2.1

Il concetto di cammino in un grafo ci permette di introdurre un’importante proprieta

dei grafi, ovvero la connessione.

Definizione 1.2.10 Un grafo G e connesso se ogni coppia di suoi vertici appartiene ad

un cammino e sconnesso altrimenti.

Riprenderemo questo concetto nelle prossime sezioni.

1.3 Esercizi

Es. 1.3.1 Dire se e possibile disegnare un grafo in cui i gradi dei vertici siano i seguenti:

d(1) = 1; d(2) = 2; d(3) = 3; d(4) = 4; d(5) = 5.

Introduzione 16

Es. 1.3.2 E’ possibile disegnare un grafo 3-regolare con 9 vertici? Se si disegnarlo. E con

8 vertici? Se si disegnarlo.

Es. 1.3.3 Dato K6, quanti cammini ricoprenti posso fare partendo da un vertice assegnato

a?

Es. 1.3.4 Dato K4,4, quanti cammini ricoprenti posso fare partendo da un dato vertice a?

Es. 1.3.5 Si disegni una 2-fattorizzazione di K5.

Es. 1.3.6 Si mostri se e possibile disegnare una 2-fattorizzazione di K6.

Es. 1.3.7 (Difficile) Determinare il numero di 1-fattori in K2n.

Es. 1.3.8 (Difficile) Determinare il numero di 2-fattori in K2n,2n.

Capitolo 2

Algoritmi

I progressi ottenuti nel campo dell’elaborazione elettronica hanno permesso lo sviluppo e

l’applicazione dei metodi matematici per la modellizzazione e la risoluzione di una gran-

de varieta di problemi decisionali, anche di dimensioni ragguardevoli. Tutto l’insieme di

metodologie che hanno in comune l’uso del metodo matematico, come per esempio l’ot-

timizzazione, la programmazione matematica, la teoria dei grafi, la teoria delle code, la

teoria delle decisioni, la simulazione, ecc, sono raccolte in una disciplina che prende il nome

di Ricerca Operativa. Data la natura applicativa della Ricerca Operativa, lo studio teorico

del problema matematico posto viene normalmente affiancato allo studio delle tecniche

necessarie per ottenere una soluzione in modo efficiente.

2.1 Breve tassonomia dei problemi decisionali

In generale, nella modellazione di un problema decisionale, ci dobbiamo preoccupare di

tre componenti fondamentali: il grado di incertezza, il numero di obiettivi ed il numero di

decisori.

Il grado di incertezza indica se ci si trova in condizioni di informazione completa, come

nei problemi deterministici, oppure in condizioni di conoscenza parziale, come nei proble-

mi stocastici. Il numero di obiettivi e un’altra componente da conoscere e, in generale,

potremo riconoscere problemi a singolo obiettivo, oppure multiobiettivo. Analogamente,

17

Algoritmi 18

per il numero dei decisori avremo una divisione in due classi, quella dei problemi a singolo

decisore e quella dei problemi multidecisore.

Continuando con questi accenni di tassonomia dei problemi decisionali, potremo con-

siderare problemi lineari oppure problemi non lineari, a seconda della nostra funzione

obiettivo. Inoltre, sulla base dei valori che possono assumere le variabili, avremo problemi

continui se i valori apparterranno allo spazio dei numeri reali R, problemi discreti (o com-

binatori) se i valori apparterranno allo spazio dei numeri interi Z ed infine, problemi misti

se le variabili possono assumere valori sia reali che interi.

Utilizzando lo schema appena descritto, nella trattazione della teoria dei grafi ci li-

miteremo in seguito al solo studio dei problemi deterministici, singolo obiettivo, singolo

decisore, lineari e discreti. Al lettore e lasciato immaginare la quantita di problemi de-

cisionali che si possono osservare nella realta al presentarsi ed al combinarsi delle diverse

ipotesi sopra dette e, di conseguenza, come la loro analisi sia fondamentale per individuare

le tecniche piu adeguate per risolverli.

2.2 Algoritmi

Per la soluzione di un problema, occorre individuare un metodo generale (procedura) in

grado di risolvere ogni generica istanza, fornendoci la soluzione desiderata in un certo

numero di passi. Il termine generale usato per definire tali procedure e algoritmo1.

Definizione 2.2.1 Un algoritmo e una procedura definita usata per risolvere un problema

usando un numero finito di passi.

Gli algoritmi ricopriranno una grande importanza nel nostro studio della Teoria dei

Grafi e, quindi, dedicheremo le prossime pagine alla descrizione di alcuni strumenti per la

loro analisi.

Esempio 2.2.1 Descrivere un algoritmo per trovare l’elemento piu grande in una sequenza

(lista) di interi.

1Il termine algoritmo deriva dal nome del matematico persiano Abu Ja’far Mohammed ibn Musa al-Khowarizmi, vissuto nel IX secolo d.C..

Algoritmi 19

Per specificare la procedura di risoluzione di questo semplice problema possiamo utilizzare

molti metodi, ma uno dei piu semplici e quello di utilizzare il linguaggio naturale per

descrivere i singoli passi della procedura. Per risolvere il problema devono essere eseguiti

i seguenti passi:

Step 1: Poni il massimo temporaneo uguale al primo intero della sequenza;

Step 2: Compara il prossimo intero nella sequenza. Se e piu grande, poni il massimo

temporaneo pari a tale valore;

Step 3: Ripetere il passo precedente per ogni altro elemento della lista;

Step 4: Stop se non ci sono altri interi. Il valore cercato e contenuto nel massimo temporaneo

(che diventa definitivo).

Per descrivere piu efficacemente un algoritmo si puo utilizzare una descrizione me-

diante pseudocodice, basata su una sintassi molto simile al linguaggio di programma-

zione PASCAL, di facile comprensione per chiunque abbia dei rudimenti di Fondamen-

ti di Informatica. Essa inoltre ci permette di evitare le specificita di un linguaggio di

programmazione.

Utilizzando lo pseudocodice, il nostro algoritmo diventa:

procedure MAX(a1, . . . , an; integers)

max := a1

for i := 2 to nif max < ai then max := ai

max contiene il massimo

Come e facile notare, l’algoritmo in pseudocodice segue fedelmente i passi sopra de-

scritti.

Per poter fornire una soluzione significativa, gli algoritmi devono rispettare alcune

proprieta:

Proprieta 2.2.1 Un algoritmo deve soddisfare le seguenti proprieta:

Algoritmi 20

• Input - L’algoritmo deve avere un input contenuto in un insieme definito I.

• Output - Da ogni insieme di valori in input, l’algoritmo produce un insieme di valori

in uscita che comprende la soluzione.

• Determinatezza - I passi dell’algoritmo devono essere definiti precisamente.

• Finitezza - Un algoritmo deve produrre la soluzione in un numero di passi finito

(eventualmente molto grande) per ogni possibile input definito su I.

• Efficacia - Deve essere possibile effettuare ogni passo dell’algoritmo esattamente ed

in un tempo finito.

• Generalita - L’algoritmo deve essere valido per ogni insieme di dati contenuti in Ie non solo per alcuni.

Oltre a queste proprieta, un algoritmo deve essere efficiente , ovvero, dato un input di

dimensione fissata, deve fornire una soluzione in un tempo ragionevole ed inoltre deve occu-

pare una quantita limitata di memoria di un computer. Problematiche di questo tipo sono

trattate dall’analisi della complessita computazionale degli algoritmi; in particolare,

se l’oggetto dello studio e il tempo di elaborazione, parleremo di complessita tempora-

le , mentre se l’oggetto e l’occupazione della memoria, allora parleremo di complessita

spaziale .

E chiaro quindi che nell’analisi di un algoritmo e di fondamentale importanza sapere se

risolvera il nostro problema in un microsecondo, in un ora o in un secolo. Analogamente,

e importante sapere se l’occupazione di memoria possa eccedere le capacita disponibili.

L’analisi della complessita spaziale coinvolge principalmente l’analisi delle strutture dati

e, quindi, esula dagli scopi di queste note. Viceversa, l’analisi della complessita temporale

e molto importante per gli algoritmi su grafo e sara approfondita nella Sezione 2.4.

2.2.1 Algoritmi di ricerca

In questa sezione vedremo alcuni esempi di algoritmi ed in particolare ci concentriamo sugli

algoritmi di ricerca su stringa che abbiamo gia introdotto nell’Esempio 2.2.1.

Algoritmi 21

Gli algoritmi di ricerca rivestono un particolare interesse nella pratica; basti pensare

alla necessita di trovare una parola in un dizionario, un dato in un database o anche alla

ricerca di pagine web attraverso i motori di ricerca. In quest’ultimo caso, l’algoritmo di

ricerca presenta, ovviamente, complessita ben diverse.

Il primo algoritmo che introduciamo e l’algoritmo di ricerca lineare (o sequenzia-

le): data una lista di elementi distinti a1, a2 . . . , an, localizzare l’elemento x o affermare

che non c’e.

procedure LINEAR SEARCH (x, integer; a1, . . . , an, distinct integers)

i := 1while (i ≤ n AND x 6= ai)

i := i + 1if i ≤ n then

posizione := ielse

posizione := 0

L’algoritmo inizia confrontando x con a1. Se l’elemento non e stato individuato, si

incrementa il contatore i e quindi si continua fino a che una delle due condizioni risulta

falsa (cioe o sono arrivato alla fine della lista, o ho trovato l’elemento) ed il ciclo while

termina. L’istruzione condizionale if ha il compito di inserire nella variabile di output il

valore della posizione o il valore 0 se tale valore non e nella lista.

Il secondo algoritmo di ricerca che descriviamo e l’algoritmo di ricerca binaria:

data una lista di elementi distinti a1, a2 . . . , an, ordinati in modo che a1 ≤ a2 ≤ . . . ≤ an,

localizzare l’elemento x o affermare che non c’e.

La differenza in questo caso e che la sequenza e ordinata in modo crescente, come

per esempio puo accadere in un vocabolario se il criterio adottato e quello lessicografico.

Supponiamo allora che sia assegnata la sequenza {1, 2, 4, 5, 6, 9, 10, 12, 15, 18, 20, 24} e che

si voglia trovare se il numero 18 appartiene a tale lista.

L’idea che sta alla base dell’algoritmo e quella di dividere ad ogni passo la lista in due

parti (nel nostro caso {1, 2, 4, 5, 6, 9} e {10, 12, 15, 18, 20, 24}) e confrontare l’elemento da

cercare rispettivamente con l’ultimo elemento della prima meta e con il primo elemento

della seconda meta. Nel nostro caso l’elemento e piu grande del primo elemento della

Algoritmi 22

seconda meta e quindi possiamo concentrarci solo in tale stringa per la ricerca. L’algoritmo

continua dividendo tale stringa ulteriormente, ottenendo pertanto {10, 12, 15} e {18, 20, 24}ed eseguendo di nuovo i confronti. Cosı facendo l’algoritmo genera ancora le stringhe {18}e {20, 24} arrestandosi al valore cercato oppure affermando che non appartiene a tale lista.

Lo pseudocodice dell’algoritmo proposto e il seguente:

procedure BINARY SEARCH (x, integer; a1, . . . , an, increasing integers)

i := 1j := nwhile (i < j )

begin

m := ⌊ i+j

2⌋

if x > am then

i := m + 1else

j := mend

if x = ai then

posizione := ielse

posizione := 0

L’apparente complessita dell’algoritmo di ricerca binaria, rispetto a quello lineare,

nasconde dei benefici che saranno mostrati nel paragrafo 2.4.

2.3 Crescita di funzioni

Nell’analisi di un algoritmo e di particolare interesse comprendere la sua applicabilita pra-

tica e, principalmente, capire il tempo necessario per ottenere un risultato utile, ovvero la

sua efficienza. Osservando gli algoritmi presentati nella sezione precedente, si puo notare

come l’input sia sempre legato al numero n di oggetti in ingresso sui quali eseguire l’elabo-

razione. Ci potremmo quindi chiedere quanto cresce il tempo di elaborazione al crescere di

n e se e possibile trovare una funzione f(n) che sia in grado di trasferire questa informa-

zione. Inoltre, sarebbe utile disporre di un criterio in grado di paragonare due algoritmi

confrontando la crescita delle rispettive funzioni dell’input.

Algoritmi 23

2.3.1 Notazione Big-O

Per analizzare il comportamento degli algoritmi dobbiamo prima introdurre la notazione

Big-O , necessaria per lo studio della crescita di una funzione generica, di cui segue la

definizione:

Definizione 2.3.1 Siano f e g due funzioni tali che f, g : N → R (o anche f, g : R → R).

Diremo che f(n) = O(g(n)) se esistono due costanti, C e k, tali che ∀n > k si ha:

f(n) ≤ C|g(n)| (2.1)

La 2.1 si legge come “f(n) e un big o di g(n)”.

E importante notare che basta trovare una sola coppia C, k tale che sia vera la 2.1. In

realta, una coppia che soddisfa la definizione data non e mai unica, anzi, basta prendere

una qualunque coppia C ′, k′ tale che C < C ′ e k < k′ per soddisfare la definizione e questo

ci porta a dire che se una coppia esiste, allora ne esistono infinite.

Esempio 2.3.1 Mostrare che f(n) = n2 + 2n + 1 e un O(n2).

Per risolvere questo esercizio basta osservare che 0 ≤ n2 + 2n + 1 ≤ n2 + 2n2 + n2 = 4n2,

avendo considerato C = 4 e k = 1. Notare che in questo caso si ha che f(n) ≤ C|g(n)| e

g(n) ≤ C|f(n)|. Quando cio accade diremo che le funzioni sono dello stesso ordine.

Occorre notare che il segno di uguale nella 2.1 non e realmente un uguale, ma, piuttosto,

indica che in questa notazione, quando si hanno dei valori di n sufficientemente grandi nei

dominii di f e g, la disuguaglianza e verificata.

Se f(n) ≤ C|g(n)| e h(n) e una ulteriore funzione che assume valori assoluti maggiori

di g(n) a partire da valori di n sufficientemente grandi, allora si ha ovviamente che f(n) ≤C|h(n)|. Di norma, pero, si sceglie la funzione g piu piccola possibile; quindi nell’esempio

precedente e corretto, ma privo di senso, dire che f(n) = O(n3).

Esempio 2.3.2 Dare una stima Big-O della somma dei primi numeri n interi positivi.

Algoritmi 24

Dato che 1 + 2 + . . . + n ≤ n + n + . . . + n = n2, allora 1 + 2 + . . . + n = O(n2), con C = 1

e k = 1.

Esempio 2.3.3 Dare una stima Big-O di f(n) = log n!.

Per quanto riguarda il fattoriale si ha che 1 · 2 · . . . · n ≤ n · n · . . . · n = nn. Quindi

log n! ≤ log nn = n log n, che implica log n! = O(n log n).

2.3.2 Crescita di combinazioni di funzioni

Gli algoritmi sono tipicamente composti da diverse operazioni concatenate ed annidate in

sottoprocedure, quindi la notazione introdotta nel paragrafo precedente deve essere estesa

in modo da tenere conto del peso delle singole sottoprocedure.

Supponiamo allora di avere assegnate due funzioni f1(n) = O(g1(n)) e f2(n) = O(g2(n)).

Per la definizione data nel paragrafo precedente sappiamo che esistono delle costanti C1,

C2, k1 e k2 tali che f1(n) ≤ C1|g1(n)|, ∀n > k1 e f2(n) ≤ C2|g2(n)|, ∀n > k2.

Teorema 2.3.1 Si supponga che f1(n) = O(g1(n)) e f2(n) = O(g2(n)). Allora la somma

delle due funzioni e:

(f1 + f2)(n) = O(max{g1(n), g2(n)}) (2.2)

Dimostrazione: Si noti che |(f1+f2)(n)| = |f1(n)+f2(n)| ≤ |f1(n)|+|f2(n)| (quest’ultima

relazione e vera per la disuguaglianza triangolare, |x + y| ≤ |x| + |y|).Se si considera g(n) = max{g1(n), g2(n)} e C = C1 + C2, allora |f1(n)| + |f2(n)| ≤

C1|g1(n)| + C2|g2(n)| ≤ C|g(n)|.

Corollario 2.3.2 Se entrambe le funzioni f1(n) e f2(n) sono entrambe O(g(n)), allora

(f1 + f2)(n) = O(g(n)).

Per quanto riguarda il prodotto di funzioni, vale il seguente teorema:

Algoritmi 25

Teorema 2.3.3 Si supponga che f1(n) = O(g1(n)) e f2(n) = O(g2(n)). Allora il prodotto

delle due funzioni e:

(f1 · f2)(n) = O(g1(n) · g2(n)) (2.3)

Dimostrazione: Considerando C = C1 · C2, allora (f1 · f2)(n) = |f1(n)| · |f2(n)| ≤C1|g1(n)| · C2|g2(n)| ≤ C|(g1 · g2)(n)|.

Esempio 2.3.4 Dare una stima Big-O della funzione f(n) = 3n log(n!) + (n2 + 3) log n.

Considerando ogni termine singolarmente abbiamo:

f(n) = 3n → n

log n! → n log n

+(n2 + 3) → n2 + 3 ≤ 4n2

log n → log n

Quindi f(n) = O(n2 log n).

L’ultimo risultato di questa sezione riguarda la crescita di funzioni polinomiali (in x,

per comodita di notazione):

Teorema 2.3.4 Sia f(x) = anxn + an−1x

n−1 + . . . + a0, con an, an−1 . . . , a0 numeri reali.

Allora f(x) = O(xn).

Dimostrazione: Utilizzando la disuguaglianza triangolare, e per x > 1,

|f(x)| = |anxn + an−1x

n−1 + . . . + a0|

≤ |an|xn + |an−1|xn−1 + . . . + |a0|

= xn(|an| +|an−1|

x+ . . . +

|a0|xn

)

≤ xn(|an| + |an−1| + . . . + |a0|)

Questo dimostra che |f(x)| < Cxn, dove C = |an| + |an−1| + . . . + |a0|, se x > 1. Quindi

f(x) = O(xn).

Algoritmi 26

Come abbiamo detto, la notazione Big-O viene usata per la stima del numero di ope-

razioni necessarie affinche un algoritmo risolva un dato problema. Le funzioni che normal-

mente si usano sono 1, log n, n, n log n, n2, 2n, n!. La sequenza presentata non e casuale, ma

rispetta l’ordinamento tale per cui la funzione successiva e sempre piu grande di quella che

la precede. In Figura 2.1 sono riportati i grafici delle funzioni indicate, dove n sia l’ascisse

e in ordinata siano i valori della funzione, in scala esponenzialmente crescente.

n!

2

1

4

2

8

16

32

64

128

256

512

1024

2048

1

log n

3 4 5 6 87

n log n

n

n2

2n

Figura 2.1: Grafico delle funzioni piu comunemente usate nella stima Big-O

2.4 Complessita degli algoritmi

L’analisi della complessita temporale degli algoritmi puo essere espressa in termini di nu-

mero di operazioni eseguite dallo specifico algoritmo quando l’input ha un data dimensione.

Questo tipo di analisi risulta essere piu efficiente della semplice misura del tempo impie-

gato da un computer per completare la sua elaborazione, perche, nel caso, la velocita di

elaborazione puo variare molto da computer a computer ed e inoltre difficile da misurare

e valutare.

Algoritmi 27

Per illustrare come analizzare la complessita di un algoritmo, consideriamo il primo

esempio della Sezione 2.2 per trovare l’elemento piu grande in una lista. Le operazioni

che sono eseguite sono i due confronti all’interno del ciclo for, uno per verificare se si e

giunti alla fine della lista, l’altro per aggiornare, eventualmente, il massimo temporaneo.

Dato che i due confronti vengono ripetuti dal passo due al passo n ed e poi eseguito

un’ulteriore confronto per uscire dal ciclo quando il contatore i = n + 1, si ha che sono

eseguiti esattamente 2(n − 1) + 1 = 2n − 1 confronti. Quindi, dato un input di lunghezza

n, se si misura la complessita in termini di confronti, si ha che l’algoritmo trova il massimo

in una lista di lunghezza n in O(n) passi.

Questo ragionamento ci ha portato ad usare la notazione Big-O introdotta nella sezione

precedente per dare una misura della complessita computazionale temporale dell’algoritmo.

Questa procedura puo essere generalizzata allo studio dell’efficienza di qualunque algoritmo

e, negli esempi che seguono, mostreremo come usare tale misura e come sia possibile servirsi

della composizione delle funzioni per valutare la complessita generata da piu procedure o

da procedure annidate.

Prendendo ad esempio l’algoritmo di ricerca lineare, all’interno del ciclo while vengono

effettuati due confronti: uno per verificare se si e arrivati alla fine della lista e l’altro per

confrontare x con un termine della lista. Successivamente viene eseguito un confronto fuori

dal ciclo. Considerando il caso peggiore, ovvero quello in cui l’elemento non e contenuto

nella lista, sono eseguiti 2n + 2 confronti e quindi la ricerca lineare richiede almeno O(n)

confronti.

Il tipo di analisi eseguita sull’algoritmo di ricerca lineare e del tipo worst case , ovvero

viene contato il massimo numero di operazioni necessarie per risolvere il nostro problema

dato un input fissato. Ovviamente, quest’analisi mostra quante operazioni sono necessarie

all’algoritmo, nel caso peggiore, per garantire che verra prodotta una soluzione, ma nella

realta possono esserne effettuate molte di meno. A titolo di esempio, si puo notare che

l’algoritmo di ricerca lineare ha complessita proporzionale a n, ma se l’elemento da ricercare

e tra i primi nella lista, l’algoritmo termina con un numero di passi minore.

Analizziamo ora l’algoritmo di ricerca binaria e, per semplicita, supponiamo che la lista

Algoritmi 28

Complessita Terminologia

O(1) Complessita costanteO(log n) Complessita logaritmicaO(n) Complessita lineareO(n log n) Complessita n log nO(na) Complessita polinomialeO(an), con a > 1 Complessita esponenzialeO(n!) Complessita fattoriale

Tabella 2.1: Terminologia comunemente usata per indicare la complessita degli algoritmi

sia composta da n = 2k elementi (e, quindi, k = log n). Notare che con questa ipotesi non

c’e perdita di generalita, perche potremmo considerare la nostra lista originale come parte

di una lista piu grande di 2k+1 elementi, dove 2k ≤ n ≤ 2k+1. Ad ogni passo dell’algoritmo,

le variabili i e j sono confrontate per vedere se la lista ristretta ha piu di un termine e, se

i < j, viene eseguito un confronto per determinare se x e maggiore del termine mediano

della lista in considerazione. Al primo passo, la ricerca e limitata a 2k−1 termini e vengono

effettuati due confronti; ad ogni passo successivo vengono eseguiti due confronti su di una

lista che e grande la meta di quella del passo precedente. Alla fine del ciclo while vengono

eseguiti due ulteriori confronti e quindi complessivamente saranno stati eseguiti al piu 2k+2

confronti, ovvero 2 ⌊log n⌋ + 2 confronti. Quindi, l’algoritmo di ricerca binaria richiede al

piu O(log n) confronti, e da cio segue che tale algoritmo, a parita di input, e molto piu

efficiente dell’algoritmo di ricerca lineare.

In Tabella 2.1 e riportata la terminologia comunemente usata per indicare la complessita

temporale degli algoritmi. La stima Big-O permette di valutare come il tempo necessario

per risolvere un problema cambi in funzione della dimensione dell’input. Tale stima pero

non fornisce indicazioni sul tempo realmente necessario ad un computer per completare

l’elaborazione perche non possiamo individuare un valore limite senza aver ricavato le

costanti C e k nell’equazione 2.1 ed inoltre perche e difficile stimare il tempo richiesto per

completare una singola operazione. Comunque, possiamo tentare di fornire una misura

riconducendoci a delle stime sui tempi di operazione sui bit2. Cosı facendo, possiamo

2Nel nostro caso si e assunto che il tempo di elaborazione di una operazione base su bit, eseguita su uncomputer ad alte prestazioni, sia di 10−9 secondi.

Algoritmi 29

Dimensione Numero di operazioni su bit eseguitedel problema

n log n n n log n n2 2n n!10 3 · 10−9 sec 10−8 sec 3 · 10−8 sec 10−7 sec 10−6 sec 3 · 10−3sec102 7 · 10−9 sec 10−7 sec 7 · 10−7 sec 10−5 sec 4 · 1013 anni ∗103 1 · 10−8 sec 10−6 sec 1 · 10−5 sec 10−3 sec ∗ ∗104 1.3 · 10−8 sec 10−5 sec 1 · 10−4 sec 10−1 sec ∗ ∗105 1.7 · 10−8 sec 10−4 sec 2 · 10−2 sec 10 sec ∗ ∗106 7 · 10−8 sec 10−3 sec 3 · 10−2 sec 17 min ∗ ∗

Tabella 2.2: Tempo di calcolo usato dagli algoritmi

ottenere la Tabella 2.2 che riporta i tempi computazionali necessari a problemi con diverse

dimensioni di input, fornendo inoltre una indicazione sul numero di operazioni su bit. Gli

asterischi indicano tempi maggiori di 10100 anni.

La tabella riporta tempi computazionali che possono risultare impraticabili anche per

istanze piccole. Ci si potrebbe chiedere quale vantaggio si avrebbe con l’aumento delle pre-

stazioni degli elaboratori. Dall’esempio seguente e facile convincersi che questa possibilita

non ha riscontro nella realta.

Supponiamo di considerare due algoritmi, uno di complessita polinomiale O(n2) e l’altro

di complessita esponenziale O(2n). Consideriamo ora un elaboratore che abbia velocita v1

e che ci permetta di risolvere in una data unita di tempo una istanza di dimensione n1.

Immaginiamo ora di poter disporre di un elaboratore 100 volte piu veloce (v2 = 100 · v1);

considerando la complessita dell’algoritmo, si puo affermare che esiste una proporzionalita

pari a n22/n

21 = v2/v1 = 100 e quindi, con un rapido conto, si ottiene che e possibile risolvere

nello stesso tempo istanze con n2 = 10 · n1, cioe 10 volte piu grandi.

Applicando lo stesso ragionamento per l’algoritmo di complessita O(2n), si ottiene,

con un elaboratore 100 volte piu veloce, che 2n2/2n1 = v2/v1 = 100, ovvero che n2 =

n1 + log 100 ≈ n1 + 7, cioe posso risolvere istanze con solo 7 nodi in piu!

Questo esempio ci mostra come il miglioramento delle capacita di elaborazione ha

purtroppo solo un impatto marginale nella efficienza degli algoritmi con complessita

esponenziale.

Algoritmi 30

2.5 Esercizi

Es. 2.5.1 Mostrare che l’algoritmo dell’Esempio 2.2.1 rispetta le Proprieta 2.2.1

Es. 2.5.2 Fornire una stima Big-O della seguente funzione: f(n) = n2 + nlog n

log n!.

Es. 2.5.3 Fornire una stima Big-O della seguente funzione: f(n) = 13 + 23 + . . . + n3.

Es. 2.5.4 Fornire una stima Big-O della seguente funzione: f(n) =√

1 +√

2 + . . . +√

n.

Es. 2.5.5 Fornire una stima Big-O della seguente funzione: f(n) = log 2 + log 3 + . . . +

log n.

Es. 2.5.6 Dare una stima Big-O per f(n) = n2(n log(n!) + n log n).

Es. 2.5.7 Dare una stima Big-O per f(n) = (log n)2 + log(n2).

Es. 2.5.8 Determinare la complessita computazionale associabile al seguente segmento di

codice (n << m):

while (j < m) do

begin

for i := 1 to m do

if a[i] < j then a[i] = j;

for i := 1 to n do


j = j + 1;

end

Es. 2.5.9 Determinare la complessita computazionale associabile al seguente segmento di

codice (m << n):

for i := 1 to m do

begin

Algoritmi 31


for i := 1 to n do


j = j + 1;

end

Es. 2.5.10

Capitolo 3

Proprieta e strutture dei grafi

3.1 Strutture dati per la rappresentazione di grafi

La performance di un algoritmo su grafo dipende non solo dall’algoritmo stesso, cosı come

e stato descritto nella sezione precedente, ma anche dal modo con il quale il grafo viene

memorizzato e da come vengono gestiti gli aggiornamenti ed i risultati parziali.

Tipicamente, nella rappresentazione di un grafo occorre memorizzare due tipi di infor-

mazioni: la topologia dei nodi e degli archi, quindi eventuali grandezze da associare ai nodi

e agli archi stessi(queste informazioni saranno necessarie soprattutto per gli algoritmi che

approfondiremo nelle prossime sezioni).

Prima di introdurre le diverse tipologie di rappresentazione, si vuole estendere e ge-

neralizzare il concetto di grafo finora esposto al caso in cui gli archi siano orientati. La

definizione e simile alla Definizione 1.1.1:

Definizione 3.1.1 Un grafo orientato G e una tripla costituita da un insieme di ver-

tici V (G) (detti anche nodi), un insieme di archi orientati E(G) e una relazione, detta

relazione di incidenza, che associa un vertice ad un altro.

Risulta chiaro allora che nel caso di grafi orientati non e piu corretto affermare che

e = ab e la stessa cosa di scrivere e = ba, perche la relazione di incidenza e vera solo

in un verso. In ogni caso pero, tutte le definizioni di walk, trail, path, ecc che abbiamo

32

Proprieta e strutture dei grafi 33

dato nel Capitolo 1, si estendono immediatamente al caso dei grafi orientati avendo cura

di considerare in modo stringente l’orientamento nelle varie tipologie di cammini (e cicli).

5

a

c

b

f

e g h

d2

1

3

4

Figura 3.1: Grafo non orientato

a

c

b

f

e

d2

1

3

4

5

g h

Figura 3.2: Grafo orientato

Le rappresentazioni dei grafi che studieremo sono la matrice di incidenza, la matrice di

adiacenza e la lista di adiacenza.

Matrice di incidenza

La rappresentazione attraverso la matrice di incidenza di un grafo non orientato G di n

nodi ed m archi avviene attraverso una matrice A di dimensione n × m che contiene una

riga per ogni nodo del grafo ed una colonna per ogni arco. La colonna corrispondente

all’arco (i, j) ha soltanto due elementi diversi da zero in corrispondenza dei nodi i e j.

Prendendo il grafo disegnato in Figura 3.1, la sua matrice di incidenza corrispondente e:

A =

1 1 0 0 0 0 0 0

1 0 1 1 0 0 0 0

0 1 1 0 1 1 0 0

0 0 0 1 1 0 1 1

0 0 0 0 0 1 1 1

La matrice di incidenza ha una struttura tipica per cui solo 2m componenti, delle n×m,

sono diverse da zero ed uguali ad uno. E da notare che la somma degli elementi diversi da

zero in una riga eguaglia il grado del nodo corrispondente, ovvero:


d(vi) =m

∑

j=1

aij

dove chiaramente aij e l’elemento della riga i-esima e colonna j-esima.

Nel caso di un grafo orientato la matrice di incidenza si modifica considerando che per

l’h-esimo arco (i, j), nella colonna h corrispondente, l’elemento aih e uguale ad 1 mentre

l’elemento ajh e uguale a −1. Di conseguenza, per il grafo in Figura 3.2 la matrice e:

A =

1 1 0 0 0 0 0 0

−1 0 −1 1 0 0 0 0

0 −1 1 0 1 1 0 0

0 0 0 −1 −1 0 −1 1

0 0 0 0 0 −1 1 −1

La rappresentazione di un grafo tramite la matrice di incidenza e chiaramente non

efficiente a causa dello spazio necessario per la sua memorizzazione su un elaboratore, so-

prattutto al crescere di n e della densita. Nonostante cio, questa rappresentazione e di

grande importanza perche come vedremo nelle prossime sezioni, oltre a possedere interes-

santi proprieta teoriche, essa coincide con la matrice dei coefficienti della formulazione dei

problemi di flusso a costo minimo.

Matrice di adiacenza

La rappresentazione attraverso la matrice di adiacenza di un grafo non orientato G di n

nodi ed m archi avviene attraverso una matrice A di dimensione n × n dove ogni riga

ed ogni colonna corrispondono ai nodi e gli elementi della matrice aij sono o 0, se non

esiste l’arco (i, j) corrispondente, oppure sono uguali alla somma del numero di archi che

uniscono i nodi (i, j). Quindi, se riprendiamo l’esempio in Figura 3.1, la sua matrice di

adiacenza e:


A =

0 1 1 0 0

1 0 1 1 0

1 1 0 1 1

0 1 1 0 2

0 0 1 2 0

La matrice di adiacenza per i grafi non orientati e simmetrica ed ha n2 elementi. Conse-

guentemente, questa rappresentazione e efficiente solo se il grafo e significativamente denso,

mentre per grafi sparsi si ha un notevole spreco di memoria.

Analizzando la matrice di adiacenza, si puo contare il numero di archi incidenti sul

nodo i semplicemente sommando gli elementi della riga i-esima (quindi d(v5) = 3, pari alla

somma del contributo dell’arco adiacente al nodo 3 e dei due archi adiacenti al nodo 4).

Analogamente, il numero di archi incidenti su un nodo j si ottiene sommando gli elementi

della colonna j-esima. Da questo ne consegue che la somma di tutti gli elementi diversi da

zero della matrice di adiacenza e uguale a 2m.

Nel caso di grafi orientati, invece, la matrice di adiacenza perdela sua caratteristica di

simmetria e, per il grafo in Figura 3.2, diventa:

A =

0 1 1 0 0

0 0 0 1 0

0 1 0 1 1

0 0 0 0 1

0 0 0 1 0

Nella matrice di adiacenza nel caso di grafi orientati e possibile contare il numero di

archi uscenti da un nodo i (tale insieme e chiamato anche stella uscente) sommando gli

elementi della riga corrispondente, mentre il numero di archi entranti in un nodo i (tale

insieme e chiamato anche stella entrante) si ottiene sommando gli elementi della colonna

corrispondente. Da questo ne consegue che gli elementi diversi da zero sono uguali a m.


Lista di adiacenza

La lista di adiacenza dei nodi A(i) di un grafo G con n nodi, e un vettore di dimensione n nel

quale ogni cella i punta una lista che contiene l’insieme dei nodi j tali per cui (i, j) ∈ E(G).

In Figura 3.3 e rappresentata la lista di adiacenza del grafo in Figura 3.2.

La lista di adiacenza di un grafo e molto utile quando, agli archi ed ai nodi, assoce-

remo dei numeri che ne rappresenteranno il costo, la lunghezza, ecc, come illustreremo

nei prossimi Capitoli. Infatti, mediante questa rappresentazione vedremo che sara suffi-

ciente aumentare, per ogni cella puntata dal nodo, i campi della lista corrispondente per

memorizzare tutte le informazioni necessarie.

Figura 3.3: Lista di adiacenza per il grafo di Figura 3.2.

3.2 Isomorfismo tra grafi

Osservando la matrice di adiacenza per i grafi non orientati, si puo notare come si introduca

implicitamente un ordinamento dei vertici per riga. In realta, quello che si vuole e ottenere

delle proprieta che non siano funzione di tale ordinamento. Intuitivamente, si puo dire che

si vorrebbero trovare due diverse rappresentazioni matriciali del grafo G tali per cui siano

preservate le relazioni di adiacenza.

Definizione 3.2.1 Due grafi G = (V,E) e G′ = (V ′, E ′) si dicono isomorfi, e si scrive

G ∼= G′, se esiste una corrispondenza biunivoca tra i due insiemi di vertici, cioe se esiste

una biiezione Φ : V → V ′ tale che xy ∈ E ⇔ φ(x)φ(y) ∈ E ′.


Per esempio, se prendiamo le matrici di adiacenza dei due grafi G e G′, rappresentati

in Figura 3.4, possiamo notare che e facile individuare una funzione biiettiva che mette in

corrispondenza i vertici dei due grafi e che le due matrici si trasformano l’una nell’altra

mediante permutazioni delle righe e delle colonne. Al lettore e lasciato per esercizio di

trascrivere le due matrici e di trovare la funzione Φ che permette di passare da una matrice

all’altra.

G G′

b c 3 4

1 2

d

a

Figura 3.4: Esempio di due grafi isomorfi

Dati due grafi generici G e H ci possiamo chiedere ora come verificare che siano tra

di loro isomorfi. Alcune condizioni necessarie possono essere facilmente individuate; per

esempio i due grafi devono avere stessi ordine e dimensione, oppure l’immagine di un vertice

i ∈ G deve avere in H lo stesso grado dell’immagine i ∈ H in G.

In generale pero lo studio esaustivo delle permutazioni delle matrici di adiacenza di due

grafi di ordine n non costituisce un algoritmo molto efficiente, perche questo avrebbe una

complessita computazionale di O(n!). Dato il grande interesse che il problema dell’isomor-

fismo tra grafi riveste nelle applicazioni pratiche, sono stati proposti molti algoritmi per

tentare di risolverlo, ma esso rimane ancora aperto, nel senso che non e ancora stato pro-

posto un algoritmo efficiente ne si e riuscito a dimostrare che tale algoritmo possa esistere

oppure no [6].

Esempio 3.2.1 Siano assegnati i due grafi in Figura 3.5. Dimostrare che sono tra loro

isomorfi.

Sia definita la funzione Φ : V (G) → V (H) tale che φ(w) = a, φ(x) = c, φ(y) = b

e φ(z) = d. Per mostrare che Φ e un isomorfismo occorre analizzare se tali funzioni


HG

ab

c dw z

yx

Figura 3.5: Due grafi isomorfi

preservino le adiacenze, e questo puo essere testato riscrivendo la matrice A(G) in modo

che permutando righe e colonne si ottenga la matrice A(H).

Nel nostro caso si puo notare come, permutando tra di loro la seconda e la terza colonna

di A(G) e poi la terza e la quarta (e la stessa cosa si fa per le righe), si ottiene la matrice

del grafo H, dimostrando quindi l’isomorfismo tra i due grafi. Per esteso:

A(G) =

0 1 0 0

1 0 1 0

0 1 0 1

0 0 1 0

→

0 0 0 1

0 0 1 1

0 1 0 0

1 1 0 0

→

0 0 0 1

0 0 1 1

0 1 0 0

1 1 0 0

= A(H)

Classi di isomorfismo

Il concetto di isomorfismo visto come “G e H sono isomorfi” ha un valore limitato se non

lo estendiamo all’applicazione su insiemi di grafi che siano tra loro isomorfi.

Ricordando che una relazione su un insieme I e una collezione di coppie ordinate

di suoi elementi e una relazione di equivalenza e una relazione riflessiva (a ∼= a),

simmetrica (a ∼= b ⇔ b ∼= a) e transitiva (a ∼= b, b ∼= c,⇒ a ∼= c), possiamo affermare che:

Proposizione 3.2.1 La relazione di isomorfismo e una relazione di equivalenza.

Dimostrazione: Lasciata per esercizio al lettore.


Una relazione di equivalenza partiziona un insieme in classi di equivalenza e quindi

due elementi appartengono alla stessa classe se e solo se ricadono nella stessa classe di

equivalenza.

Definizione 3.2.2 Una classe di isomorfismo di grafi e una classe di equivalenza di grafi

sotto una relazione di isomorfismo.

Per esempio, i grafi completi Kn costituiscono delle classi di isomorfismo di grafi perche,

prese due a due, rispettano le proprieta delle relazioni di equivalenza. Un’altra importante

classe di isomorfismo e costituita dai grafi bipartiti completi , ovvero quei grafi semplici

bipartiti tali che due vertici sono adiacenti se e soltanto se appartengono a partizioni

diverse. Se gli insiemi partizioni hanno dimensione p e q, il grafo bipartito completo e

indicato come Kp,q.

K3,3K2,3

Figura 3.6: I grafi bipartiti completi K2,3 e K3,3.

3.3 Connessione, cicli e grafi bipartiti

Nelle prossime definizioni ci dirigeremo verso le classi di equivalenza delle relazioni di

connessione limitandoci al caso dei grafi non orientati. Riprendendo i concetti definiti alla

fine della Sezione 1.2.4, diremo che un sottografo connesso di G e massimale se e connesso

e non e contenuto in nessun altro sottografo connesso di G.

Definizione 3.3.1 Dato un grafo G, le sue componenti connesse sono i suoi sottografi

connessi massimali.

In Figura 3.7 e rappresentato un grafo con quattro componenti connesse, {a, b},{c, d, e, f}, {g} e {h, i, j, }. Come si puo notare, la componente connessa {g} e costituita

da un solo nodo e viene chiamata anche componente triviale.


a c e f ji

hgdb

Figura 3.7: Un grafo con quattro componenti connesse.

Definizione 3.3.2 Un cut-vertex e un vertice la cui rimozione aumenta il numero di

componenti connesse. Un bridge e un arco la cui rimozione aumenta il numero di

componenti connesse.

Quindi riprendendo la Figura 3.7, un cut-vertex e per esempio il nodo i, mentre l’arco

ij e un bridge (infatti, in entrambi i casi passo da 4 a 5 componenti connesse).

Proposizione 3.3.1 Ogni grafo G con n vertici ed m archi ha almeno n−m componenti

connesse.

Dimostrazione: Supponiamo sia assegnato un grafo con n nodi e nessun arco. In questo

caso ho esattamente n componenti connesse. Per la Definizione 3.3.2, aggiungendo un arco

diminuisco di uno il numero di componenti connesse, quindi dopo aver aggiunto m archi il

numero di componenti e diminuito a n − m.

Esempio 3.3.1 Sia G un grafo con n vertici tale che ogni suo vertice abbia grado almeno

(n − 1)/2. Mostrare che G e connesso.

Per dimostrare la connessione, ipotizziamo per assurdo che ci siano due nodi x ed y di G

appartenenti a due diverse componente connesse ed aventi grado ciascuno almeno (n−1)/2.

Sia la componente di x quella in Figura 3.8. Allora il numero di nodi di tale componente

connessa deve essere 1 + (n− 1)/2 = (n + 1)/2. Tale numero di nodi si ottiene ovviamente

anche nell’altra componente connessa.

Ora, per ottenere il numero di nodi del grafo di partenza basta sommare il numero di

nodi delle due componenti connesse, ma cosı facendo ci accorgiamo che otteniamo (n +


1)/2+(n+1)/2 = n+1, che eccede il numero di nodi di partenza di G, mostrando l’assurdo.

x

n−12

Figura 3.8: Componente connessa di x

Definizione 3.3.3 Se a e b sono due vertici appartenti alla stessa componente connessa,

allora esiste un path di lunghezza minima d(a, b) chiamato distanza.

Lemma 3.3.2 Ogni walk chiuso W di lunghezza dispari contiene un ciclo dispari.

Dimostrazione: La dimostrazione e per induzione. Per l = 1 il lemma e ovvio; per l > 1

si ponga l’ipotesi induttiva affermando che il lemma e vero per walk chiusi piu corti di W .

In questo caso si possono presentare due possibilita: se non ho walk chiusi ripetuti

allora ho gia cicli dispari ed il lemma e dimostrato; altrimenti, se ho nodi ripetuti (per

esempio il nodo i, come in Figura 3.9) allora posso spezzare W in due walk chiusi, uno di

lunghezza pari e l’altro di lunghezza dispari. Ma per il walk chiuso di lunghezza dispari

vale l’ipotesi induttiva e quindi deve contenere un ciclo di lunghezza dispari.

PariDisparii

Figura 3.9: Un circuito con un nodo ripetuto.

Le definizioni ed i teoremi che seguono caratterizzano ed esaminano la connessione nei

grafi.


Esempio 3.3.2 Sia G un grafo con n ≥ 2 vertici, n − 1 archi e senza vertici isolati.

Mostrare che G contiene almeno due vertici di grado 1.

Per il Lemma 1.1.1,∑

v d(vi) = 2m = 2n − 2, quindi ci devono essere almeno due vertici

con d(vi) = 1.

Definizione 3.3.4 Un grafo G si dice aciclico se non contiene cicli.

Lemma 3.3.3 Ogni grafo connesso G di ordine n contiene almeno n − 1 archi.

Dimostrazione: Dimostriamo il lemma per induzione. Per n = 1 il lemma e ovvio.

Per n ≥ 2, considero un vertice arbitrario v ∈ G e considero il grafo H = G \ v, non

necessariamente connesso, con Fi componenti connesse aventi ciascuna ni vertici, ovvero

n1 + n2 + . . . + nk = ni − 1. Per ipotesi induttiva, affermo che il sottografo di H indotto

su Fi ha almeno n − 1 archi.

Ora, osservo che il vertice v deve essere connesso ad ognuna delle k componenti Fi con

almeno un arco; quindi G contiene almeno (n1 − 1) + (n2 − 1) + . . . + (nk − 1) + k =

n − 1 − k + k = n − 1 archi.

Lemma 3.3.4 Ogni grafo aciclico ha, al piu, n − 1 archi.

Dimostrazione: Dimostriamo il lemma per induzione. Per n = 1 il lemma e ovvio.

Per n ≥ 2, prendo un arco xy ∈ G. Quindi il grafo H = G \ xy ha esattamente una

componente connessa in piu di G (questo perche, per ipotesi, il grafo e aciclico e quindi tra

x e y non puo esserci un altro path), ovvero, H puo essere decomposto in grafi connessi

aciclici H1, H2, . . . , Hk. Per ipotesi induttiva, affermo che ogni grafo Hi contiene al piu

ni − 1 archi, dove ni e il numero di nodi di ogni componente connessa, i = 1, . . . , k.

Allora G ha al piu (n1−1)+(n2−1)+. . .+(nk−1)+1 = (n1+n2+. . .+nk)−(k−1) ≤ n−1

archi.

Teorema 3.3.5 Sia G un grafo di ordine n. Allora due qualunque delle seguenti afferma-

zioni implicano la terza:


a) G e connesso;

b) G e aciclico;

c) G ha n − 1 archi.

Dimostrazione:

a, b ⇒ c Se G e connesso ed aciclico, allora per il Lemma 3.3.3 e per il Lemma 3.3.4 il grafo

ha esattamente n − 1 archi;

a, c ⇒ b Supponiamo G connesso e con n−1 archi e che, per assurdo, abbia un ciclo C. Allora

H = G \ xy, con xy ∈ C, e un grafo connesso di n vertici e n − 2 archi e questo

contraddice il Lemma 3.3.3;

b, c ⇒ a Supponiamo che G sia aciclico ed abbia n−1 archi. Per il Lemma 3.3.4 non ho vertici

isolati (altrimenti avrei n − 1 nodi e n − 1 archi), quindi per il Lemma 1.1.1 il grafo

G ha almeno un vertice di grado uno ed abbiamo che G \ v e un grafo aciclico con

n − 1 vertici e n − 2 archi. Per induzione, G \ v e connesso e quindi anche G.

Grafi bipartiti

L’enunciato del Lemma 3.3.2 ci tornera utile nella dimostrazione del prossimo teorema che

ci permettera di riconoscere la bipartizione di un grafo. Ricordiamo dalla Sezione 1.2.2

che un grafo G si dice bipartito se l’insieme dei suoi nodi V (G) e l’unione di due insiemi

indipendenti disgiunti V1 e V2 chiamati insiemi partizione ed ogni suo arco va da V1 a V2.

Teorema 3.3.6 Un grafo G e bipartito se e soltanto se non contiene cicli dispari.

Dimostrazione: Necessita. Sia G un grafo bipartito. Ogni walk alterna i propri archi tra

le due partizioni di nodi per cui ogni circuito deve avere un numero di archi pari, quindi

G non ha cicli dispari.


Sufficienza. Sia G un grafo senza cicli dispari. Poiche un grafo e bipartito solo e soltanto

se lo sono le sue componenti, possiamo assumere allora il grafo G connesso. Si prenda un

vertice x ∈ V e poniamo V1 = {y : d(x, y) sia pari} e V2 = V \ V1. Si puo notare allora che

non ci sono archi che uniscono due nodi in V1, altrimenti G dovrebbe contenere un ciclo

dispari. Quindi G e bipartito.

3.4 Alberi

I grafi che soddisfano le condizioni del Teorema 3.3.5 costituiscono una classe di grafi molto

particolari chiamati alberi .

Definizione 3.4.1 Un albero e un grafo connesso che non contiene cicli. Ogni vertice

di grado uno di un albero e chiamata foglia. Una foresta e un grafo le cui componenti

connesse sono alberi.

Proposizione 3.4.1 Per un albero sono vere le seguenti affermazioni:

1. Un albero con n nodi contiene n−1 archi; una foresta di ordine n e con k componenti

contiene n − k archi.

2. Un albero ha almeno due foglie.

3. Ogni coppia di nodi di un albero e connessa da un solo path.

Figura 3.10: Una foresta Figura 3.11: Un albero

Le definizioni e le preposizioni date possono essere riassunte nel seguente teorema:


Teorema 3.4.2 Dato un grafo G, le seguenti affermazioni sono equivalenti:

1. G e un albero.

2. G e connesso e se xy ∈ G, allora G − xy e sconnesso, ovvero ogni arco e un bridge.

3. G e aciclico e se x e y sono due vertici non adiacenti di G, allora G + xy contiene

un ciclo.

Il seguente corollario ci fornisce una proprieta che useremo nel seguito:

Corollario 3.4.3 Ogni grafo connesso G contiene un albero ricoprente, ovvero un albero

che contiene tutti i nodi del grafo (denominato anche spanning tree).

Dimostrazione: E sufficiente costruire un sottografo di G connesso e aciclico di n − 1

archi e che ricopre ogni nodo.

Riprenderemo lo studio di questa classe di grafi nella Sezione 5.3 dove verranno proposti

degli algoritmi per la ricerca di alberi ricoprenti.

3.5 Cammini Euleriani

In questo paragrafo risolveremo il Problema dei Ponti di Konisberg introdotto nel Capito-

lo 1 nel caso di grafi arbitrari. Quanto diremo sui cammini euleriani si estende anche ai

grafi non semplici, ovvero ai grafi che possiedono archi paralleli o cappi e che in letteratura

vengono chiamati anche multigrafi.

Definizione 3.5.1 Un trail euleriano (tour di Eulero) e un trail (trail chiuso) che

contiene ogni arco di G esattamente una volta.

Definizione 3.5.2 Un grafo e chiamato Euleriano se contiene un tour di Eulero.

Enunciamo ora il Teorema di Eulero (1736) che caratterizza i grafi Euleriani.

Teorema 3.5.1 Sia G un multigrafo connesso. Allora le seguenti affermazioni sono

equivalenti:


1. Il grafo G e euleriano.

2. Ogni vertice di G ha grado pari.

3. Gli archi di G possono essere partizionati in cicli.

Dimostrazione:

(1) ⇒ (2) Se G e euleriano, allora ogni vertice aggiunge un contributo di 2 al ciclo. Dato che

ogni arco compare esattamente una volta, ogni vertice v deve avere grado pari

(2) ⇒ (3) Supponiamo che G abbia n vertici. Dato che il grafo e connesso, ha almeno n−1 archi

per il Lemma 3.3.3, mentre per l’Esempio 3.3.2 deve avere almeno n archi; quindi per

il Lemma 3.3.4 c’e un ciclo C in G. Rimuoviamo ora C, ottenendo un nuovo grafo H

nel quale ogni vertice ha ancora grado pari. Considerando separatamente le compo-

nenti connesse di H, possiamo ripetere il ragionamento per ognuna delle componenti

e quindi, proseguendo, ci arrestiamo quando abbiamo terminato la decomposizione.

Quindi gli archi di G possono essere partizionati in cicli.

(3) ⇒ (1) Sia C uno dei cicli della partizione di E(G) in cicli. Se C e gia euleriano, abbiamo

la tesi. Altrimenti esiste un altro ciclo C ′ che ha un vertice v in comune con C.

Possiamo allora, senza perdita di generalita, considerare v come vertice di partenza

e di fine di entrambi i cicli C e C ′ in modo che CC ′ sia ancora un tour. Continuando

con la stessa procedura otteniamo un tour d’Eulero

Esempio 3.5.1 Supponiamo sia assegnata la porzione di scacchiera cosı come disegnato

nell’immagine a sinistra della Figura 3.12. Considerando che nelle quattro caselle bianche

agli angoli ci sono i quattro cavalli, sopra i due bianchi (chiamati CB) e sotto i due neri

(chiamati CN), e possibile, usando le mosse ammesse per i cavalli negli scacchi, invertire

le posizioni in modo che dopo un certo numero di mosse i due cavalli bianchi siano nelle

caselle inferiori e quelli neri nelle caselle superiori?


Per risolvere questo problema basta modellare la porzione di scacchiera con un grafo dove

i nodi sono le caselle ed un arco esiste tra due nodi se esiste un trasferimento lecito tra le

due caselle.

CN

CB CB

CN

Figura 3.12: Come spostare i quattro cavalli.

Allora, dato il grafo (rappresentato a destra in Figura 3.12), e sufficiente individuare un

cammino lungo il grafo in modo che i quattro cavalli, spostandosi, arrivino nella posizione

finale richiesta. E facile convincersi che tale percorso esiste se c’e un ciclo euleriano sul

grafo, cosa immediatamente verificabile osservando che i nodi hanno tutti grado pari.

3.6 Cammini Hamiltoniani

3.7 Esercizi

Es. 3.7.1 Date la seguente matrice di incidenza, disegnare i grafi corrispondenti:

Es. 3.7.2 Date la seguente matrice di adiacenza, disegnare i grafi corrispondenti:

A1 =

0 1 1 1 0 0 0 0

0 0 0 0 1 0 0 0

0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1

0 1 1 0 1 0 1 0

0 0 0 0 0 0 0 1

0 0 0 0 0 1 0 0

A2 =

0 1 1 1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 1

0 0 1 1 1 0 1 0

0 0 0 1 0 0 0 1

0 0 0 0 0 1 0 0

Es. 3.7.3 Mostrare che P4 e isomorfo al suo complemento.


Es. 3.7.4 Disegnare tutte le classi di isomorfismo costituite da grafi con n = 5 e m = 5,

anche non connessi.

Es. 3.7.5 Si disegnino tutte le classi di isomorfismo formate da spanning tree di K3,3.

Quante sono in tutto?

Es. 3.7.6 Si disegnino tutti le possibili classi di grafi di 4 nodi non isomorfi.

Es. 3.7.7 Si disegnino tutti le possibili classi di grafi di 6 nodi non isomorfi.

Es. 3.7.8 Quanti sono gli alberi che posso ottenere, a meno di isomorfismi, legando con

due archi i due vertici n − 1 e n al path 1, 2, . . . , n − 2 ?

Es. 3.7.9 A partire da K4, togliendo quattro archi, quanti grafi connessi posso ottenere?

E quanti sconnessi?

Es. 3.7.10 Dire quanti sono gli alberi con 4 vertici.

Es. 3.7.11 Sia assegnato un albero G con n vertici aventi grado pari a: d(v1) = d(v2) =

d(v3) = 1, d(vn) = 3 e d(v4) = d(v5) = . . . = d(vn−1) = 2 e con l’arco (2, n) ∈ E(G).

Quanti alberi diversi si possono ottenere legando gli archi in modo da soddisfare i dati

imposti?

Es. 3.7.12 Sia assegnato il grafo in figura, composto da un ciclo di n1 nodi, un ciclo di

n2 nodi e un terzo ciclo da n3 nodi, tutti e tre uniti in un solo vertice. In quanti modi

posso trovare un albero togliendo contemporaneamente tre archi, uno per ogni ciclo? (N.B.

I nodi dei cicli nel disegno sono solo indicativi, si deve considerare il caso generale).

Capitolo 4

Grafi Planari

Per facilitare la trattazione dei grafi planari iniziamo dal seguente problema: tre acerrimi

nemici hanno tre case vicine ed hanno contemporaneamente la necessita di doversi allacciare

le loro abitazioni alle forniture di energia elettrica, gas ed acqua. Per evitare qualsiasi

discussione esigono che nessuna delle connessioni di ognuno di loro si intersechi in qualunque

punto con quelle degli altri due. La situazione e rappresentata in Figura 4.1.

Il problema posto puo essere modellato mediante un grafo bipartito completo K3,3 (vedi

Figura 4.2) e quindi la domanda che ci vogliamo porre e la seguente: e possibile disegnare

K3,3 senza intersezioni tra gli archi? In questa sezione ci occuperemo della trattazione dei

grafi che possono essere disegnati su di un piano senza intersezioni tra archi e dimostreremo

che il problema dei tre nemici non ha soluzione.

elettricita

gas acqua

Figura 4.1: Il problema dei tre nemici.

50

Grafi Planari 51

elettricita

gas acqua

Figura 4.2: Connessioni per il problema dei tre nemici.

4.1 Grafi sul piano

I concetti che verranno esposti si basano sulla semplice osservazione che ogni curva chiusa

disposta su di un piano divide il piano stesso in due regioni distinte, ovvero la regione

interna alla curva e la regione esterna alla curva. Questa osservazione elementare ha senso

se ci limitiamo ad una trattazione semplice della Teoria dei Grafi, mentre, se volessimo

fornire maggiori dettagli, dovremmo introdurre concetti di topologia che esulano dagli

scopi di queste note. Il lettore che volesse approfondire questi argomenti puo trovare una

trattazione piu approfondita in [5] e [13].

Proposizione 4.1.1 K5 e K3,3 non possono essere disegnate sul piano senza intersezioni

tra archi.

Dimostrazione: Consideriamo un disegno di K5 sul piano come in Figura 4.3 e conside-

riamo un ciclo ricoprente C. Se non ci sono intersezioni, allora C e disegnato come una

curva chiusa e le corde di C possono essere disegnate fuori e dentro tale curva. Due corde

sono in conflitto se i loro estremi in C sono alternati e se cio accade e possibile disegnarne

una internamente a C ed una esternamente a C. Se il ciclo e di lunghezza cinque, due cor-

de possono essere tracciate internamente e due esternamente, ma dato che ci sono cinque

corde se ne deduce che e impossibile completare il disegno.

Grafi Planari 52

K5 K3,3

Figura 4.3: K5 e K3,3.

Analogamente, nel disegno di K3,3 della Figura 4.3 ci sono tre corde in mutuo conflitto

nel ciclo esterno di lunghezza sei e quindi la corda rimanente rende impossibile il comple-

tamento del disegno.

Definizione 4.1.1 Il disegno di un grafo G(V,E) e una funzione f definita su V ∪E tale

che f : v ∈ V → f(v), e ∈ E → f(e). Un punto f(e) ∩ f(e′) e chiamato intersezione.

Quindi, per disegno di un grafo intendiamo una funzione che assegna ad ogni vertice

v un punto f(v) del piano ed assegna ad ogni arco e di vertici u e v una curva f(e). Si

puo osservare che possiamo utilizzare G come nomenclatura sia per un grafo che per il suo

disegno; questo perche le relazioni di adiacenza sono chiaramente rispettate e, quindi, un

disegno del grafo G puo essere visto come un membro della classe di isomorfismo contente

G.

Dato un disegno di un grafo G, possiamo pensare di spostare gli archi sul piano in modo

da assicurarci che non esistano tre archi che abbiano un punto interno in comune, che un

arco contiene solo i vertici che costituiscono i suoi estremi e che non ci sono archi tra di

loro tangenti. Nel seguito considereremo solo disegni con tali proprieta.

Definizione 4.1.2 Un grafo G si definisce planare se ha un disegno senza intersezioni.

Tale disegno e un embedding planare di G. Un grafo piano e un particolare embedding

planare di un grafo planare.

Grafi Planari 53

Il termine embedding1 planare ribadisce il fatto che il disegno di un grafo G sul piano

e composto da punti del piano stesso, definiti dalla funzione f . Di conseguenza, allo stesso

grafo G possono corrispondere differenti funzioni che definiscono embedding diversi.

Un embedding planare divide il piano in parti che saranno ora oggetto del nostro studio.

Definizione 4.1.3 Un insieme aperto nel piano e un insieme A ∈ R2 tale che ∀p ∈ A,

∃r : ||p − r|| < ǫ, ǫ > 0, ⇒ r ∈ A.

Definizione 4.1.4 Una regione e un insieme aperto A che contiene una poligonale di

estremi u e v, ∀u, v ∈ A.

Definizione 4.1.5 Le facce Fi di un grafo planare sono le regioni massimali del piano

che contengono punti del piano che non sono interessati dall’embedding planare.

Sulla base di questa definizione, un grafo planare partiziona il piano in un numero di

regioni mutuamente disgiunte che sono quelle racchiuse all’interno delle poligonali dell’em-

bedding, piu la faccia esterna, ovvero la faccia illimitata costituita dalla restante parte di

piano.

F4

F1

F2F3

Figura 4.4: La facce di un grafo planare.

Per esempio, considerando l’embedding planare di Figura 4.4, questo divide il piano in

quattro regioni costituite dall’insiemi aperti con frontiera gli archi di G e che definiscono

le facce triangolari F1 e F2, la faccia quadrata F3 ed infine la faccia esterna F4.

4.2 Grafi duali

Da ogni grafo planare G e possibile costruire un grafo planare duale G∗ ad esso legato.

1In inglese il termine embedding significa incastrato, incastonato.

Grafi Planari 54

Definizione 4.2.1 Il grafo duale G∗(V ∗, E∗) di un grafo piano G(V,E) e un grafo piano

che ha i vertici corrispondenti con le facce di G, mentre i suoi archi corrispondono a quelli

di G nel seguente modo: se e = (u, v) e un arco di G con facce X da un lato e Y dall’altro,

allora i vertici dell’arco duale e∗ ∈ E∗ sono x ed y che rappresentano le facce X ed Y di

G. Il grado del vertice x ∈ V ∗ e uguale al numero di archi frontiera della faccia X di G.

x

u

v

y

e

e∗

Figura 4.5: Costruzione del duale.

La Figura 4.5 schematizza questo processo, mostrando la costruzione degli archi nel

grafo duale. Utilizzando questo metodo, si puo costruire per esempio il duale di K4 e si

puo notare come le sue quattro facce portino ad ottenere un duale che e ancora K4.

4.2.1 Proprieta dei grafi planari e Formula di Eulero

Nel processo di costruzione dei grafi duali puo verificarsi la comparsa di loop ed archi

multipli. Per esempio, la costruzione del duale (rappresentato con i vertici bianchi e archi

tratteggiati) per l’embedding in Figura 4.6 porta ad avere due vertici, uno per la faccia

interna triangolare ed uno per la faccia esterna, ed archi corrispondenti alle frontiere tra

le diverse facce.

Figura 4.6: Un esempio di grafo G e del suo duale G∗.

Grafi Planari 55

E da notare che i loop si formano in corrispondenza di un bridge dato che le facce sui

due lati sono le stesse, mentre archi multipli si hanno in corrispondenza di facce che hanno

piu di un arco frontiera in comune. Basandoci su ragionamenti simili possiamo provare che

il duale del duale (G∗)∗ e isomorfo a G se e soltanto se G e connesso.

Figura 4.7: Esempio di due embedding planari con duali non isomorfi.

Definizione 4.2.2 La lunghezza l(Fi) di una faccia Fi in un grafo G planare e pari alla

lunghezza del walk chiuso che e frontiera della faccia.

Per esempio nel grafo in alto nella Figura 4.7, le lunghezze delle facce sono rispetti-

vamente 3, 6, 7, mentre nel grafo in basso le lunghezze sono 3, 4, 9. In entrambe i casi si

puo notare che la somma fa 16, cioe il doppio del numero degli archi. Questo suggerisce la

seguente proposizione:

Proposizione 4.2.1 Se l(Fi) denota la lunghezza della faccia Fi del grafo piano G, allora

2m(G) =∑

l(Fi).

Dimostrazione: La lunghezza delle facce corrisponde al grado dei vertici duali relativi e,

dato che |m(G)| = |m(G∗)|, la formula 2m(G) =∑

l(Fi) altro non e che una diversa forma

del Lemma 1.1.1 (lemma handshaking).

Grafi Planari 56

Questa proposizione evidenzia che le relazioni relative a grafi piani connessi diventano

relazioni per il loro duale quando scambiamo il ruolo dei vertici e delle facce. Infatti,

archi incidenti su vertici diventano archi frontiera di una faccia e viceversa; analoga cosa si

verifica per il ruolo della lunghezza delle facce e grado dei vertici. Un’ulteriore relazione si

puo presentare nella colorazione dei vertici di G∗ in termini di G. Di fatto, gli archi di G∗

rappresentano frontiere condivise tra facce di G, quindi il numero cromatico di G∗ eguaglia

il numero di colori necessari per colorare le facce di G. Dato pero che il duale del duale

di un grafo piano connesso e il grafo originale, allora 4 colori sono sufficienti per colorare

correttamente le regioni di ogni grafo planare se e soltanto se ogni grafo planare ha numero

cromatico al piu 4.

Continuando nella nostra caratterizzazione dei grafi planari, dimostriamo il seguente

teorema.

Teorema 4.2.2 Le seguenti affermazioni sono equivalenti per un grafo piano G:

1. G e bipartito;

2. ogni faccia di G ha lunghezza pari;

3. il duale G∗ e euleriano.

Dimostrazione:

(1) ⇒ (2) Se il grafo e bipartito, allora per il Teorema 3.3.6 non ho cicli dispari e quindi il

contributo alla misura della lunghezza di una faccia e sempre pari.

(2) ⇒)(1) Consideriamo il ciclo C nel grafo G di Figura 4.8. Dato che non ho intersezioni tra

archi, allora C e una curva chiusa che racchiude la regione F ed inoltre tutte le regioni

di G o sono completamente all’interno della regione F o completamente all’esterno;

se sommo la lunghezza delle regioni contenute in F ottengo un numero pari, per

ipotesi. Questa somma contiene sia archi di C, che contano una sola volta, sia ogni

arco contenuto in F , contati due volte (perche insistono su due facce). Sottraendo a

tale somma i contributi degli archi contenuti in F deve rimanere ancora una quantita

pari; quindi C ha lunghezza pari e da cio consegue la bipartibilita di G.

Grafi Planari 57

C

Figura 4.8: Il ciclo C evidenziato per la dimostrazione del teorema.

(2) ⇔ (3) Il grafo duale G∗ e connesso ed il grado dei sui vertici corrisponde alla lunghezza

delle facce che e pari. La tesi segue subito dal Teorema 3.5.1.

Dimostriamo ora la Formula di Eulero che rappresenta uno dei piu importanti risultati

per i grafi planari e che mette in relazione vertici, archi e facce.

Teorema 4.2.3 (Eulero, 1758) Se un grafo piano G connesso ha esattamente n vertici,

m archi e f facce, allora

n − m + f = 2 (4.1)

Dimostrazione: Dimostriamo il teorema per induzione. Per n = 1, se m = 0 allora la

formula vale (1 − 0 + 1 = 2), mentre qualunque inserimento di un arco aggiunge un loop

che porta ad avere un arco in piu ed una faccia in piu; dato che questi ultimi nella formula

si elidono, questa vale qualunque sia il numero di archi.

e →

Figura 4.9: Contrazione dell’arco e.

Per ipotesi induttiva, affermiamo che il teorema sia valido per m − 1, ∀G connesso.

Allora, se il grafo e connesso, posso trovare un arco e che non e un loop. Se contraggo tale

arco come in Figura 4.9 ottengo un nuovo grafo G′ con n′ = n−1 vertici, m′ = m−1 archi

Grafi Planari 58

e f ′ = f facce. Per l’ipotesi induttiva posso scrivere che:

n − m + f = (n − 1) − (m − 1) + f ′ = n′ − m′ + f ′ = 2

Il teorema di Eulero ha notevoli implicazioni nello studio dei grafi planari e ci porta a

dire, per esempio, che tutti gli embedding planari di un grafo connesso G hanno lo stesso

numero di facce o che, sebbene il duale dipenda dal particolare embedding scelto, il numero

dei vertici del duale e invece indipendente.

La formula di Eulero puo essere generalizzata al caso di grafi k-connessi attraverso la

formula n − m + f = k + 1.

4.2.2 Caratterizzazione dei grafi planari

Un problema molto importante e, dato un grafo G qualunque, capire se questo possiede un

embedding in un piano, ovvero se e planare. Data l’importanza pratica dei grafi planari,

che compaiono in molte modellizzazioni nella produzione industriale e nella progettazione

dei circuiti VLSI, occorre trovare un modo efficace per certificare la planarita.

Un importante risultato che fornisce un test di planarita e il Teorema di Kuratowski,

che in forma semplificata ha il seguente enunciato.

Teorema 4.2.4 (Kuratowski, 1930) Un grafo e planare se e solo se non contiene K5 o

K3,3.

La dimostrazione di questo importante risultato esula dagli scopi di queste note. Il

lettore interessato potra trovare una completa trattazione su [5].

4.3 Esercizi

Es. 4.3.1 Dato K2,4 dire se esiste un possibile embedding planare. Se si, disegnarlo e

costruire il suo grafo duale.

Grafi Planari 59

Es. 4.3.2 Dato il grafo in figura, disegnare il suo grafo duale. Dire quante sono le facce e

validarlo con la legge di Eulero.

Es. 4.3.3 A partire dal grafo dell’esercizio precedente, connettere il grafo con un singolo

bridge e quindi costruire il duale. Dire quante sono le facce e applicare la legge di Eulero.

Es. 4.3.4 Fornire un esempio di un grafo in grado di dimostrare che G∗ e non isomorfo

a G.

Es. 4.3.5 E’ possibile disegnare un grafo planare semplice con 3 vertici e 4 facce? Perche?

Se e possibile, disegnarlo.

Es. 4.3.6 E’ possibile disegnare un grafo planare semplice con 4 vertici e 4 facce? Perche?

Se e possibile, disegnarlo.

Es. 4.3.7 E’ possibile disegnare un grafo planare semplice con 6 facce e 5 vertici? Se si,

disegnarlo.

Es. 4.3.8 E’ sempre possibile disegnare un grafo planare con n > 2 vertici e 3n− 6 archi?

Es. 4.3.9 Dato un grafo semplice e connesso, una condizione necessaria per la planarita

e che sia m ≤ 3n − 6. E possibile disegnare un grafo planare di 11 nodi in cui ogni nodo

ha grado almeno pari a 5? Perche?

Capitolo 5

Algoritmi di ricerca su grafo

Gli algoritmi di ricerca su grafo, oggetto dei prossimi paragrafi, rappresentano tecniche

fondamentali per determinare nodi che soddisfino particolari proprieta sia su grafi non

orientati che orientati. Inoltre, le varianti a tali tecniche sono alla base di numerosi impor-

tanti algoritmi, come per esempio: trovare tutti i nodi che a partire da un nodo specifico

siano raggiungibili da un path orientato; individuare tutti i path orientati che da tutti i

nodi raggiungano un nodo assegnato; individuare tutte le componenti connesse di un grafo;

determinare se un grafo e bipartito, ecc. Un’ulteriore applicazione di grande riscontro nella

pratica consiste nella ricerca di cicli in grafi orientati e, se il grafo e aciclico, nell’ordinarne

i nodi secondo un dato criterio, cosı come vedremo nella Sezione 5.2.

In merito ai grafi non orientati vedremo, specificamente nella nella Sezione 5.3, gli

algoritmi di ricerca del minimo albero ricoprente di un grafo, all’analisi dei quali faremo

precedere la dimostrazione delle condizioni che garantiscono l’ottimalita della soluzione

trovata.

5.1 Algoritmi di ricerca su grafo

Il problema che ci poniamo di risolvere e il seguente: determinare tutti i nodi in un grafo

orientato G(V,E) raggiungibili lungo cammini orientati a partire da un nodo assegnato s,

chiamato sorgente.

60

Algoritmi su grafo 61

Partire dalla sorgente ed identificare un numero via via crescente di nodi raggiungi-

bili dalla sorgente rappresenta un criterio che possiamo seguire per risolvere il problema.

Immaginiamo che ad ogni passo intermedio dell’algoritmo i nodi del grafo possono tro-

varsi in due stati differenti: marcato, se e possibile raggiungerli a partire dalla sorgente,

o non marcato se non e stato ancora possibile. E evidente che, se un nodo i e marcato

(e quindi raggiungibile dalla sorgente) ed il nodo j non e ancora marcato ed esiste l’arco

(i, j), allora possiamo marcare j perche allora questo e raggiungibile da un cammino dalla

sorgente attraverso l’arco (i, j). Chiameremo l’arco (i, j) ammissibile se i e marcato e j

non e marcato, non ammissibile viceversa. Successivamente, esaminando archi ammissibili,

potremo marcare altri nodi e, ogni volta che ci riusciremo, affermeremo che il nodo i e un

predecessore di j. L’algoritmo termina quando il grafo non contiene piu archi ammissibili.

L’algoritmo visita i nodi marcati in un certo ordine di cui possiamo tenere traccia

utilizzando un vettore che chiameremo ordine e nel quale l’elemento ordine(i) contiene il

passo nel quale i e stato marcato.

In Figura 5.1 viene riportato il listato in pseudocodice dell’algoritmo di ricerca.

Nell’algoritmo in questione, il vettore LISTA contiene l’insieme dei nodi marcati che de-

vono ancora essere considerati per individuare altri archi dai quali poi marcare altri nodi,

mentre il vettore pred(i) definisce un albero di nodi marcati che prende il nome di albero

di ricerca. Quando l’algoritmo sara terminato, tutti i nodi raggiungibili dalla sorgente

attraverso un cammino orientato risulteranno marcati. Notare che in talune istanze di

grafo l’algoritmo potrebbe terminare senza aver marcato tutti i nodi del grafo stesso, il

che equivale a dire che i nodi non marcati sono tutti quelli non raggiungibili dalla sorgente

tramite un cammino orientato.

Si puo dimostrare facilmente che l’algoritmo ha una complessita computazionale di

O(m + n) = O(m). Infatti, ad ogni iterazione del ciclo while o viene trovato un arco

ammissibile oppure no. Nel primo caso, l’algoritmo marca un nuovo nodo e lo aggiunge a

LISTA, mentre nel secondo caso cancella un nodo marcato da LISTA. Pertanto, dato che

ogni nodo viene marcato al piu una volta, il ciclo while e eseguito 2n volte. Per quanto

riguarda la ricerca di archi ammissibili, per ogni nodo i viene percorsa la lista di adiacenza


algorithm SEARCH;

beginponi tutti nodi come non marcati;

marca la sorgente s;pred(s) = 0;next:=1;

ordine(s) = 1;LISTA := {s};while LISTA 6= ∅ dobegin

seleziona un nodo i in LISTA;

if il nodo i e incidente ad un arco ammissibile (i, j) thenbegin

marca il nodo j;pred(j) := i;next:= next + 1;

ordine(j) := next;

aggiungi il nodo j a LISTA;

endelse cancella il nodo i da LISTA;

endend

Figura 5.1: L’algoritmo di ricerca su grafo.

A(i) al piu una volta; quindi l’algoritmo esamina un totale di∑

i∈V |A(i)| = m archi e

quindi termina al piu in O(m) volte.

Un aspetto centrale dell’algoritmo e la disciplina con la quale selezioniamo i nodi del

grafo contenuti nel vettore LISTA per ricercare archi ammissibili e, quindi, marcare nuovi

nodi. Per ottenere cio possiamo fare uso della lista di adiacenza A(i) introdotta nella

Sezione 3.1 alla quale aggiungiamo la seguente regola d’ordinamento: gli archi in A(i) sono

disposti in ordine crescente rispetto al loro nodo successore, ovvero se (i, j) e (i, k) sono

due nodi consecutivi in A(i), allora j < k.

Tra tutte le discipline possibili di selezione di una lista, le due piu note sono la coda e

la pila che definiscono, rispettivamente, le tecniche di ricerca in ampiezza e di ricerca in

profondita.


2

3

1 6

5

4

Figura 5.2: Grafo per gli Esempi 5.1.1 e 5.1.2.

Ricerca in ampiezza

Nel caso della ricerca in ampiezza viene implementata una disciplina di tipo first in, fir-

st out (FIFO), ovvero ogni nuovo elemento viene inserito in coda e l’estrazione avviene

considerando il primo elemento della lista.

Se definiamo la distanza di un nodo i dalla sorgente come la somma degli archi di cui

e composto il cammino diretto da s a i, questa disciplina porta a marcare prima i nodi a

distanza 1, poi quelli a distanza 2 e cosı via.

Proprieta 5.1.1 Nella ricerca in ampiezza, l’albero dei cammini dalla sorgente s ad ogni

nodo i e composto dai cammini piu corti.

Esempio 5.1.1 Considerando il grafo di Figura 5.2, si determini l’albero dei cammini

utilizzando la disciplina di ricerca in ampiezza.

Per risolvere il nostro problema, analizziamo passo per passo l’evoluzione dell’algoritmo.

Chiaramente, si devono inizializzare le variabili secondo i valori che seguono: LISTA =

{1}, pred(1) = 0; next = 1; ordine(1) = 1.

Step 1 Al primo passo, selezionando il nodo 1 preso da LISTA, possiamo marcare il nodo 2;

quindi, pred(2) = 1; next = 2; ordine(2) = 2. Dopo l’ultimo aggiornamento, LISTA

= {1, 2} (notare che il nodo 2 e stato aggiunto in coda a LISTA).


Step 2 Al secondo passo, selezionando il nodo 1 preso da LISTA, possiamo marcare il nodo

3; pred(3) = 1; next = 3; ordine(3) = 3. Dopo l’ultimo aggiornamento, LISTA

= {1, 2, 3}.

Step 3 Al terzo passo, selezionando il nodo 2 preso da LISTA (notare che il nodo 1 e stato

cancellato dalla lista in quanto non presentava piu archi ammissibbili ed e quindi stato

selezionato il primo nodo che era stato immesso, cioe il nodo 2) possiamo marcare il

nodo 4; pred(4) = 2; next = 4; ordine(4) = 4. Dopo l’ultimo aggiornamento, LISTA

= {2, 3, 4}.

Step 4 Al quarto passo, selezionando il nodo 2 preso da LISTA, possiamo marcare il nodo

5; pred(5) = 2; next = 5; ordine(5) = 5. Dopo l’ultimo aggiornamento, LISTA

= {2, 3, 4, 5}.

Step 5 Al quinto ed ultimo passo, selezionando il nodo 4 preso da LISTA, possiamo marcare

il nodo 6; pred(6) = 4; next = 6; ordine(6) = 6. Dopo l’ultimo aggiornamento,

LISTA = {4, 5, 6}.

A questo punto l’algoritmo non trova piu archi ammissibili e si arresta. In Figura 5.3 e

disegnato l’albero dei cammini definito dall’algoritmo ed i valori assunti dai due vettori

pred(i) e ordine(i).

E da notare che l’applicazione della disciplina FIFO ha originato, come ci dovevamo

aspettare, un albero con le minime distanze tra la sorgente s ed ogni nodo di G.

s

Figura 5.3: Albero dei cammini e valori dei vettori pred(i) e ordine(i) nel caso FIFO.


Ricerca in profondita

Nel caso della ricerca in profondita viene implementata una disciplina del tipo last in,

first out (LIFO), ovvero ogni elemento nuovo viene inserito in coda e l’estrazione avviene

considerando l’ultimo elemento della lista.

Utilizzando questa disciplina si crea un cammino orientato il piu lungo possibile e

quando non si riescono ad individuare altri archi ammissibili, la lista viene scorsa ritornando

verso i nodi che erano stati inseriti nei passi precedenti.

Proprieta 5.1.2 Se il nodo j e un successore del nodo i e i 6= j, allora ordine(j) >

ordine(i). Inoltre, tutti i successori dei nodi nella sequenza sono ordinati consecutivamente.

Esempio 5.1.2 Considerando il grafo di Figura 5.2, si determini l’albero dei cammini

utilizzando la disciplina di ricerca in profondita.

Anche in questo caso analizziamo passo per passo l’evoluzione dell’algoritmo. Chiara-

mente, si devono inizializzare le variabili secondo i valori che seguono: LISTA = {1},pred(1) = 0; next = 1; ordine(1) = 1.

Step 1 Al primo passo, selezionando il nodo 1 preso da LISTA, possiamo marcare il nodo 2;

pred(2) = 1; ordine(2) = 2. Dopo l’ultimo aggiornamento, LISTA = {1, 2}.

Step 2 Al secondo passo, selezionando il nodo 2 preso da LISTA, possiamo marcare il nodo 3

(notare che adesso viene selezionato l’ultimo nodo che era entrato in LISTA, appunto

il nodo 2); pred(3) = 2; ordine(3) = 3. Dopo l’ultimo aggiornamento, LISTA =

{1, 2, 3}.

Step 3 Al terzo passo, selezionando il nodo 3 preso da LISTA, possiamo marcare il nodo 4;

pred(4) = 3; ordine(4) = 4. Dopo l’ultimo aggiornamento, LISTA = {1, 2, 3, 4}.

Step 4 Al quarto passo, selezionando il nodo 4 preso da LISTA, possiamo marcare il nodo

6; pred(6) = 4; ordine(6) = 5. Dopo l’ultimo aggiornamento, LISTA = {1, 2, 3, 4, 6}.


Step 5 Al quinto ed ultimo passo, selezionando il nodo 2 preso da LISTA, possiamo marcare

il nodo 5; pred(5) = 2; ordine(5) = 6. Dopo l’ultimo aggiornamento, LISTA =

{1, 2, 5}.

A questo punto l’algoritmo non trova piu archi ammissibili e si arresta. In Figura 5.3 e

tracciato l’albero dei cammini definito dall’algoritmo ed i valori assunti dai due vettori

pred(i) e ordine(i).

Osservando l’albero dei cammini individuato, possiamo notare come questa volta il

cammino dalla sorgente ai nodi sia il piu lungo possibile.

s

Figura 5.4: Albero dei cammini e valori dei vettori pred(i) e ordine(i) nel caso LIFO.

5.2 Algoritmo di ordinamento topologico

Il prossimo problema che affronteremo e quello di cercare, se esistono, cicli diretti in un

grafo orientato, altrimenti, se il grafo e aciclico, di etichettare i nodi 1, 2, . . . , n in modo tale

che per ogni arco (i, j) ∈ E(G), l’etichetta del nodo i sia minore dell’etichetta di j. Questa

numerazione, se esiste, prende il nome di ordinamento topologico. Gli algoritmi di

ordinamento topologico sono essenziali in molte applicazioni come per esempio nel project

management.

Per etichettare i nodi di un grafo G con n numeri distinti possiamo usare un vettore

ordine in modo che ordine(i) fornisca l’etichetta del nodo i.


Definizione 5.2.1 Dato un grafo orientato G, diremo che una etichettatura e un

ordinamento topologico se ∀(i, j) ∈ E, si ha che ordine(i) < ordine(j).

Come si e detto, non tutti i grafi possono essere ordinati topologicamente; basta infatti che

il grafo sia ciclico e la condizione ordine(i) < ordine(j) non puo essere dimostrata vera

per ogni arco del grafo. Analogamente, un grafo che non contiene cicli puo essere ordinato

topologicamente. Questo ci porta a dire che un grafo orientato e aciclico se e soltanto se

ammette un ordinamento topologico.

algorithm ORDINAMENTO TOPOLOGICO;

beginfor tutti i nodi i ∈ V do

indegree(i):=0;

for tutti gli archi (i, j) ∈ E doindegree(j):=indegree(j) + 1;

LISTA= 0;next:=0;

for tutti i nodi i ∈ V doif indegree(i) = 0 then LISTA = LISTA∪{i};

while LISTA 6= ∅ dobegin

seleziona un nodo i in LISTA e rimuovilo;

next:= next + 1;

ordine(i) := next;

for tutti gli archi (i, j) ∈ E dobegin

indegree(j):= indegree(j) − 1;if indegree(j) = 0 then LISTA = LISTA∪{j};

endendif next < n then il grafo contiene un ciclo diretto;

else il grafo e aciclico ed il vettore ordine contiene il suo

ordinamento topologico;

end

Figura 5.5: L’algoritmo di ordinamento topologico.

Vediamo ora una implementazione dell’algoritmo di ordinamento topologico, di cui

forniamo lo pseudocodice in Figura 5.5. La variabile indegree(i) considera il numero di

archi entranti nel nodo i, che viene chiamato anche grado entrante di un nodo. In analogia,


1

4

3

2

5 7

6 8

Figura 5.6: Grafo per l’Esempio 5.2.1

si puo contare anche il numero di archi uscenti da un nodo che prende il nome di grado

uscente.

La complessita computazionale di questo algoritmo e O(m). Infatti, per prima cosa,

vengono conteggiati i gradi in ingresso di tutti i nodi, formando una lista che comprende

tutti i nodi con grado 0. Ad ogni iterazione selezioniamo un nodo i da LISTA, per ogni

arco (i, j) ∈ A(i) riduciamo il grado in ingresso di 1 del nodo j e se il grado in ingresso

del nodo j diviene 0 lo aggiungiamo a LISTA. Dato che l’algoritmo esamina ogni nodo ed

ogni arco del grafo O(1) volte, allora la sua complessita totale e O(m).

Esempio 5.2.1 Dato il grafo in Figura 5.6, individuare, se esiste, un ordinamento

topologico.

L’algoritmo comincia inserendo al primo passo il nodo 1 nella LISTA e quindi ordine(1) =

1. Al successivo passo, in LISTA ci sono i nodi 3 e 4, scelgo il primo e aggiorno il vettore

ordine(3) = 2. Continuando, in LISTA ci sono i nodi 2 e 4, scelgo ancora il primo ed

ho ordine(2) = 3. Continuando in questo modo, ottengo la sequenza ordine(4) = 4,

ordine(6) = 5, ordine(5) = 6, ordine(7) = 7 ed infine ordine(8) = 8. In Figura 5.7 e

rappresentato il vettore ordine(i). Si puo notare che tale ordinamento trovato non e unico.

Infatti, in alcuni passi si possono presentare piu di un nodo con grado in ingresso nullo e

la scelta di uno e di un altro non pregiudica la soluzione perche la relazione ordine(i) <

ordine(j) rimane valida, ∀(i, j) ∈ E.


Figura 5.7: Contenuto del vettore ordine(i) dopo l’ordinamento topologico.

Infine, siccome l’algoritmo termina con una etichettatura ammissibile per ogni nodo, si

puo affermare che il grafo assegnato e aciclico.

E importante ribadire che nel caso dell’ordinamento topologico la selezione dell’elemento

dalla lista puo essere effettuato arbitrariamente. Questo porta a determinare differenti

etichettature, cosa del tutto lecita visto che il nostro obiettivo era quello di rispettare una

semplice condizione, ovvero che ∀(i, j) ∈ E, si abbia che ordine(i) < ordine(j).

5.3 Algoritmi di ricerca di alberi ricoprenti minimi

Nella Sezione 3.4 abbiamo dato la definizione di albero ricoprente, definendolo come l’albero

che comprende tutti i nodi di un dato grafo connesso G. Chiaramente un albero ricoprente

non e, in generale, unico, ma dipende dalla scelta degli archi dell’insieme E.

In questa sezione vogliamo considerare il Problema del minimo albero ricoprente. Sup-

poniamo sia assegnato un grafo connesso non orientato G = (V,E) e che ad ogni arco

(i, j) ∈ E sia assegnato un costo cij, dove cij e un numero intero. Si vuole trovare un al-

bero ricoprente T chiamato minimo albero ricoprente (in inglese: minimum spanning

tree, MST) tale che il costo totale, dato dalla somma dei singoli costi degli archi che lo

costituiscono, sia minimo.

Il problema del minimo albero ricoprente ha una importanza rilevante dato il vasto

campo di applicazioni che vanno dal disegno di sistemi fisici, alla cluster analysis fino ai

metodi di riduzione della memorizzazione dei dati.


Condizioni di ottimalita

Per risolvere il problema forniremo due condizioni di ottimalita che ci porteranno a presen-

tare due algoritmi in grado di fornirci la soluzione ottima. Chiaramente le due condizioni

sono equivalenti, cosı come i due algoritmi forniscono la stessa soluzione sullo stesso grafo.

Prima di definire tali condizioni esponiamo alcune osservazioni preliminari:

Definizione 5.3.1 Dato un grafo G = (V ; E), si definisce taglio di G una sua partizione

in due insiemi, S ed S = V − S. Ogni taglio definisce un insieme di archi che hanno un

estremo in S e l’altro in S. Indicheremo il taglio con la notazione [S, S].

Nell’esposizione successiva faremo spesso riferimento alle due osservazioni seguenti:

1. Per ogni arco (p, q) che non appartiene all’albero ricoprente T , allora T contiene un

unico path da p a q. L’arco (p, q) assieme al path definisce un ciclo.

2. Se si cancella un arco (i, j) ∈ T , il grafo risultante partiziona l’insieme V in due

sottoinsiemi. Gli archi del grafo G sottostante i cui estremi ricadono uno in un

sottoinsieme e uno nell’altro definiscono un taglio.

T ∗

p q

ji

SS

Figura 5.8: Tagli e path per le condizioni di ottimalita.

In Figura 5.8 sono illustrate le due osservazioni che abbiamo esposto, ovvero l’arco

(p, q) genera con il path pq un ciclo, mentre la rimozione dell’arco (i, j) genera il taglio

[S, S]. Risultera molto utile al lettore fare riferimento a tale figura per le dimostrazioni che

seguono.


Enunciamo la prima condizione di ottimalita, che prende il nome di condizione di

ottimalita sul taglio:

Teorema 5.3.1 Un albero ricoprente e un minimo albero ricoprente T ⋆ se e soltanto se e

soddisfatta la seguente condizione di ottimalita sul taglio: per ogni arco (i, j) ∈ T ∗ allora

cij ≤ cpq, per ogni arco (p, q) contenuto nel taglio formato dalla rimozione dell’arco (i, j)

da T ∗.

Dimostrazione: Per dimostrare che ogni albero minimo ricoprente T ⋆ deve soddisfare la

condizione di ottimalita del taglio basta notare che, se esistesse un arco (p, q) ∈ [S, S] con

cpq < cij, basterebbe sostituire tale arco all’arco (i, j) per ottenere un nuovo albero T ◦ con

un costo minore di T ⋆, contraddicendo la sua ottimalita.

Per dimostrare la sufficienza, dobbiamo far vedere che ogni albero T ⋆ che soddisfa

la condizione di ottimalita deve essere ottimo. Supponiamo allora che T ◦ 6= T ⋆ sia un

minimo albero ricoprente. T ⋆ contiene almeno un arco (i, j), che non appartiene a T ◦ che,

se cancellato, crea un taglio [S, S]. Se ora aggiungiamo tale arco a T ◦ creiamo un ciclo W

che conterra un arco (p, q) ∈ [S, S]. Dato che T ⋆ soddisfa la condizione di ottimalita, allora

avremo che cij ≤ cpq, ma contemporaneamente T ◦ e un albero minimo ricoprente, quindi

cpq ≤ cij; di conseguenza deve essere che cij = cpq. Chiaramente, sostituire l’arco (p, q)

all’arco (i, j) in T ⋆ non comporta alcun aumento del costo di tale albero, ma otteniamo un

nuovo T ⋆ che ha un ulteriore arco in comune con T ◦. Ripetendo tale procedura per tutti i

suoi archi, otterremo un nuovo T ⋆ che coincide con il minimo albero ricoprente T ◦, ovvero

anche T ⋆ e un minimo albero ricoprente.

La condizione di ottimalita sul taglio implica che ogni arco di un minimo albero rico-

prente ha il valore del costo piu piccolo tra tutti i costi degli archi che appartengono al

taglio generato dalla sua rimozione. Questo implica che noi possiamo includere nell’albero

ricoprente minimo qualunque arco a costo minimo appartente a qualunque taglio. Per

dimostrare questo ci e utile la seguente proposizione:

Proposizione 5.3.2 Sia F un sottoinsieme di archi appartenenti ad un albero ricoprente

minimo e sia S un insieme di nodi di certe componenti di F . Si supponga che (i, j) sia un


arco a costo minimo nel taglio [S, S]. Allora un minimo albero ricoprente contiene tutti gli

archi di F e l’arco (i, j).

Dimostrazione: Supponiamo che F ⊆ T ⋆. Se (i, j) ∈ T ⋆ allora la proposizione e banal-

mente vera. Se (i, j) /∈ T ⋆, aggiungendolo a T ⋆ si crea un ciclo W che contiene almeno

un arco (p, q) 6= (i, j), con (p, q) ∈ [S, S]. Per assunzione, cij ≤ cpq, ma T ⋆ soddisfa la

condizione di ottimalita e quindi cij ≥ cpq, quindi cij = cpq. Di conseguenza, aggiungere

l’arco (i, j) e rimuovere l’arco (p, q) produce un albero minimo ricoprente che contiene tutti

gli archi di F e l’arco (i, j).

Passiamo ora a dimostrare la seconda condizione di ottimalita che chiameremo

condizione di ottimalita sul path :

Teorema 5.3.3 Un albero ricoprente e un minimo albero ricoprente T ⋆ se e soltanto se e

soddisfatta la seguente condizione di ottimalita sul path: per ogni arco (p, q) ∈ G che non

appartiene a T ⋆ si ha che cij ≤ cpq, ∀(i, j) contenuto nel path in T ⋆ che connette i nodi p

e q.

Dimostrazione: Per dimostrare la necessita, supponiamo che T ⋆ sia un albero minimo

ricoprente e che (i, j) sia un arco contenuto nel path tra i nodi p e q. Se cij > cpq, allora

la sostituzione di tale arco in T ⋆ al posto dell’arco (i, j) creerebbe un nuovo albero T ◦ con

un costo minore di T ⋆, contraddicendo la sua ottimalita.

Per dimostrare che se T ⋆ e ottimo allora deve verificare la condizione di ottimalita sul

path, supponiamo che (i, j) sia un arco in T ⋆ e siano S e S i due insiemi di nodi connessi

generati dalla cancellazione dell’arco (i, j) da T ⋆, con i ∈ S e j ∈ S. Consideriamo ora un

arco (p, q) ∈ [S, S]. Dato che T ⋆ contiene un unico path tra p e q e dato che (i, j) e l’unico

arco tra S ed S, allora (i, j) deve appartenere a tale path. La condizione di ottimalita

implica che cij ≤ cpq e dato che tale condizione deve essere vera per ogni arco (p, q) /∈ T ⋆

nel taglio [S, S] generato dalla cancellazione dell’arco (i, j), allora T ⋆ soddisfa la condizione

di ottimalita sul taglio e quindi deve essere ottimo.

Si puo notare come nella dimostrazione di quest’ultimo teorema si sia usata quella della

sufficienza del Teorema 5.3.1. Questo evidenzia come le due condizioni siano completamen-


te equivalenti e che quindi un minimo albero ricoprente T ⋆ che soddisfa la condizione di

ottimalita sul taglio deve contemporaneamente soddisfare anche la condizione di ottimalita

sul path.

Un’altra osservazione e che la condizione di ottimalita sul taglio e una condizione che

potremmo indicare come una caratteristica esterna del minimo albero ricoprente, nel senso

che coglie una relazione tra un suo arco e gli altri archi fuori dall’albero; viceversa, la

condizione di ottimalita sul path coglie una caratterizzazione interna del minimo albero

ricoprente che considera la relazione tra un singolo arco, che non appartiene all’albero, ed

i diversi archi che appartengono al path, nell’albero, che si forma aggiungendo tale arco.

5.3.1 Algoritmo di Kruskal

La condizione di ottimalita sul path suggerisce immediatamente un algoritmo per la ricerca

del minimo albero ricoprente su un grafo. Infatti, si puo partire con un generico albero

ricoprente T e si testa la condizione di ottimalita sul path; se T soddisfa la condizione per

ogni arco allora e un albero ottimo, altrimenti ci sara un qualche arco (p, q) che chiude

l’unico path tra p e q in T con cij > cpq. Sara sufficiente sostituire l’arco (p, q) all’arco (i, j)

per ottenere un albero di costo piu basso; quindi, ripetendo la procedura, in un numero

finito di iterazioni avremo l’albero ottimo. La semplicita di questo algoritmo ha pero

una complessita computazionale che non puo essere limitata in un numero polinomiale di

iterazioni.

Per ottenere un algoritmo piu efficiente, noto con il nome di Algoritmo di Kruskal ,

si puo iniziare considerando un ordinamento non decrescente degli archi secondo il loro

peso e, quindi, una procedura che a partire da un albero vuoto, rispettando l’ordinamento

posto, aggiunga archi uno alla volta. L’algoritmo puo essere descritto nel seguente modo:

Algoritmo di Kruskal

Step 1 - Ordina tutti gli archi del grafo G per valori non decrescenti del costo degli archi;

Step 2 - Prendi una foresta ricoprente H = (V (H), F ) di G, con all’inizio F = ∅;


Step i - Aggiungi ad F un arco (i, j) /∈ F a minimo costo, tale che H rimanga una foresta.

Stop quando H e un albero ricoprente.

L’algoritmo esegue la procedura corretta perche, ad ogni passo, vengono scartati archi

che formerebbero un ciclo con quelli che invece appartengono alla foresta corrente. Inoltre,

si puo notare che gli archi che formerebbero il ciclo hanno un costo che e maggiore o al piu

uguale al costo degli altri archi, appartenenti alla foresta, nel ciclo; questo perche i costi

sono ordinati in ordine non decrescente. Pertanto, l’albero trovato soddisfa la condizione

di ottimalita sul path e quindi e ottimo.

Esempio 5.3.1 Dato il grafo G = (V,E) riportato in Figura 5.9 ed assegnati i costi cij,

∀(i, j) ∈ E (trascritti accanto ad ogni arco) trovare l’albero ricoprente ottimo mediante

l’algoritmo di Kruskal e fornire il suo valore ottimo z⋆.

5

18

16

15 1210

c12 = 5

8

21

3 4

Figura 5.9: Grafo per l’Esempio 5.3.1.

Il primo passo e quello di ordinare gli archi in ordine non decrescente, attraverso il quale

otteniamo la lista {(1, 2), (3, 4), (2, 3), (2, 4), (1, 3), (4, 5), (2, 5)}. Il passo successivo (Step 1

in Figura 5.10) parte dalla foresta F = ∅ e poi seleziona l’arco (1, 2) che e quello a costo

minimo e lo aggiunge ad F . Al passo successivo (Step 2 in Figura 5.10) viene selezionato

(3, 4) e dopo aver controllato che non crei un ciclo, e aggiunto ad F . L’algoritmo procede

selezionando l’arco (2, 3) (Step 3 in Figura 5.10) e, dopo aver controllato che non si crei

un ciclo, lo aggiunge ad F. Il test sul ciclo fallisce nei due passi successivi (Step 4 e 5 in

Figura 5.10) quando selezionando prima l’arco (2, 4) e poi l’arco (1, 3) ci si accorge che


generano un ciclo. L’ultimo passo (Step 6 in Figura 5.10) seleziona l’arco (4, 5) e con

quest’ultimo inserimento la foresta F diventa l’albero ricoprente ottimo T ⋆, avente costo

z⋆ = 39.

Step 6

Step 1 Step 2 Step 3

Step 4 Step 5

Figura 5.10: Evoluzione dell’algoritmo di Kruskal sul grafo di Figura 5.9.

Per determinare la complessita computazionale dell’algoritmo1 occorre osservare che,

per individuare un ciclo, si puo, tra l’altro, creare ad ogni passo delle liste di nodi in numero

pari alle componenti della foresta ricoprente corrente (nell’esempio precedente al passo 3

avremmo le due liste {1, 2, 3, 4} e {5}) e poi, per ogni arco (i, j) che si vuole introdurre,

controllare se i nodi i e j appartengono ad una stessa lista. Se il test ha esito positivo,

l’arco crea un ciclo (come l’arco (2, 4) al passo 4 dell’esempio) e viene scartato, altrimenti

puo essere aggiunto alla foresta corrente (come l’arco (4, 5) all’ultimo passo dell’esempio).

Per eseguire questi passi occorre effettuare O(n) iterazioni per ogni arco del grafo e, quindi,

la complessita computazionale dell’algoritmo di Kruskal e O(nm).

5.3.2 Algoritmo di Prim

Il secondo algoritmo per la ricerca del minimo albero ricoprente segue dalla applicazione

della condizione di ottimalita sul taglio. L’algoritmo, noto con il nome di Algoritmo

di Prim , costruisce un albero ricoprente a partire da un nodo ed aggiunge un arco per

1Il calcolo e eseguito a meno dell’ordinamento dei costi degli archi che, in un grafo di ordine n,dimensione m e costi di valore arbitrario, e uguale a O(m log m) = O(m log n2) = O(m log n).


volta. L’arco viene selezionato tra quelli a costo minimo appartenenti al taglio [S, S]

generato dall’inserimento in S dei nodi estremi degli archi aggiunti all’albero nel passo

precedente. L’algoritmo termina quando S = V . La correttezza dell’algoritmo segue dalla

Proposizione 5.3.2 dove e stato dimostrato che ogni arco che aggiungiamo ad un albero

e contenuto in un certo albero ricoprente assieme agli archi che sono stati selezionati nei

passi successivi. La descrizione dell’algoritmo e la seguente:

Algoritmo di Prim

Step 1 - Considerare un albero H = (V (H), T ), con inizialmente V (H) = {r} e T = ∅, con

r ∈ V (G);

Step i - Ad ogni passo, aggiungi all’albero connesso H un arco a minimo costo (i, j) /∈ H

scegliendolo tra quelli che a minimo costo aggiungono un nuovo nodo e mantengono

l’albero connesso. Stop se H e il minimo albero ricoprente.

In pratica, l’algoritmo evolve attraverso la selezione di archi a minimo costo che ab-

biano gli estremi uno nell’insieme dei nodi degli archi gia selezionati (cioe in S) e l’altro

nell’insieme dei nodi degli archi che non sono stati ancora selezionati (cioe in S). Quindi,

l’algoritmo mantiene un albero connesso che cresce di un arco ad ogni passo e che, all’ul-

timo, coincide con l’albero ottimo. Osservando l’algoritmo di Kruskal si nota invece che

l’algoritmo aggiunge, ad ogni passo, archi ad una foresta che diventa connessa solo alla

fine.

Per analizzare la complessita computazionale dell’algoritmo, basta notare che l’algorit-

mo stesso esegue n−1 iterazioni per definire gli n−1 archi dell’albero ed in ogni iterazione

viene selezionato da un taglio un arco a costo minimo. Dato che tale selezione puo essere

eseguita anche sull’intera lista degli archi, ne segue che la complessita dell’algoritmo di

Prim e O(nm).

Esempio 5.3.2 Considerando il grafo di Figura 5.9, trovare l’albero ricoprente ottimo

mediante l’algoritmo di Prim e fornire il suo valore ottimo z⋆.


Supponiamo che l’algoritmo parta da V (H) = {1}. In questo caso, l’algoritmo puo sceglie-

re tra gli archi del taglio [S, S] = [{1}, {2, 3, 4, 5}]; l’arco a costo minimo selezionato e che

mantiene l’albero connesso e (1, 2) (vedi Step 1 in Figura 5.11, dove la linea tratteggiata

indica il taglio); aggiungo l’arco ad H (indicato in figura dagli archi in grassetto) ed il

nodo 2 ad S. Al passo successivo (Step 2 in Figura 5.11) l’algoritmo deve scegliere gli archi

a costo minimo tra quelli del taglio [{1, 2}, {3, 4, 5}] e, tra tutti, viene scelto l’arco (2, 3).

L’algoritmo continua scegliendo (3, 4) in [{1, 2, 3}, {4, 5}] (Step 3 in Figura 5.11) ed infine

termina aggiungendo l’arco (4, 5) dal taglio [(1, 2, 3, 4}, {5}] (Step 4 in Figura 5.11), resti-

tuendoci l’albero ottimo di costo minimo, pari a z⋆ = 39. Come si puo notare, l’algoritmo

termina in n− 1 = 4 passi, avendo ad ogni passo aggiunto un arco ad un albero connesso.

Step 4Step 1 Step 2 Step 3

Figura 5.11: Evoluzione dell’algoritmo di Prim sul grafo di Figura 5.9.

Osservazione. Si vuole ribadire che negli esempi che abbiamo esposto, cosı come ci do-

vevamo aspettare, gli algoritmi forniscono lo stesso valore ottimo e, inoltre, i due alberi

ottenuti sono identici. Quest’ultima affermazione non nasconde pero una proprieta di uni-

cita sugli archi che compongono l’albero ricoprente ottimo, perche, in generale, si possono

ottenere alberi a costo minimo composti da archi differenti. Questo non ci deve sorprendere

poiche gli algoritmi si possono trovare nella condizione di poter selezionare archi nella lista

(per Kruskal) o nel taglio (per Prim) che abbiano stesso costo. Dato che selezionare un

arco piuttosto che un altro e solo funzione delle condizioni di ottimalita, possiamo ottenere

alberi minimi ottimi composti da archi differenti.


5.4 Esercizi

Da inserire.

Es. 5.4.1 Data le matrice di adiacenza dell’Esercizio 3.7.2, disegnare il grafo corrispon-

dente e individuare su questo, se esiste, un ordinamento topologico. In caso negativo,

motivare perche esso non esiste e quindi rimuovere il minimo numero di archi in modo che

sia possibile trovare un ordinamento topologico.

Capitolo 6

Problemi di flusso su grafo

In questo capitolo introdurremo ed analizzeremo il seguente problema: si vuole trasferire,

a minimo costo, un flusso di beni attraverso una rete in modo da soddisfare la domanda

di certi nodi sulla base di quanto procurato da parte di altri nodi.

Sia G = (V,E) un grafo orientato al quale considereremo associato ad ogni arco e ad

ogni nodo un insieme di grandezze che li caratterizzano. In particolare, assoceremo ad ogni

arco (i, j) ∈ E un costo cij che definisce il costo per unita di flusso nell’arco stesso e che

varia linearmente con il flusso; una capacita uij che indichi la massima quantita di flusso

che puo scorrere lungo l’arco; infine, un limite inferiore lij che indica la minima quantita

di flusso che deve scorrere nell’arco medesimo. Ad ogni nodo i ∈ V , invece, assoceremo una

grandezza b(i) che indichera se il nodo e un punto di rifornimento del flusso oppure e un

punto di domanda del flusso; se b(i) > 0 allora il nodo i sara un nodo di rifornimento del

flusso, se b(i) < 0 allora il nodo i sara un nodo di domanda del flusso e se b(i) = 0 allora il

nodo i sara un nodo di trasferimento del flusso. In generale, considereremo∑

∀i∈V b(i) = 0.

Per formulare il nostro problema in termini di modello di ottimizzazione, introduciamo

la variabile decisionale xij che rappresenta la quantita di flusso che scorre nell’arco (i, j).

Il Problema di flusso a costo minimo si puo formulare nel seguente modo:

min∑

(i,j)∈E

cijxij

79

Problemi di flusso su grafo 80

soggetto ai vincoli:

∑

j:(i,j)∈E

xij −∑

j:(j,i)∈E

xji = b(i) ∀i ∈ V (6.1)

lij ≤ xij ≤ uij ∀(i, j) ∈ E (6.2)

Il vincolo 6.1 impone sia soddisfatto il bilancio di massa ad ogni nodo. Infatti, esso

indica che in un nodo la quantita di flusso entrante meno la quantita di flusso uscente deve

eguagliare la quantita di flusso rifornita o richiesta. Il vincolo 6.2 impone invece che siano

rispettati i limiti inferiori e superiori della capacita di ogni arco, cioe che il flusso che scorre

rispetti lo spettro di valori di capacita ammessi. In molte applicazioni si ha per ogni arco

che lij = 0, quindi nel seguito considereremo tale valore, se non altrimenti specificato.

6.1 Algoritmi di ricerca del cammino minimo su di un

grafo

Gli algoritmi di ricerca del cammino minimo su un grafo costituiscono uno degli argomenti

principali dello studio delle reti di flusso. Le ragioni risiedono nel gran numero di appli-

cazioni reali che possono essere risolte mediante questo modello, nella grande semplicita

nell’ottenere soluzioni in modo molto efficiente, nel fatto che, nonostante la loro semplicita,

catturano alcuni aspetti teorici che sono alla base delle reti di flusso e della teoria dei grafi

e nel fatto che compaiono come sottoproblemi in molte applicazioni.

Consideriamo un grafo orientato G = (V,E) al quale associamo ad ogni arco (i, j) ∈ E

una lunghezza cij. Il grafo ha un nodo particolare che chiameremo sorgente s. Definiamo

la lunghezza di un cammino orientato nel grafo come la somma delle lunghezze degli archi

nel cammino. Il problema del cammino minimo in un grafo G = (V,E) (in inglese,

shortest path problem, SPP) consiste nel determinare i cammini di lunghezza minima dalla

sorgente s verso ogni altro nodo in V . In termini di flusso, possiamo modellare il problema


supponendo di inviare, a costo minimo, una unita di flusso verso ogni nodo i ∈ V −{s} in

un grafo senza vincoli di capacita. In termini di formulazione matematica, il modello e il

seguente:

min∑

(i,j)∈E

cijxij


∑

j:(i,j)∈E

xij −∑

j:(j,i)∈E

xji = n − 1 i = s (6.3)

∑

j:(i,j)∈E

xij −∑

j:(j,i)∈E

xji = −1 ∀i ∈ V − {s} (6.4)

xij ≥ 0 ∀(i, j) ∈ E (6.5)

Nello studio del cammino minimo dobbiamo fare alcune assunzioni:

• Gli archi devono avere lunghezza intera. Questa assunzione non e restrittiva perche

nella rappresentazione nei computer i numeri irrazionali sono convertiti in numeri

razionali e qualunque numero razionale puo essere trasformato in un numero intero

moltiplicandolo per un numero sufficientemente grande.

• Il grafo contiene un cammino orientato dalla sorgente s verso qualunque altro nodo

nel grafo.

• Il grafo non contiene cicli di lunghezza negativa. Per la formulazione vista, l’esistenza

di un ciclo W a costo negativo implicherebbe una soluzione non limitata inferiormente

perche potremmo inviare una quantita infinita di flusso lungo W .

Dato che esiste un cammino orientato dalla sorgente ad ogni altro nodo del grafo, allora

possiamo dire che esiste un albero dei cammini minimi che dalla sorgente si emana verso

tutti gli altri nodi i cui archi sono gli archi dei diversi cammini. L’esistenza di tale albero

e sostenuta dalla seguente proprieta:


s

P1 P3

P2

p k

Figura 6.1: Cammini da s a k.

Proprieta 6.1.1 Se il cammino s = n1, n2, . . . , nk = k e un cammino minimo dalla sor-

gente s al nodo k, allora per ogni p = 2, 3, . . . , k − 1, il sottocammino s = n1, n2, . . . , np e

il cammino minimo dalla sorgente s al nodo p.

Dimostrazione: Questa proprieta e facile da dimostrare. Infatti, se prendiamo in Figu-

ra 6.1 il cammino minimo P1-P3 da s a k che passa attraverso un certo nodo p, allora il

cammino P2 non e il cammino minimo da s a p. Se P2 fosse il cammino minimo, allora

sarebbe sufficiente prendere il cammino P2-P3 da s a k per avere un cammino piu corto di

P1-P3, contraddicendo la sua ottimalita.

Indichiamo ora con d(i) la distanza del nodo i ∈ V da s. La Proprieta 6.1.1 implica

che se P e un cammino minimo da s a k, allora d(j) = d(i) + cij, ∀(i, j) ∈ P ; anche il

viceversa e vero, infatti:

Proprieta 6.1.2 Se d(j) = d(i)+cij, ∀(i, j) ∈ P , allora P deve essere il cammino minimo

tra s e k.

Dimostrazione: Per dimostrare questa affermazione, supponiamo che s =

n1, n2, . . . , nk = k sia la successione di nodi nel cammino P . Allora, prendendo la distanza

d(k) ed aggiungendo e togliendo la distanza di ogni nodo in P otteniamo, manipolando

algebricamente l’espressione, che:

d(k) = d(nk) = (d(nk) − d(nk−1)) + (d(nk−1) − d(nk−2)) + . . . + (d(n2) − d(n1))

Considerando che d(n1) = d(s) = 0 e che per assunzione d(j)−d(i) = cij, abbiamo che:

d(k) = cnk−1nk+ cnk−1nk−2

+ . . . + cn1n2=

∑

∀(i,j)∈P

cij


Di conseguenza, P e un cammino diretto dalla sorgente s a k di lunghezza d(k) e dato

che per assunzione d(k) e la distanza del cammino minimo del nodo k, allora P deve essere

il cammino minimo del nodo k.

Quanto detto si puo riassumere nel seguente risultato:

Proprieta 6.1.3 Un cammino diretto P dalla sorgente s al nodo k e un cammino di

lunghezza minima se e solo se d(j) = d(i) + cij, ∀(i, j) ∈ P .

6.1.1 L’algoritmo di Dijkstra

L’algoritmo di Dijkstra e un algoritmo in grado di risolvere il problema della ricerca del

cammino minimo dalla sorgente s a tutti i nodi. L’algoritmo mantiene una etichetta d(i)

ai nodi che rappresentano un upper bound sulla lunghezza del cammino minimo del nodo i.

Ad ogni passo l’algoritmo partiziona i nodi in V in due insiemi: l’insieme dei nodi etichet-

tati permanentemente e l’insieme dei nodi che sono ancora etichettati temporaneamente.

La distanza dei nodi etichettati permanentemente rappresenta la distanza del cammino

minimo dalla sorgente a tali nodi, mentre le etichette temporanee contengono un valore

che puo essere maggiore o uguale alla lunghezza del cammino minimo.

L’idea di base dell’algoritmo e quella di partire dalla sorgente e cercare di etichettare

permanentemente i nodi successori. All’inizio, l’algoritmo pone il valore della distanza

della sorgente a zero ed inizializza le altre distanze ad un valore arbitrariamente alto (per

convenzione, porremo come valore iniziale delle distanze d(i) = +∞, ∀i ∈ V ). Ad ogni

iterazione, l’etichetta del nodo i e il valore della distanza minima lungo un cammino dal-

la sorgente che contiene, a parte i, solo nodi etichettati permanentemente. L’algoritmo

seleziona il nodo la cui etichetta ha il valore piu basso tra quelli etichettati temporanea-

mente, lo etichetta permanentemente ed aggiorna tutte le etichette dei nodi a lui adiacenti.

L’algoritmo termina quando tutti i nodi sono stati etichettati permanentemente.

In Figura 6.2 e riportata la descrizione dell’Algoritmo di Dijkstra. Le operazioni com-

piute dall’algoritmo sono fondamentalmente due: una operazione di selezione del nodo ed

una operazione di aggiornamento delle distanze. La prima seleziona ad ogni passo il nodo


con il valore dell’etichetta piu basso, l’altra verifica la condizione d(j) > d(i) + cij e, in

caso positivo, aggiorna il valore dell’etichetta ponendo d(j) = d(i) + cij.

algorithm DIJKSTRA;

beginS = ∅;

S = V ;

∀i ∈ V , d(i) = ∞;

d(s) = 0;pred(s) = 0;while |S| < n dobegin

sia i ∈ S un nodo per cui d(i) = min{d(j) : j ∈ S};S = S ∪ {i};S = S − {i};for ∀(i, j) ∈ A(i) do

if d(j) > d(i) + cij thenbegin

d(j) = d(i) + cij;

pred(j) = i;end;

end;end;

Figura 6.2: L’algoritmo di Dijkstra

Vediamo un esempio per analizzare i passi effettuati dall’algoritmo.

Esempio 6.1.1 Dato il grafo G in Figura 6.3, calcolare i cammini minimi del nodo sorgen-

te {1} verso gli altri nodi utilizzando l’algoritmo di Dijkstra. Usare le tabelle di Etichetta

nodo, Archi e Predecessore per indicare rispettivamente l’aggiornamento delle etichette dei

nodi, gli archi candidati per ogni nodo ed i predecessori lungo il cammino minimo.

All’inizio, l’algoritmo partiziona i nodi in due insiemi S (nodi etichettati permanentemen-

te) e S (nodi etichettati temporaneamente), pone l’etichetta della sorgente uguale a zero e

le etichette degli altri nodi uguali a ∞. Successivamente entra nel ciclo while ed esegue i

seguenti passi:

• seleziona il primo nodo ad etichetta minima, cioe la sorgente s; quindi, per ogni suo

nodo adiacente ad esso, verifica se d(2) > d(1) + c12, d(3) > d(1) + c13 e d(4) >


2

1

2

2

4

2

1

4

3

1

5

2

2

1

4

3

3 8

4 7

6

5

Figura 6.3: Grafo per l’Esempio 6.1.1 e corrispondente tabella degli archi.

d(1) + c14; dato che ∞ > 0 + 2 = 2, ∞ > 0 + 4 = 4 e ∞ > 0 + 2 = 2, tutte e tre le

condizioni sono verificate e quindi aggiorno le etichette ed i predecessori nel seguente

modo: d(2) = d(1) + c12 = 0 + 2 = 2 e pred(2) = 1, d(3) = d(1) + c13 = 0 + 4 = 4 e

pred(3) = 1 ed infine d(4) = d(1) + c14 = 0 + 2 = 2 e pred(4) = 1.

• al secondo passo, l’etichetta con il valore piu basso e d(2) e quindi seleziono il nodo 2

che diventa etichettato permanentemente. Per i suoi nodi adiacenti si deve verificare

se d(3) > d(2) + c23 e d(5) > d(2) + c25; dato che solo la seconda viene verificata

(perche d(3) = 4 > d(2) + c23 = 2 + 2 = 4 non e verificata, mentre e vero che

d(5) = ∞ > d(2) + c25 = 2 + 4 = 6), aggiorno la sua etichetta ponendo d(5) =

d(2) + c25 = 2 + 4 = 6 e pred(5) = 2.

• al terzo passo, l’etichetta di valore piu basso e d(4) e quindi seleziono il nodo 4 che

diventa etichettato permanentemente. Per i suoi nodi adiacenti si deve verificare se

d(3) > d(4) + c43 e d(7) > d(4) + c47; dato che entrambe sono verificate (perche

d(3) = 4 > d(4) + c43 = 2 + 1 = 3 e d(7) = ∞ > d(4) + c47 = 2 + 5 = 7), aggiorno le

etichette ed ottengo d(3) = 3 e pred(3) = 4, e d(7) = 7 e pred(7) = 4.

• al quarto passo, l’etichetta di valore piu basso e d(3) e quindi seleziono il nodo 3 che


d(5) > d(3) + c35 e d(6) > d(3) + c36; dato che e verificata solo la seconda, aggiorno

l’etichetta corrispondente ed ottengo d(6) = 4 e pred(6) = 3.


• al quinto passo, l’etichetta di valore piu basso e d(6) e quindi seleziono il nodo 6 che


d(7) > d(6) + c68 e d(8) > d(6) + c68; dato che entrambe sono verificate, aggiorno le

due etichette ed ottengo d(7) = 6 e pred(7) = 6, e d(8) = 8 e pred(8) = 6.

• al sesto passo, l’etichetta di valore piu basso e d(5) e quindi seleziono il nodo 5 che


d(6) > d(5) + c56 e d(8) > d(5) + c58; dato che solo la seconda e verificata, aggiorno

l’etichetta corrispondente ed ottengo d(8) = 7 e pred(8) = 5.

• al settimo passo, l’etichetta di valore piu basso e d(7) e quindi seleziono il nodo 7

che diventa etichettato permanentemente. Per i suoi nodi adiacenti si deve verifi-

care se d(8) > d(7) + c78; dato che la relazione non e verificata non effettuo alcun

aggiornamento.

• all’ottavo ed ultimo passo, l’etichetta di valore piu basso e d(8) e quindi seleziono il

nodo 8 che diventa etichettato permanentemente. Il nodo non ha nessun adiacente,

quindi l’algoritmo termina.

Nelle due tabelle in Figura 6.4 sono riassunti rispettivamente l’andamento delle etichette

lungo i singoli passi dell’algoritmo e i predecessori dei singoli nodi per ricostruire i cammini

minimi.

Correttezza dell’algoritmo di Dijkstra

Per dimostrare la correttezza dell’algoritmo di Dijkstra facciamo due ipotesi induttive. La

prima e che le etichette di distanza dei nodi in S sono ottime, la seconda che le etichette di

distanza dei nodi sono la lunghezza del cammino minimo dalla sorgente s che contengono

solo nodi in S. Per dimostrare la prima ipotesi, ricordiamoci che ad ogni passo l’algoritmo

trasferisce un nodo i con l’etichetta piu piccola da S a S; quindi, occorre dimostrare che

d(i) e ottima. Ma per le ipotesi induttive poste, d(i) e la lunghezza del cammino minimo

del nodo i tra tutti i cammini che non contengono un nodo di S. Supponiamo allora, per


Figura 6.4: Evoluzione delle etichette dei nodi e lista di adiacenza per il grafo di Figura 6.3.

assurdo, di considerare un cammino P che contiene almeno un nodo k ∈ S, come mostrato

in Figura 6.5 e di decomporre il cammino P nei due sottocammini P1-P2: il sottocammino

P1 non contiene un nodo di S, ma termina in un nodo in S; quindi, per ipotesi induttiva

la lunghezza e d(k) e dato che i ha la distanza minima in S, deve risultare che d(k) ≥ d(i)

e quindi il sottocammino P1 deve avere lunghezza almeno d(i). Dato che ogni arco ha

lunghezza non negativa, la lunghezza del sottocammino P2 e non negativa e quindi la

lunghezza del cammino P e almeno d(i).

Per dimostrare che l’algoritmo verifica la seconda ipotesi induttiva, osserviamo che dopo

che e stata effettuata l’etichettatura permanente del nodo i, le etichette di alcuni nodi in

S − {i} decrescono, perche questo e interno al cammino minimo che si sta cercando per

tali nodi. Ma dopo aver permanentemente etichettato un nodo i, l’algoritmo esamina ogni

arco (i, j) ∈ A(i) e se d(j) > d(i) + cij, allora avviene l’aggiornamento d(j) = d(i) + cij,

pred(j) = i. Quindi, dopo l’aggiornamento, per le ipotesi induttive, il cammino dalla

sorgente al nodo j definito dal vettore dei predecessori soddisfa la Proprieta 6.1.3 e quindi

le etichette di distanza di ogni nodo in S − {i} sono la lunghezza del cammino minimo

soggette alla restrizione che ogni nodo del cammino deve appartenere ad S ∪ {i}.Per quanto riguarda la complessita computazionale dell’algoritmo di Dijkstra partiamo

dalle due operazioni di base che l’algoritmo esegue. In particolare, l’operazione di selezione

dei nodi viene eseguita n volte ed ad ogni passo scandisce ogni nodo etichettato tempora-


P1

SS

i

s

k

pred(i)P2

Figura 6.5: Disegno per la correttezza di Dijkstra

neamente, quindi esegue n + (n − 1) + (n − 2) + . . . + 1 = O(n2) iterazioni. L’operazione

di aggiornamento delle etichette viene eseguita |A(i)| volte per ogni nodo i, quindi lungo

tutta l’esecuzione dell’algoritmo viene eseguita∑

∀i∈V |A(i)| = m; dato che ogni opera-

zione di aggiornamento richiede O(1), ne segue che l’algoritmo impiega O(m) per aggior-

nare le etichette. Riassumendo, dato che O(m) < O(n2), la complessita computazionale

dell’algoritmo di Dijkstra e O(n2).

Il valore di complessita trovato e il migliore che si puo ottenere per grafi molto densi,

mentre puo essere migliorato nel caso di grafi sparsi. Infatti, la complessita della ope-

razione di selezione dei nodi pesa considerevolmente di piu rispetto alla complessita del-

l’aggiornamento delle etichette. Di conseguenza sono stati effettuati molti sforzi diretti al

miglioramento dell’efficienza di tale operazione e, in particolare, implementando strutture

dati piu elaborate, si e riuscito a diminuire la complessita sino a O(m + n log n) nel caso

di liste di nodi memorizzate come liste di Fibonacci. Rimandiamo il lettore a [10] per una

trattazione completa sulle diverse implementazioni.

6.2 Problemi di massimo flusso su grafo

Il problema della ricerca del massimo flusso su di un grafo e un problema complementare a

quello della ricerca del cammino minimo. Infatti, alcuni aspetti del problema del flusso a

costo minimo sono catturati dal problema del cammino minimo nel quale sono considerati

i costi ma non le capacita; il problema del massimo flusso, invece, considera le capacita, ma


non i costi. L’unione dei problemi del cammino minimo e del flusso massimo rappresenta

la combinazione di tutti gli ingredienti di base dell’ottimizzazione delle reti di flusso.

Consideriamo un grafo orientato G = (V,E) nel quale ad ogni arco (i, j) ∈ E sia

assegnata una capacita uij ≥ 0 e sia U = max{uij : uij < ∞,∀(i, j) ∈ E}. Il Problema

del massimo flusso su di un grafo si puo enunciare nel seguente modo: in un grafo

orientato con capacita, determinare il massimo flusso che puo essere inviato da un nodo

s chiamato sorgente ad un nodo t chiamato pozzo, senza eccedere le capacita dei singoli

archi. Il problema puo essere formulato matematicamente nel seguente modo:

max v


∑

j:(i,j)∈E

xij −∑

j:(j,i)∈E

xji = v i = s (6.6)

∑

j:(i,j)∈E

xij −∑

j:(j,i)∈E

xji = 0 ∀i ∈ V − {s} − {t} (6.7)

∑

j:(i,j)∈E

xij −∑

j:(j,i)∈E

xji = −v i = t (6.8)

0 ≤ xij ≤ uij ∀(i, j) ∈ E (6.9)

Il vettore x = {xij} che soddisfa le equazioni scritte conterra il valore del flusso per

ogni arco (i, j) e la variabile v conterra il valore totale del flusso. Nell’analisi del problema

del massimo flusso poniamo le seguenti assunzioni:

• Tutte le capacita sono interi non negativi.

• Il grafo non contiene un cammino diretto dal nodo s al nodo t composto solo da archi

di capacita infinita. Questa assunzione impedisce che una quantita di flusso infinita

possa scorrere lungo un cammino, rendendo il problema illimitato.

• Se il grafo contiene l’arco (i, j) allora contiene anche l’arco (j, i). Questa assunzione

non e restrittiva perche possiamo sempre aggiungere archi a capacita nulla.


• Il grafo non contiene archi paralleli.

Per poter sviluppare l’algoritmo necessario per risolvere il nostro problema, abbiamo

bisogno di definire il concetto di grafo residuo G(x) corrispondente ad un flusso assegnato

x. Supponiamo che un arco (i, j) trasporti xij quantita di flusso. Quindi possiamo ancora

inviare sull’arco uij − xij unita di flusso dal nodo i al nodo j; analogamente, potremmo

inviare xij unita di flusso da j ad i per annullare il flusso che scorre in (i, j). Sulla base

di questa osservazione possiamo definire un grafo residuo, rispetto ad un dato flusso x,

sostituendo ogni arco (i, j) con una coppia di archi: un arco (i, j) con capacita residua

rij = uij − xij e un arco (j, i) con capacita residua rji = xji, come si puo notare in

Figura 6.6. Il grafo residuo consiste solo negli archi con capacita residua positiva. Dalla

uij − xij

i i j

rij

i jj

(xij, uij)

⇒xji

Figura 6.6: Costruzione del grafo residuo.

definizione di grafo residuo che abbiamo dato, ne segue che la capacita residua e composta

da due componenti: una componente che indica la capacita non utilizzata uij − xij ed

una componente xji che indica il flusso corrente. Quindi, possiamo scrivere che rij =

uij − xij + xji.

Nella Sezione 5.3 abbiamo dato la definizione di taglio in un grafo come la partizione

dei suoi nodi in due insiemi, S e S = V − S, usando la notazione [S, S]. Nel seguito di

questo capitolo faremo riferimento ai tagli di tipo s-t, ovvero quei tagli nei quali s ∈ S

e t ∈ S. Inoltre, definiremo come archi diretti del taglio [S, S] gli archi (i, j) tali per cui

i ∈ S e j ∈ S e con archi inversi del taglio [S, S] gli archi (i, j) tali per cui i ∈ S e j ∈ S;

indicheremo con (S, S) l’insieme degli archi diretti del taglio [S, S] e con (S, S) l’insieme

degli archi inversi del taglio [S, S]. Per esempio, in Figura 6.8 e riportato un taglio s-t

per il grafo G di Figura 6.7, dove [S, S] = {(1, 3), (3, 4), (4, 6)}, (S, S) = {(1, 3), (4, 6)} e

(S, S) = {(3, 4)}.


G(x)

1

2

3

4

5

61

2

3

4

6

5

11

1

1

1

11

1

1

22

2(1,2)

(1,3)

(1,2)

(1,2)

(2,2)

(2,2)

(1,2)

G

Figura 6.7: Un grafo G con un flusso assegnato x ed il corrispondente grafo residuo G(x).

1

2

3

4

6

5

Figura 6.8: Un taglio s-t per il grafo di Figura 6.7.


Definizione 6.2.1 Si definisce capacita u[S, S] di un taglio s-t la somma delle capacita

degli archi diretti del taglio, ovvero:

u[S, S] =∑

(i,j)∈(S,S)

uij (6.10)

Si definisce taglio minimo il taglio s-t che tra tutti i possibili tagli s-t ha capacita

minima.

Chiaramente, la capacita di un taglio e un limite superiore della quantita massima di

flusso che possiamo inviare dai nodi in S ai nodi in S rispettando i vincoli di capacita

imposti.

Definizione 6.2.2 Si definisce capacita residua r[S, S] di un taglio s-t la somma delle

capacita residue degli archi diretti del taglio, ovvero:

r[S, S] =∑

(i,j)∈(S,S)

rij (6.11)

Dato un flusso x su di un grafo, per calcolare il flusso attraverso un taglio s-t possiamo

utilizzare il vincolo di bilancio di massa della formulazione, per cui:

v =∑

∀i∈S

[

∑

j:(i,j)∈E

xij −∑

j:(j,i)∈E

xji

]

Questa espressione si puo semplificare notando che se (p, q) ∈ E e p ∈ S e q ∈ S,

allora comparira un xpq nella prima sommatoria all’interno delle parentesi quadre (quando

i = p), ed un −xpq nella seconda (quando j = q). Considerando che nella sommatoria non

compaiono neanche le componenti di x che fanno riferimento ad archi che hanno solo nodi

in S, possiamo scrivere che:

v =∑

(i,j)∈(S,S)

xij −∑

(i,j)∈(S,S)

xij (6.12)

Questa relazione indica che il flusso dai nodi in S ai nodi in S e uguale al flusso che

da S va in S, meno il flusso che da S va a S e, dato che il primo membro dell’equazione e


esattamente il valore del flusso, abbiamo che esso eguaglia esattamente il valore del flusso

nel taglio. Considerando che xij ≤ uij e che xij ≥ 0, possiamo scrivere che:

v ≤∑

(i,j)∈(S,S)

uij (6.13)

Questo risultato ci indica che il valore di un qualunque flusso sul grafo e minore o al piu

uguale alla capacita di un su qualunque taglio s-t. Tale risultato e abbastanza intuitivo

perche ogni flusso che scorre da s a t deve attraversare ogni taglio s-t e, quindi, non ne puo

eccedere la capacita.

6.2.1 L’algoritmo di Ford e Fulkerson

Per risolvere il problema del massimo flusso in un grafo attraverso l’algoritmo che stiamo

per introdurre abbiamo bisogno di alcune definizioni sul grafo residuo:

Definizione 6.2.3 Si definisce cammino aumentante nel grafo residuo un cammino

diretto dalla sorgente al pozzo e capacita residua δ la minima capacita residua di ogni

arco nel cammino aumentante.

Nel grafo in Figura 6.7, un cammino aumentante nel grafo G(x) e costituito dagli

archi {(1, 2), (2, 4), (4, 3), (3, 5), (5, 6)} e la capacita residua δ = min{r12, r24, r43, r35, r56} =

min{1, 1, 1, 2, 1} = 1. Come si puo notare, la capacita residua e sempre maggiore di zero;

quindi, non appena un grafo contiene un cammino aumentante, possiamo inviare ulteriore

flusso dalla sorgente al pozzo.

Quest’ultima osservazione ci suggerisce l’algoritmo per risolvere il problema della ricerca

del massimo flusso. Infatti, potremmo iniziare utilizzando le tecniche di ricerca viste nella

Sezione 5.1 per identificare un cammino da s a t nel grafo G(x) partizionando i nodi del

grafo in due insiemi: nodi etichettati (quelli raggiungibili da s) e nodi non etichettati

(quelli non raggiungibili da s). Se alla fine del processo t e etichettato, allora invio la

massima quantita di flusso, pari alla capacita residua sul cammino aumentante trovato;

quindi, cancello tutte le etichette e ripeto la procedura iterativamente. L’algoritmo termina


quando non riesco ad etichettare t, cioe quando non esiste un cammino aumentante dalla

sorgente al pozzo.

Prima di esporre l’algoritmo, si vuole sottolineare che la ricerca di un cammino aumen-

tante nel grafo residuo G(x) corrisponde alla ricerca in G di un cammino dalla sorgente al

pozzo, non necessariamente orientato, con xij < uij per ogni arco diretto nel verso del cam-

mino e con xij > 0 per ogni arco inverso rispetto al verso del cammino ed esiste un cammino

aumentante rispetto ad un certo flusso x se e soltanto se esiste un cammino diretto da s a t

in G(x). Se ad un certo passo dell’algoritmo si aggiorna il flusso con un flusso addizionale

δ, allora xij variera rispettando la definizione di capacita residua (rij = uij − xij + xji) o

aumentando xij di δ unita o diminuendo xji di δ unita, oppure si avra una combinazione

convessa delle due possibilita precedenti.

Le osservazioni fatte fin qui possono essere formalizzate nell’algoritmo di Ford e Fulker-

son descritto in Figura 6.9. La correttezza dell’algoritmo segue dal fatto che sono possibili

due casi: o l’algoritmo trova un cammino aumentante dalla sorgente al pozzo, oppure non

riesce a trovare alcun cammino. Se si verifica il secondo caso dobbiamo dimostrare che

allora il flusso e ottimo. Supponiamo quindi che ad un certo passo, S sia l’insieme dei nodi

etichettati e S = V −S l’insieme dei nodi non etichettati, con s ∈ S e t ∈ S. Se l’algoritmo

non puo etichettare i nodi in S a partire dai nodi in S, allora rij = 0, ∀(i, j) ∈ (S, S);

inoltre, dato che rij = uij − xij + xji, xij ≤ uij e xji ≥ 0, allora la condizione rij = 0

implica che xij = uij per ogni arco (i, j) ∈ (S, S) e xij = 0 per ogni arco (i, j) ∈ (S, S).

Sostituendo questi valori nell’Equazione 6.12 otteniamo:

v =∑

(i,j)∈(S,S)

xij −∑

(i,j)∈(S,S)

xij =∑

(i,j)∈(S,S)

uij = u[S, S] (6.14)

Questa relazione mostra che il valore del flusso corrente x eguaglia la capacita del taglio

[S, S] e dato che l’Equazione 6.13 implica che x e il flusso massimo e [S, S] e il taglio minimo,

allora abbiamo dimostrato il seguente risultato:

Teorema 6.2.1 Il valore massimo del flusso dalla sorgente s al pozzo t in un grafo con

capacita eguaglia la capacita del minimo taglio s-t.


algorithm FORD&FULKERSON;

beginetichetta il nodo t;while t e etichettato dobegin

cancella le etichette di tutte i nodi i ∈ V ;

pred(j) = 0, ∀i ∈ V ;

etichetta s e poni LISTA= {s};while LISTA6= ∅ e t e non etichettato dobegin

rimuovi un nodo i da LISTA;

for (i, j) ∈ G(x) doif nodo j e non etichettato then;begin

pred(j) = i;etichetta j;aggiungi j a LISTA;

end;end;if t e etichettato thenbegin

usa le etichette dei predecessori per trovare all’indietro

il cammino aumentante P da s a t;δ = min{rij, (i, j) ∈ P};aumenta di δ unita di flusso lungo P e aggiorna G(x);

end;end;

end;

Figura 6.9: L’algoritmo di Ford e Fulkerson

Il teorema precedente, che chiameremo Teorema del massimo flusso e del mini-

mo taglio ci dice anche che quando l’algoritmo di Ford e Fulkerson termina con il massimo

flusso, contemporaneamente ci fornisce anche il taglio minimo.

Esempio 6.2.1 Dato il grafo in Figura 6.10, calcolare il flusso massimo dalla sorgente

{1} al pozzo {8} utilizzando l’algoritmo di Ford e Fulkerson, disegnando la successione dei

grafi residui. Indicare il taglio minimo corrispondente al flusso trovato.


4

1 3 8

4 7

6

52

3

2

3

3

5

4

6

3 2

2

2

4

Figura 6.10: Grafo per l’Esempio 6.2.1.

Nel grafo in Figura 6.10 il flusso e posto inizialmente a xij = 0 per ogni arco; quindi, il

primo grafo residuo coincide con il grafo di partenza.

• Nella prima iterazione l’algoritmo trova il cammino aumentante {(1, 2), (2, 5), (5, 8)},con δ = min{r12, r25, r58} = min{4, 2, 4} = 2. L’algoritmo esegue l’aumento del flusso

pari a δ = 2 unita ed aggiorna il grafo residuo, disegnato in Figura 6.11.

2

1 3 8

4 7

6

52

3

2

3

3

56

3 2

2

2

4

22 2

Figura 6.11: Il grafo residuo dopo la prima iterazione.

• Nella seconda iterazione l’algoritmo trova il cammino aumentante

{(1, 2), (2, 4), (4, 7), (7, 8)} con δ = min{r12, r24, r47, r78} = 2. L’algoritmo ese-

gue l’aumento del flusso pari a δ = 2 unita ed aggiorna il grafo residuo, disegnato in

Figura 6.12.

• Nella terza iterazione l’algoritmo trova il cammino aumentante {(1, 3), (3, 5), (5, 8)}


2

1 3 8

4 7

6

52

2

3

3

56

3 2

2

2

24

2

2

1

2

Figura 6.12: Il grafo residuo dopo la seconda iterazione.

con δ = min{r13, r35, r58} = 2. L’algoritmo esegue l’aumento del flusso pari a δ = 2

unita ed aggiorna il grafo residuo, disegnato in Figura 6.13.

21 3 8

4 7

6

52

2

3

5

3 2

2

4

2

2

1

2 2

3

4

4

Figura 6.13: Il grafo residuo dopo la terza iterazione.

• Nella quarta iterazione l’algoritmo trova il cammino aumentante {(1, 3), (3, 6), (6, 8)}con δ = min{r13, r36, r68} = 3. L’algoritmo esegue l’aumento del flusso pari a δ = 3

unita ed aggiorna il grafo residuo, disegnato in Figura 6.14.

• Nella quinta iterazione, l’algoritmo non riesce ad etichettare il pozzo e quindi termina.

Il flusso massimo e pari alla somma degli incrementi eseguiti nei singoli passi, cioe

v⋆ = 2 + 2 + 2 + 3 = 9. Il taglio minimo e riportato in Figura 6.15.


51 3 8

4 7

6

52

2

33 2

2

4

2

2

1

2 2

4

3

3

21

Figura 6.14: Il grafo residuo dopo la quarta iterazione.

4

1 3 8

4 7

6

52

3

2

3

3

5

4

6

3 2

2

2

4

Figura 6.15: Il taglio minimo del grafo di Figura 6.10.


Complessita computazionale dell’algoritmo di Ford e Fulkerson

Per calcolare la complessita computazionale osserviamo che l’algoritmo esegue una ricerca

per trovare un cammino dalla sorgente al pozzo (che sappiamo essere eseguibile, dalla

Sezione 5.1, in O(m) passi) tante volte quanto e possibile eseguire degli aumenti di flusso.

Per tali aumenti, se le capacita sono intere e limitate da U , allora la capacita di un taglio

(s,N − {s}) e al piu nU . Di conseguenza, siccome l’algoritmo aumenta il flusso di almeno

una unita ogni iterazione, ne segue che globalmente l’algoritmo esegue O(nmU) iterazioni.

L’algoritmo visto e sicuramente uno dei piu semplici per risolvere il problema del mas-

simo flusso, ma il valore di complessita computazionale e legato al valore di U e questo

potrebbe portare a casi nei quali l’algoritmo non risulta essere efficiente (per esempio, se

U = 2n). Inoltre, in alcuni casi puo eseguire tante iterazioni quante indicate dal caso

peggiore. Per esempio, se si considera l’istanza della Figura 6.16, l’algoritmo potrebbe

selezionare i cammini aumentanti 1− 3− 2− 4 e 1− 2− 3− 4, alternativamente, 106 volte,

ogni volta aumentando il flusso di una unita.

106-1

1

3

2

1

3

2

1

3

2

4 44

106

106

106

106

1

106

106

1 11

106-1 106-1

11

1

106-1106-1

1

106-1

1

Figura 6.16: Istanza patologica per l’algoritmo di Ford e Fulkerson.

Un altro difetto dell’algoritmo risiede nel fatto che ad ogni passo deve essere rieseguito il

processo di etichettatura e, quindi, le informazioni che si generano sui cammini aumentanti

vengono perse ad ogni passo e si devono ricalcolare di nuovo.

In [10] sono riportati diversi algoritmi efficienti per la risoluzione del problema del

massimo flusso che non risentono dei limiti dell’algoritmo di Ford e Fulkerson.


6.3 Esercizi

Da inserire

Indice analitico

Albero, 44

Ricoprente, 45

Minimo, 69

Algoritmo, 18

di Kruskal, 73

di ordinamento topologico, 67

di Prim, 75

di Dijkstra, 83

di Ford e Fulkerson, 93

di ricerca su grafo, 60

in ampiezza, 63

in profondita, 65

di ricerca su stringa, 20

Archi, 3

Multipli, 3

Bridge, 40

Ciclo, 13

Clique, 6

Componenti connesse, 39

Connessione, 15

Crescita di funzioni, 22

Combinazione di, 24

Cut-vertex, 40

Densita, 6

Distanza, 41

Embedding planare, 52

Faccia, 53

Flusso, 79

Foresta, 44

Formula di Eulero, 57

Grafo, 3

Aciclico, 42

Bipartito, 11, 43

Complemento, 9

Completo, 6

Denso, 6

Dimensione di un, 5

Disegno di un, 52

Duale, 54

Euleriano, 45

k-regolare, 8

Ordine di un, 5

Orientato, 32

Piano, 52

Planare, 52

Semplice, 3

101

INDICE ANALITICO 102

Sparso, 6

Insieme indipendente, 9

Isomorfismo, 36

Classi di equivalenza, 39

K-Fattorizzazione, 8

Lemma Handshaking, 7

Lista di adiacenza, 36

Loop, 3

Matrice di adiacenza, 34

Matrice di incidenza, 33

Nodi, 3

Notazione Big-O, 23

Numero cromatico, 12

Ordinamento topologico, 66

Path, 13, 14

Problema

decisionale, 17

del cammino minimo, 80

del flusso massimo, 88

dell’albero ricoprente minimo, 69

di flusso a costo minimo, 79

Regione, 53

Sottografo, 4

Indotto, 4

Ricoprente, 4

Taglio, 70

Teorema

del massimo flusso e minimo taglio, 95

di Eulero, 45

di Kuratowski, 58

Trail, 14

Euleriano, 45

Hamiltoniano, 47

Vertex covering, 10

Vicinato, 7

Walk, 14

Bibliografia

[1] AA.VV. Kaliningrad Business Guide. http://guide.kaliningrad.net.

[2] B. Bollobas. Modern graph theory. Springer-Verlag, 1998.

[3] K. Steiglitz C. H. Papadimitriou. Combinatorial optimization: algorithms and

complexity. Prentice Hall, 1982.

[4] N. Christofides. Graph theory, an algorithmic approach. Academic Press, 1975.

[5] R. Diestel. Graph Theory. Springer-Verlag, 2005.

[6] S. Fortin. The graph isomorphism problem. Technical Report TR96-20, Department

of Computer Science, The University of Alberta, Canada, July 1996.

[7] D. Jungnickel. Graphs, network and algorithms. Springer-Verlag, 1999.

[8] F. Maffioli. Elementi di programmazione matematica. Casa Editrice Ambrosiana,

2000.

[9] R. J. Wilson N. L. Biggs, E. K. Lloyd. Graph Theory 1736-1936. Oxford University

Press, 1999.

[10] J. B. Orlin R. K. Ahuja, T. L. Magnanti. Network Flows. Pearson Education, 1993.

[11] K. H. Rosen. Discrete mathematics and its applications. McGraw Hill Text, 1998.

[12] P. Serafini. Ottimizzazione. Zanichelli, 2000.

[13] A. Ventre. Introduzione ai grafi planari. Zanichelli Editore, 1983.

103

BIBLIOGRAFIA 104

[14] D. B. West. Introduction to graph theory. Prentice Hall, 2000.

Universit`a degli Studi di Roma “Tor Vergata” · 6.2 Problemi di massimo ﬂusso su grafo ......

Documents

Transcript of Universit`a degli Studi di Roma “Tor Vergata” · 6.2 Problemi di massimo ﬂusso su grafo ......