Lezionidi RicercaOperativa Lezionen 18 °

Lezione n

°

18

- Teoria dei grafi: definizioni di base - Problema del flusso a costo minimo

R. Cerulli

–

Lezioni di Ricerca Operativa

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

! V={v₁,...,v_n} l’insieme degli n Nodi di G

! E={e₁,..,e_m}ÍVxV l’insieme degli m Archi non orientati di G

Ogni arco non orientato e_k=(v_i,v_j) di G corrisponde ad una

coppia non ordinata di nodi v_i e v_j di G. I nodi v_i e v_j sono gli

estremi dell’arco e_k.

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

Un esempio: G=(V,E)

v

v

v

v

v

e

e

e

e

e

e

e

V = {v

,v

,v

,v

,v

}

E = {e

,e

,e

,e

,e

,e

,e

}

e

=(v

,v

) e

=(v

,v

) …

Definizioni di base

:

! un arco (v,v) è detto loop

! un arco e=(u,v)ÎE si dice incidente su u e su v ! due nodi u,vÎV sono detti adiacenti Û (u,v)ÎE

! due archi e₁,e₂ÎE sono detti adiacenti Û e₁=(u,v) ed e₂=(v,w)

(hanno un estremo in comune)

! l’insieme di nodi N(u)={vÎV: v adiacente a u} è detto intorno

di u in G

! l’insieme di archi d(u)={eÎE: e incide su u} è detto stella di u

in G

! |d(u)| è detto grado del nodo u

v₁ v₅ v₃ v₂ v₄ e₁ e₂ e₃ e₄ e₅ e₆ e₇

I grafi sono un mezzo per rappresentare relazioni binarie Ad esempio:

! due città connesse da una strada

! due calcolatori connessi in una rete telematica

! due persone legate da una relazione di parentela (come,

padre-figlio)

! due persone che condividono una stanza

! il collegamento tra due componenti elettronici

! un’operazione che deve essere eseguita da una certa

macchina

! ...

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

Ad esempio:

! determinare il percorso più breve che connette due città

! determinare come connettere nella maniera più

economica (più efficiente) un insieme di calcolatori in una rete telematica

! assegnare un insieme di operazioni ad un insieme di

macchine

! determinare il percorso più conveniente da far percorrere

ad una flotta di veicoli commerciali per effettuare delle consegne e quindi rientrare al deposito

! ...

Grafi e Sottografi

! G’=(V’,E’) è detto sottografo di G=(V,E) ⟺ Ø V’ ⊆ V

Ø E’ ⊆ E e (v_i,v_j) ∈ E’ ⟹ v_i,v_j ∈ V’

! G’=(V’,E’) è detto sottografo indotto da V’ in G=(V,E) ⟺ Ø V’⊆V

Ø "u,v∈V’ se (u,v) ∈ E allora (u,v) ∈ E’

Grafo semplice:

Non esistono “loop” o archi paralleli (ossia tra due nodi ci può essere più di un arco).

Esempio

v

v

v

v

v

e

e

e

e

e

e

e

G=(V,E)

v

v

v

v

e

e

Esempio

v

v

v

v

v

e

e

e

e

e

e

e

G=(V,E)

v

v

v

v

e

e

e

e

Grafo Bipartito

G è detto grafo bipartito se esiste una partizione di V in due sottoinsiemi V₁ e V₂ tali che:

! V₁ÇV₂ = Æ ! V₁ÈV₂ = V

! "e=(u,v)ÎE se uÎV₁ allora vÎV₂ oppure se uÎV₂ allora

vÎV₁

Esempio

! G è un grafo completo Û contiene tutti i possibili archi,

ovvero ú d(v)ú = n-1 "vÎV

! il numero di archi in un grafo completo è: 𝑛

