Nozioni, Ricerca operativa

Grafo Euleriano

Un grafo connesso viene detto euleriano se è possibile percorrere in un ciclo

elementare ( senza ripassare su steso arco) tutti i suoi archi.

Un ciclo euleriano percorre esattamente una sola volta tutti gli

archi del grafo (problema dei ponti di Könisberg).

Teorema di Eulero: Un grafo è euleriano se e solamente se tutti i

suoi nodi hanno grado pari.

Circuito Hamiltoniano

un percorso hamiltoniano è un percorso che passa per tutti i nodi del grafo una sola

volta (tour)

un circuito hamiltoniano è un percorso ha miltoniano chiuso

Alberi e foreste

un grafo è aciclico se non contiene cicli.

un albero è un grafo connesso ed aciclico.

Dato un albero, valgono le seguenti proprietà:

• Un albero contiene esattamente n − 1 archi. Infatti se contenesse meno archi non

potrebbe essere un grafo connesso, mentre se contenesse più di n − 1 archi allora

esisterebbe almeno un ciclo.

• Un albero ha almeno due foglie (nodi con grado 1).

• Per ogni coppia di nodi di un albero esiste un solo cammino che li connette. Se ce

ne fosse più di uno allora esisterebbe un ciclo nel grafo, mentre se per una coppia di

nodi non ci fosse un cammino il grafo non sarebbe connesso.

IMPORANTI esercizi dispensa 1 da pag 34 a 40

26/05

Albero ricoprente a costo minimo

Un albero ricoprente di un grafo connesso è un

albero che collega tutti i nodi del grafo.

Si consideri un grafo non orientato G pesato e connesso.

Obiettivo : individuare un albero ricoprente tale che la somma dei pesi degli archi

appartenenti all’albero sia minimizzata.

Se i pesi degli archi possono assumere valori uguali tra di loro, sarà sufficiente

trovare una sola soluzione ottima tra le molte che potrebbero esistere con lo stesso

valore della funzione obiettivo.

Indicheremo con T* un albero ricoprente a costo minimo.

Dato un albero ricoprente generico T, chiameremo tree arc l’insieme di archi

appartenenti all’albero e nontree arc gli archi non appartenenti ad esso

• Dato un albero ricoprente si può notare come l’aggiunta di un qualunque arco ad

esso crea esattamente un ciclo fondamentale

• L’eliminazione di un qualunque arco dal ciclo fondamentale genera un altro albero

ricoprente

• Dati un grafo connesso ed un suo albero ricoprente, si può notare che la rimozione

di un qualunque arco dall’albero ricoprente generi due sottoalberi, che definiscono un

taglio fondamentale.

• Visto che un albero contiene n − 1 archi sarà possibile definire esattamente n − 1

tagli fondamentali.

• Aggiungendo un arco appartenente al taglio si ottiene nuovamente un albero

ricoprente.

Condizioni di ottimalità sui tagli (1)

Teorema: Sia T* un albero ricoprente di costo minimo, un arco e apparterrà

all’albero ricoprente di costo minimo se e solo se esiste un taglio fondamentale in G

tale che l’arco e minimizzi il costo degli archi tagliati. cf > ce

ch > ce

Sono descritte le dimostrazioni di

necessità e sufficienza.

Dimostrazione Sufficienza: Supponiamo per assurdo che esista un arco e che

minimizza un taglio, ma che tale arco non appartenga all’albero ricoprente di costo

minimo. Aggiungendo all’albero ricoprente l’arco e si otterrà un ciclo fondamentale,

e ci sarà almeno un altro arco che appartiene al taglio, sia questo arco f.

Varrà la condizione cf > ce, quindi rimuovendo f dall’albero di costo minimo si

avrebbe un albero a costo inferiore segue l’assurdo.

Dimostrazione Necessità: Dato T* dobbiamo mostrare come sia possibile costruire

un taglio tale che l’arco e sia l’arco di costo minimo tra gli archi appartenenti al

taglio. A tal fine consideriamo nell’insieme S una delle due componenti connesse che

si verrebbe a generare a seguito della rimozione dell’arco e. L’arco e quindi

appartiene ad un taglio e necessariamente sarà il minimo in quel taglio altrimenti

l’albero T* non sarebbe una soluzione ottima.

Condizioni di ottimalità sui cammini (1)

Teorema: Un albero ricoprente T* è minimo se e solo se soddisfa ce <= cf per ogni

arco nontree f di G e per ogni arco e contenuto nel cammino che connette i due nodi

terminali di f.

Sono descritte le dimostrazioni di necessità e sufficienza.

Dimostrazione Necessità: Supponiamo per assurdo che T* sia ottimo e che esista un

arco e nel cammino tra i nodi terminali dell’arco f che non soddisfi la condizione.

Se vale ce >= cf allora introdurre l’arco f nell’albero ricoprente al posto dell’arco e

produrrebbe un albero a costo inferiore di T*, contraddicendo l’ipotesi iniziale.

Dimostrazione Sufficienza: Sia e un tree arc e siano S e S generati dal taglio legato

alla rimozione di e, sia l’arco f nel taglio [S, V − S]. Visto che T* contiene un unico

cammino che unisce le estremità di f, tale cammino dovrà passare per l’arco e.

L’ipotesi implica ce <= cf .

Considerando che questa condizione deve essere valida per ogni nontree arc nel

taglio [S, S] , allora T* soddisfa le condizioni di ottimalità dei tagli da cui T* deve

essere un albero a costo minimo.

Algoritmo di Kruskal

Sfruttando le condizioni di ottimalità dei cammini è possibile costruire un algoritmo

