Esercitazioni algoritmi RO1

ALGORITMI:

• RICERCA IN AMPIEZZA: Basato su FIFO

• RICERCA IN PROFONDITÀ: Basato su LIFO

• ORDINAMENTO TOPOLOGICO: Utile per verificare l'aciclicità

ALGORITMI PER DETERMINARE L'ALBERO DEI CAMMINI MINIMI:

• Algoritmo per reti cicliche (se non sono cicli):

• Algoritmo di Dijkstra (se a sorgente unica)

• Algoritmo di Bellman-Ford (reti con archi negativi)

ALGORITMO PER DETERMINARE IL MASSIMO FLUSSO / MINIMO TAGLIO:

• Algoritmo di Ford e Fulkerson (su rete originaria)

• Algoritmo dei cammini aumentanti (su rete residua)

ALGORITMI PER DETERMINARE IL MINIMO ALBERO RICOPRENTE:

• Algoritmo di Prim-Dijkstra

• Algoritmo di Kruskal (se ci viene fornita la lista degli archi in ordine crescente)

CONDIZIONI DI OTTIMALITÀ:

• n-1 sugli archi fondamentali

• m - (n-1) sui cicli fondamentali

Per il grafo G = (V, E) pesato sugli spigoli riportato nella seguente figura determinare un albero ricoprente di peso minimo con l'algoritmo di Prim.

Certificare l'ottimalità della soluzione.

Tabella dell'algoritmo

S.m. degli archi dell'albero ricoprente

z(T_a*) = 116

Applicando l'algoritmo più opportuno, individuare un albero di cammini minimi dal nodo s per la rete riportata nella seguente figura, dove il valore associato ad ogni arco ne rappresenta il costo.

VERIFICHIAMO L'ACICLICITÀ DELLA RETE CON L'ORDINAMENTO TOPOLOGICO

IEN | 19 it. | 29 it.

1 | 0 | s

2 | 1 | 1 | Non possiamo completare la numerazione, quindi è presente un ciclo.

(*POI ogni 1 inserire, estrarre il nodo con etichetta minore e aggiungere a lista output archi uscenti

USIAMO QUINDI L'ALGORITMO DI DIJKSTRA, CHE RISULTA EFFICACE ANCHE NEI GRAFI CICLICI CON COSTI POSITIVI

IEN | 29 it. | 39 it. | 49 it. | 59 it. | 69 it. | 79 it. | 89 it.

L | s,4 | a,c(f) | a,c,d(f) | d,a,e(f,g) | d,e(a,c,f) | b,e,g(f) | l,e,b(f) | l,g(f)

s | 0

a | 2 | a,c | 10; 5

b |*

c | 2; 9

d | 6; a | c

e | 5 | 5; a, c | e

f | f

g | 6; b

*

Rileggiamo con la tabella per controllare l'algoritmo

VERIFICHIAMO L'OTTIMITÀ TRAMITE LE CONDIZIONI DI BELLMAN

PER OGNI ARCO DELLA RETE DEV'ESSERE d^*_k+d_i+c_ij∀(i

VERIFICHIAMO LA CONDIZIONE SUGLI ARCHI NON D'ALBERO:

(s,a) d_a+d_c

(s,f) d_c+d_f

(s,e) d_c+d_e

(i,a) d_e

(i,a) d_i

(e,e) d_e

(o,b) d_i

(o,c) d_c

(e,i)

Tutti OK

ESERCIZIO 7

DISENIAMO LA RETE RESIDUA R(x):

Ricordiamo = ( − ) +

RICERCA CAMMINI AUMENTANTI CON LA RICERCA IN AMPIEZZA

1^a ITER.

= 1

= 4

= 1

_s→t^I = (s, a, e, t) con δ^I = 1

2^a ITER.

MODIFICO LA RETE RESIDUA

R²(x)

1 4 2

_s→t^II = (s, b, e, t) con δ^II = 2

10. Data un’arborescenza esterna capacità T = (N(T), A(T), u) e radicata in s è N(T), con capacità u_ij per ogni (i,j) è A(T), si consideri il problema di determinare il massimo flusso da s a t, per ogni t è N(T)\\s. Per ognuna delle seguenti affermazioni dire se è vera o falsa.

• a) Il valore del massimo flusso da s a t è pari alla somma delle capacità degli archi che appartengono al cammino (s, ..., t). R: F
• b) Il valore del massimo flusso da s a t è pari al minimo delle capacità degli archi che appartengono al cammino (s, ..., t). R: V
• c) Il valore del massimo flusso da s a t è pari al massimo delle capacità degli archi che appartengono al cammino (s, ..., t). R: F

11. Si consideri il grafo bipartito B = (X ∪ Y, E) con X = , Y =

• E={, , , , , , , , }. Verificare se esso ammette un abbinamento Y-completo (cioè tale che ogni vertice di Y è abbinato ad uno di X), e in caso negativo fornire un insieme Q ≤ Y che viola la condizione di Hall. Determinare inoltre un vertex cover di cardinalità minima e un insieme stabile di cardinalità massima di B. Risolvere l’esercizio tramite l’algoritmo dei cammini alternati aumentati c/o riconducendo il problema ad un problema di massimo flusso su una opportuna rete. Certificare l’ottimalità della soluzione ottenuta. Risolvere l’esercizio anche per il grafo bipartito B’ = (X ∪ Y, E’) con E’ = E\{(3, d), (3, e)} ∪ {(2, d)}.

|E X: X = {a, b, c, d, e, f}

|E Y: Y = {1, 2, 3, 4, 5}

Condizione necessaria affinché il grafo bipartito ammetta abbinamento Y-completo è che:

|Y| ≤ |X|

In questo caso è soddisfatta.

Risolviamo il problema del massimo abbinamento con l’alg. dei cammini alternati aumentati.

Guardando solo Y a sinistra e X a destra.

1^a iter.

• 1 - a
• Ok ho trovato nel cammino alterato aumentato (inizio su un vertice esposto su Y e termina un vertice esposto su X)
• P^I = {(a, b)}
• M^I = M^I ⊕ P^I = M\{(a, b)}
• 2 - c
• M^I = M^I Ξ P^I = M\{(a, b), (c, 2)}