Lezione n°18

(1)

Lezione n°18

 Teoria dei grafi: definizioni di base

 Problema del flusso a costo minimo

R. Cerulli – F. Carrabs

Lezioni di Ricerca Operativa

Università degli Studi di Salerno

(2)

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_jdi 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

Teoria dei Grafi: Concetti Fondamentali

(3)

Un esempio: G=(V,E)

V = {v₁,v₂,v₃,v₄,v₅}

E = {e₁,e₂,e₃,e₄,e₅,e₆,e₇}

e₁ =(v₁,v₅) e₂ =(v₁,v₂) …

v₁

v₅

v₃ v₂

v₄ e₁

e₂

e₃ e₄

e₅

e₆

e₇

(4)

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₇

(5)

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

 ...

Teoria dei Grafi: Concetti Fondamentali

(6)

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

 ...

Applicazioni

(7)

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).

(8)

Esempio

G=(V,E)

è un sottografo di G G’

v₁

v₅

v₃ v₂

v₄ e₁

e₂

e₃ e₄

e₅

e₆ e₇

v₁

v₅

v₃ v₂

e₁

e₂

(9)

Esempio

G=(V,E)

è un sottografo indotto di G G’

v₁

v₅

v₃ v₂

v₄ e₁

e₂

e₃ e₄

e₅

e₆ e₇

v₁

v₅

v₃ v₂

e₁

e₂

e₃ e₆

(10)

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

grafo bipartito grafo non bipartito

(11)

 G è un grafo completo Û contiene tutti i possibili archi, ovvero ú d(v)ú = n-1 vÎV

 il numero di archi in un grafo completo è:



Esempio

grafo completo

Grafo Completo

(12)

 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.

Grafo Connesso

(13)

 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

Componenti Connesse

(14)

 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

Coda Testa

L’arco e_i si dice uscente da v_h ed entrante in v_k

Grafi Orientati

v_h e_i v_k

(15)

Esempio

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 i grafi non orientati

v₁

v₄ v₃

v₂ e₁ ^e₂

e₃

e ₆ e₄

e₅

(16)

 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.

Componenti Fortemente Connesse

(17)

Esempio

Componenti fortementi connesse

Ci sono in G componenti fortemente connesse?

G v₁

v₄ v₃

v₂ v₁

v₄ v₃

v₂

(18)

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) : a_ij = 1 se v_i Î e_j, a_ij = 0 altrimenti

(19)

• Lista di adiacenza: memoria O(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))

• Matrice di adiacenza: memoria O(n²)

Vantaggi: Inserimenti e cancellazioni in O(1)

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

• D.: matrice di incidenza ?

Rappresentazioni di un Grafo: Vantaggi e Svantaggi

(20)

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:

�_��={¹ ^��^� ^è ��  _�

¿0 ��



(21)

Esempio

v₄

v₁

v₂

v₃ e₁ e₂

e₃ e₄

e₅

matrice di incidenza di un grafo non orientato

Matrice di Incidenza dei Grafi

(22)

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:

�_��=

{

¹ ^{�� }^� ^è ^{�� } ^�⁽�� _�)

¿ −1�� _� è��  _� (�� _�)

¿0 ��



(23)

Esempio

v₃ v₁

v₂

v₄

e₁ e₂

e₃ e₄

e₅

matrice di incidenza di un grafo orientato

Matrice di Incidenza dei Grafi Orientati

(24)

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

Problema del Flusso a Costo Minimo

(25)

Problema del Flusso a Costo Minimo: Formulazione

min ∑

(�, �)∈ �

�_�� �_��



�∈ ��(�)∑

�_��− ∑

�∈ ��(�)

�_��=�_� �=1,… ,�



= 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):

: nodo di offerta : nodo di domanda : nodo di passaggio



�_��≥ 0 ∀ (� , � )∈ �

 Intere?

(26)

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:

 : nodo di offerta : nodo di domanda : 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

Problema del Flusso a Costo Minimo: Esempio

(27)

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

6

1

3 4 1

4 3

2



(28)

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

6

1

3 4 1

4 3

2

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

(29)

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

2

-3 6 -4

1

2

4 3 Flusso 5 1

Flusso 5

Flusso 5-4=1 Flusso

5-4=1

Flusso 2 Flusso

2 4

3

5

2

-3 6 -4

1

2

4 3

1 Flusso 4

Flusso 4

Flusso 1+2=3 Flusso 1+2=3 4

3 Flusso 5

Flusso 5 Flusso 5 Flusso 5

3

1 2

3 4

(30)

In forma matriciale:

Osservazioni:

1. La matrice A è la matrice di incidenza nodo-arco con dimensione n^xm. 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



(31)

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 in Q o entrambe in Q .

(32)

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.

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

4 0 0 0 0 -1 1 1 1

Q₁ Q₂=∅

(33)

Inoltre 

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 

Poiché è TU e non singolar, .

(34)

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

Dimostrazione: Sia A_B una sottomatrice di A dimensioni (n-1)x(n-1) non singolare. La soluzioni di base ammissibili associate ad A_Bha la struttura 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.



∎