noto come Algoritmo di Kruskal:

0) L’algoritmo parte con un albero ricoprente vuoto (T = emptyset)

1) Si ordinano gli archi in ordine crescente di peso in una lista

2) Si scorre la lista prendendo ad ogni passo l’arco con peso minore

[Ad ogni passo si deve decidere se l’arco considerato va aggiunto

all’albero ricoprente di costo minimo o meno in base al fatto che crei cicli con i nodi

già inseriti nell’albero ricoprente a costo minimo.]

3) Alla fine si ottiene un albero ricoprente a costo minimo.

Il numero di operazioni per un’esecuzione dell’algoritmo = numero di operazioni per

ordinare gli archi + numero di operazioni di aggiornamento * num. aggiornamenti.

Da cui il numero di operazioni per una esecuzione dell’algoritmo di Kruskal è

limitato superiormente da O(m log n + n2) operazioni.

Con strutture dati specializzate è possibile ridurre la complessità teorica

dell’algoritmo di Kruskal fino a O(m log n) operazioni.

Algoritmo di Prim - Dijkstra (1)

L’algoritmo di Prim–Dijkstra sfrutta l’osservazione sui tagli fondamentali per

generare l’albero ricoprente a costo minimo.

Passo iniziale: Albero ricoprente vuoto

Ad ogni iterazione:

1) si considera un taglio fondamentale differente

2) si cerca l’arco che minimizza il peso tra gli archi appartenenti

al taglio corrente

3) si aggiorna il taglio corrente con l’arco selezionato

4) si inserisce l’arco selezionato nell’albero ricoprente

L’iterazione viene ripetuta finché non si è costruito l’intero albero

Esempio

• Si sceglie il nodo iniziale a caso, ad esempio il nodo 1

• Si considera quindi il taglio generato dall’insieme S = {1}, ovvero [S, S’] = {(1, 2),

(1, 3)}

• L’arco (1, 3) con c13 = 12 minimizza il costo degli archi del taglio corrente, per cui

il nodo 3 viene aggiunto all’insieme S

Esempio

• Alla seconda iterazione S = S U {3}

• L’arco che minimizza il costo del taglio è (2,3), e S = S U {2}

• L’arco (1,2) non appartiene più al taglio [S, V − S] ( formerebbe un ciclo)

• Alla terza iterazione S = S U {2}

• L’arco che minimizza il costo del taglio è (3,5), e S = S U {5}

• Alla quarta iterazione S = S U {5}

• L’arco che minimizza il costo del taglio è (2,4), e S = S U {4}

• L’arco (4,5) non appartiene più al taglio [S, V − S]

• Alla quinta iterazione S = S U {5}

• L’arco che minimizza il costo del taglio è (2,6), e S = S U {6}

• L’algoritmo esegue al più n iterazioni, infatti ad ogni iterazione l’algoritmo

aggiunge un nodo all’albero ricoprente

• La versione vista dell’algoritmo richiede m operazioni di confronto, infatti è

necessario scorrere tutti gli archi del grafo (m) per stabilire se l’arco appartiene o

meno all’insieme [S, S], e se vi appartiene stabilire se è quello di costo minimo o

meno.

• La complessità intesa come il maggior numero di operazioni per una esecuzione

dell’algoritmo di Prim–Dijkstra, sarà dunque non superiore a O(mn) operazioni. Dato

che m << n2 si ha O(n3)

Algoritmo di Prim – Dijkstra (2) implementazione efficiente

Concetto chiave: L’operazione collo di bottiglia nell’algoritmo è quella di individuare

l’arco a minor costo nel taglio [S, S]

Osservazione rilevante: Tra una iterazione e la successiva, [S, S] non deve essere

necessariamente ricalcolato per intero, infatti molti archi rimangono gli stessi

Speed-up dell’algoritmo: Struttura dati specializzata che mantiene memorizzati i dati

di [S, S] per riusarli nell’iterazione successiva

Nuova struttura dati:

• un vettore booleano di flag (V) che conserva l’informazione se il nodo i appartiene o

meno all’insieme S

• un vettore (D) che mantiene aggiornata, per ogni nodo in S, la distanza minima

necessaria per raggiungere il nodo a partire da S

{Il vettore delle distanze D sarà inizializzato con i valori degli archi della stella del

nodo radice }

• Inoltre sia C la matrice di adiacenza (n × n) che rappresenta i costi c[i, j] degli archi

tra i nodi i e j { Nel caso in cui l’arco da i a j non sia presente si assume

c[i, j] = +infinito, altrimenti si avrà c[i, j] = cij }

Considerazioni sul vettore delle distanze: Il vettore D rappresenta una stima della

distanza minima necessaria per congiungere ogni nodo in S al nodo radice.

Questa distanza viene inizializzata con + infinito se non esiste un arco diretto dal

nodo radice al generico nodo, altrimenti viene inizializzata con il peso dell’arco.

Durante l’esecuzione dell’algoritmo queste distanze vengono diminuite non appena il

nodo diviene raggiungibile, ovvero l’arco appartiene al taglio corrente

Se la distanza rimane +infinito il nodo non è ancora raggiungibile.

30/05

Il problema del cammino minimo

Cammino: una sequenza senza ripetizioni di vertici ed archi

Cammino minimo: cammino in un grafo orientato e pesato tale che sia minimizzato il

suo costo

Attenzione: in generale un grafo G può ammettere dei cicli a peso negativo

Problema ciclo a peso negativo: un algoritmo risolutivo potrebbe percorrere quel

ciclo un infinito numero di volte

Tipologie di problemi

Cammino minimo tra due nodi. Si