2 = !(!#$) &

Esempio

grafo completo

Grafo Completo

! Dato G=(V,E), un nodo vÎV si dice connesso ad un nodo uÎV

se esiste un cammino tra u e v in G

! vÎV è connesso a v (riflessività)

! vÎV è connesso a uÎV Þ uÎV è connesso a vÎV (simmetria)

! se vÎV è connesso a uÎV e uÎV è connesso a wÎV Þ vÎV è

connesso a wÎV (transitività)

! Un grafo G=(V,E) è connesso Û tutti i suoi nodi sono connessi

tra loro.

! L’insieme V può essere partizionato in sottoinsiemi

C_i={vÎV : v è connesso a u, "uÎC_i }

! Il sottografo indotto da C_i in G è detto componente connessa

di G

! G è connesso Û possiede una sola componente connessa (v è

connesso a u , "v,uÎV)

Esempio

componenti

connesse

grafo connesso

! G=(V,E) è detto orientato se, dato V={v₁,...,v_n}, l’insieme degli

archi E={e₁,..,e_m} è formato da coppie ordinate di nodi.

Per un grafo orientato si ha che e_i=(v_k,v_h) ¹ e_j = (v_h,v_k) , e_i,e_jÎE

v

_e

v

i

Coda

Testa

L’arco e

si dice

uscente

da v

ed

entrante

in v

Esempio

_v

v

v

v

e

e

e

e

e

grafo orientato

! Fs(v) = {uÎV: (v,u) ÎE} è detto stella uscente di v ! Bs(v) = {uÎV: (u,v) ÎE} è detto stella entrante di v ! S(v) = Fs(v) È Bs(v) è detto stella di v

! le definizioni di sottografo, sottografo indotto e componente

connessa di un grafo orientato sono analoghe a quelle date per

! Dato G=(V,E), un nodo vÎV si dice fortemente connesso ad

un nodo uÎV se esiste una path (cammino orientato) tra v e u in G.

! vÎV è connesso a v (riflessività)

! se vÎV è fortemente connesso a uÎV e uÎV è fortemente

connesso a wÎV Þ vÎV è fortemente connesso a wÎV (transitività)

! Un grafo G=(V,E) è fortemente connesso Û tutti i suoi nodi

sono fortemente connessi tra loro.

Esempio

v

v

v

Componenti fortementi connesse

Ci sono in G componenti fortemente connesse?

v

v

v

v

G

v

Rappresentazioni di un Grafo

! Liste di adiacenza:

ad ogni vertice è associata la lista dei vertici adiacenti (può essere una tabella o una lista concatenata).

! Matrice di adiacenza (n x n) :

a_ij = 1 se (v_i, v_j) Î E, a_ij = 0 altrimenti

! Matrice di incidenza (n x m) :

•

Vantaggi: permette di scorrere i nodi adiacenti a v in O(grado(v))

Svantaggi: inserimenti e cancellazioni su liste concatenate in O(grado(v))

•

Vantaggi: Inserimenti e cancellazioni in O(1)

Svantaggi: permette di scorrere i nodi adiacenti a v in O(n)

•

Matrice di Incidenza dei Grafi

! Sia G=(V,E) un grafo non orientato con |V|=n ed |E|=m.

Denotiamo con A=[a_ij], con i=1,...,n e j=1,...,m, la matrice di

incidenza di G, dove:

𝑎

= #

1 𝑠𝑒 𝑣

è 𝑢𝑛 𝑒𝑠𝑡𝑟𝑒𝑚𝑜 𝑑𝑖 𝑒

0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖

Esempio

v

v

v

v

e

e

e

e

e

matrice di incidenza di un grafo non orientato

Matrice di Incidenza dei Grafi Orientati

! Sia G=(V,E) un grafo orientato con |V|=n ed |E|=m.

Denotiamo con A=[a_ij], con i=1,...,n e j=1,...,m, la matrice di

incidenza di G, dove:

𝑎

= 3

1

𝑠𝑒 𝑣

è 𝑐𝑜𝑑𝑎 𝑑𝑖 𝑒

(𝑎𝑟𝑐𝑜 𝑢𝑠𝑐𝑒𝑛𝑡𝑒 𝑑𝑎 𝑣

)

−1 𝑠𝑒 𝑣

è 𝑡𝑒𝑠𝑡𝑎 𝑑𝑖 𝑒

(𝑎𝑟𝑐𝑜 𝑒𝑛𝑡𝑟𝑎𝑛𝑡𝑒 𝑖𝑛 𝑣

)

0

𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖

Esempio

v

v

v

v

e

_e

e

e

e

matrice di incidenza di un grafo orientato

Sia G=(V,E) un grafo connesso e orientato in cui:

Ø Ad ogni arco (i,j) è associato un costo c_ij che rappresenta il costo da

pagare per ogni unità di flusso che transita sull’arco (i,j).

Ø Ad ogni vertice v∈V è associato un valore intero b_v dove:

- b_v > 0 indica che il nodo v è un nodo di offerta

- b_v < 0 indica che il nodo v è un nodo di domanda

- b_v = 0 indica che il nodo v è un nodo di passaggio

Ø La somma di tutti i b_v deve essere uguale a zero (condizione di

bilanciamento). Ciò che viene prodotto dalle sorgenti viene consumato dalle destinazioni.

Nel problema del flusso a costo minimo bisogna far giungere la merce prodotta dai nodi di offerta ai nodi di domanda minimizzando i costi di trasporto.

Problema del Flusso a Costo Minimo: Formulazione

𝑥_!" = quantità di flusso che transita sull’arco (i,j)

𝑐_!" = costo di trasporto di una unità di flusso sull’arco (i,j)

𝑏_! = valore intero associato al nodo i (ne definisce il ruolo nel problema): 𝑏_! > 0: nodo di offerta

𝑏_! < 0: nodo di domanda 𝑏 = 0: nodo di passaggio

Consideriamo un grafo orientato G=(V,E) rappresentante una rete di trasporto. L’obiettivo è quello di trasportare, al minimo costo, determinate quantità di merce (unità di flusso) dai nodi di offerta a quelli di domanda (eventualmente transitando per dei nodi di passaggio).

Abbiamo:

! 𝑏_! > 0: nodo di offerta

𝑏_! < 0: nodo di domanda 𝑏_! = 0: nodo di passaggio

! Un costo c_ij ≥ 0 per ogni arco

(costo per il trasporto di una unità di flusso) 1 2 3 4 5 5 2 -3 -4 0 6 1 3 4 1 4 3 2

Consideriamo una variabile x_ij ≥ 0, ∀(i,j) ∈ E, rappresentante la quantità di flusso che attraverserà tale arco nella soluzione.

1 2 3 4 5 5 2 -3 -4

0

Problema del Flusso a Costo Minimo: Esempio

La matrice A dei vincoli del modello matematico corrisponde alla matrice di incidenza nodo-arco del grafo G.

1 2 3 4 5 5 2 -3 -4

0

Problema del Flusso a Costo Minimo: Esempio

A (1,2) (1,3) (2,5) (3,2) (3,4) (4,1) (4,2) (4,5) 1 1 1 0 0 0 -1 0 0 2 -1 0 1 -1 0 0 -1 0 3 0 -1 0 1 1 0 0 0 4 0 0 0 0 -1 1 1 1 5 0 0 -1 0 0 0 0 -1

Soluzione 1 Costo: (6*5)+(4*1)+(3*2)=40 Soluzione 2 Costo: (1*5)+(2*5)+(1*4)+(3*3)=28 1 2 4 5 5 2 -3 -4 6 1 2 4 3 1 Flusso 5 Flusso 5-4=1 Flusso 2 4 3 5 5 -3 -4 6 1 2 4 3 1 Flusso 4 Flusso 1+2=3 4 3 Flusso 5 Flusso 5 3 1 2 4 3

In forma matriciale:

Osservazioni:

1. La matrice A è la matrice di incidenza nodo-arco con dimensione nxm. Ogni colonna 𝑎_') è associata all’arco (i,j), ed in

particolare abbiamo che: 𝑎_') = 𝑒_' − 𝑒₎

2. Il rango di questa matrice è: r(A) = n - 1

(e_i vettore colonna con tutti 0 eccetto un 1 nella posizione i-ma)

Problema del Flusso a Costo Minimo:

Formulazione

min 𝑐

𝑥

A𝑥 = 𝑏

Definizione (totale unimodularità): Una matrice si dice totalmente

unimodulare (TU) se tutte le sue sottomatrici quadrate (di ogni ordine) hanno

determinante uguale a 0, 1 o -1.

Matrici Totalmente Unimodulari

Osservazione 1: Tutte le componenti di una matrice totalmente unimodulare sono uguali a 0, 1 o -1 dato che ogni suo elemento è una particolare matrice quadrata di ordine 1x1.

Osservazione 2: Sia A una matrice i cui elementi sono tutti uguali a 0, +1 o -1 e lungo ogni colonna non vi sono più di due elementi diversi da 0. Allora A è TU se e solo se l’insieme delle righe di A può essere suddiviso in due sottoinsiemi Q₁ e Q₂ tali che, se una colonna contiene due elementi diversi da 0, allora:

! se i due elementi hanno lo stesso segno allora una delle due righe in cui si

trovano è in Q₁ e l’altra in Q₂ ;

! se hanno segno opposto le righe corrispondenti sono entrambe contenute

Teorema 1: Sia A una matrice i cui elementi sono tutti uguali a 0, +1 o -1 e lungo ogni colonna non vi sono più di due elementi diversi da 0. Se nelle colonne con due elementi diversi da 0 la somma di tali elementi è uguale a 0 (ovvero un elemento è uguale a +1 e l’altro a -1), allora A è TU.

Matrici Totalmente Unimodulari

Corollario 1: Le matrici di incidenza nodo-arco di un grafo orientato sono totalmente unimodulari.

Dimostrazione: Dall’osservazione 2, è sufficiente porre Q₁= {tutte le righe di A } e Q₂ = ∅. Il corollario ci dice ad esempio che tutte le matrici di incidenza nodo-arco di un grafo orientato sono matrici TU. ∎

A (1,2) (1,3) (2,5) (3,2) (3,4) (4,1) (4,2) (4,5)

1 1 1 0 0 0 -1 0 0

2 -1 0 1 -1 0 0 -1 0

3 0 -1 0 1 1 0 0 0

Inoltre 𝑐𝑜𝑓 𝐴_#!" = (−1)!$"2 𝑚𝑖𝑛𝑜𝑟(𝐴_#!")

Matrici Totalmente Unimodulari

Corollario 2: Sia A la matrice di incidenza nodo-arco di un grafo orientato G, e sia 𝐴_# una sottomatrice quadrata di A non singolare. Si ha che 𝐴%&_# ha tutte le componenti intere.

Dimostrazione: Dal Corollario 1 sappiamo che la matrice A è totalmente

unimodulare e quindi tutte le sue componenti hanno valore -1,0,1. Poichè 𝐴_# è una sottomatrice di A, tutte le sue componenti sono uguali a -1,0,1. Per calcolare la matrice inversa utilizziamo la formula:

Quindi '() *!" è sempre un intero.

∎

= -1,0,+1 (𝑝𝑒𝑟𝑐ℎè 𝐴_#!" è 𝑇𝑈)

Teorema 2: I vertici del poliedro, definito dal modello matematico del problema del flusso a costo minimo, hanno coordinate intere.

Matrici Totalmente Unimodulari

Dimostrazione: Sia A_B una sottomatrice di A dimensioni (n-1)x(n-1) non singolare. La soluzioni di base ammissibili associate ad A_B ha la struttura 𝑥 =

𝑥_#

𝑥₀ = 𝐴# %&_𝑏

0 e corrisponde ad un vertice del poliedro. Dobbiamo quindi dimostrare che il vettore 𝐴_#%&𝑏 ha tutte le componenti intere.

Dal Corollario 2 sappiamo che 𝐴_#%& ha tutte le componenti intere. Inoltre, per ipotesi, 𝑏 ha tutte le componenti intere, quindi 𝐴%&_# 𝑏 ha tutte le componenti intere.