• Progetto di servizi logistici

Ottimizzazione Combinatoria A. A. 2007-2008

Docente:

Mara Servilio

Orario delle lezioni: Mercoledì 11:30-13:30; Giovedì 11:30-13:30

Orario di ricevimento:

giovedì 15:00-17:00

Sito web: http://www.di.univaq.it/~oil

Testi di riferimento

1. A. Sassano, Modelli e Algoritmi della Ricerca Operativa 2. L. A. Wolsey, Integer Programming

3. W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization

Applicazioni

• Progetto di servizi logistici

• Progetto di una rete di trasmissione radiotelevisiva

• Gestione del servizio di trasporto urbano per handicappati

• Pianificazione della produzione

• Gestione delle partenze e degli arrivi in un aeroporto

Progetto di servizi logistici

L’azienda di spedizioni Ex-press, proprietaria di alcuni treni

merci, intende realizzare un servizio di spedizioni tra L’Aquila e Pescara via ferrovia.

Pertanto:

1. Chiede gli orari disponibili alla società che gestisce la rete ferroviaria (Rete Ferroviaria Italiana) e i costi relativi.

2. Configura il servizio che massimizza il guadagno.

Il gestore della rete

1. Studia la fattibilità delle richieste della società.

2. Pianifica alcuni orari alternativi.

3. Definisce i prezzi di ogni alternativa.

Ex-press ha un problema di ottimizzazione

Dati

–Un insieme di orari O, ognuno con il proprio costo –Un insieme di treni T, ognuno con il proprio “profitto”

Problema

Assegnare un sottoinsieme T’ ⊆ T di treni a un sottoinsieme

di orari O’ ⊆ O in modo da massimizzare il guadagno

(somma dei profitti – somma dei costi) e rispettando i

vincoli “fisici”.

RFI ha un problema di ottimizzazione

Dati

• L’orario di un nuovo treno

• L’intervallo di tempo necessario a percorrere ogni tratta della linea

• L’intervallo di tempo minimo e massimo di sosta in ogni stazione

• Standard di sicurezza (due treni che

viaggiano sulla stessa linea devono essere separati da almeno k metri, ecc.)

• L’orario esistente Problema

Trovare (se esiste !) un orario che contenga il nuovo

treno e che rispetti gli standard di sicurezza

Problema di Ottimizzazione

Siano

• U = insieme universo, ossia un insieme di soluzioni, decisioni e alternative.

• F ⊆ U = insieme ammissibile definito tramite una serie di relazioni dette vincoli.

• f: U → ℜ = funzione obiettivo.

• Direzione di ottimizzazione: minimo o massimo.

Problema di ottimizzazione (in forma di minimo)

Trovare un elemento x∈F tale che f(x) < f(y) per ogni y∈F.

v = f(x) = valore ottimo

x = soluzione ottima

Problema di Ottimizzazione Combinatoria

Siano

• N = {1,2,…,n} insieme finito.

• c vettore di pesi con coordinate c

definite per ogni j ∈N

• Insieme universo: U = {tutti i possibili 2

sottoinsiemi di N}

• Famiglia ammissibile: ℑ = {sottoinsiemi F di U che soddisfano una certa proprietà ℘}.

Problema di ottimizzazione combinatoria (in forma di minimo) min { Σ ^c

^{: S∈ℑ}}

S⊆N j∈S

Problema dell’assegnamento

Consideriamo 3 artigiani e 3 lavori da realizzare.

I costi richiesti da ogni artigiano per ogni lavoro sono riportati nella seguente tabella

10 15 12 2

14 7 10

1

3 2 1

A L

9 18 20 3

Problema: Assegnare esattamente un artigiano ad un lavoro in

modo da minimizzare i costi totali.

Insiemi ammissibili

1. {(a₁,l₁); (a₂,l₂); (a₃,l₃)} di costo 34

3. {(a₁,l₃); (a₂,l₁); (a₃,l₂)} di costo 37 4. {(a₁,l₃); (a₂,l₂); (a₃,l₁)} di costo 49 5. {(a₁,l₂); (a₂,l₁); (a₃,l₃)} di costo 28 6. {(a₁,l₁); (a₂,l₃); (a₃,l₂)} di costo 38 2. {(a₁,l₂); (a₂,l₃); (a₃,l₁)} di costo 44

10 15 12 2

14 7 10

1

3 2 1

A L

9 18 20 3

La soluzione ottima ha valore 28.

I possibili assegnamenti, e quindi i possibili insiemi ammissibili, sono 3!

In generale, esistono n! insiemi ammissibili.

Problema dell’assegnamento

Problema dello zaino

Supponiamo di avere a disposizione un budget b per gli investimenti del 2008.

Associamo ad ogni possibile investimento j

• un costo c

> 0;

• un guadagno p

> 0.

Problema: Scegliere l’insieme di investimenti da effettuare in

modo da massimizzare il guadagno e senza eccedere il budget a

disposizione.

4 1 8 12 4

14 3

10 2

p c

1 2 3

Dimensione dello zaino: b = 5

Insiemi ammissibili

∅, {1}, {2}, {3}, {4}, {1, 2}, {1, 4}, {2, 4}, {3,4}

Soluzione ottima {1, 2} di valore 24

Il numero di insiemi ammissibili è pari al numero di possibili sottoinsiemi di un insieme di n oggetti, ossia 2ⁿ.

Se b =

Σ

j =1 n

Problema dello zaino

Problema del commesso viaggiatore (TSP)

Consideriamo n punti nel piano.

Per ogni coppia di punti (i, j) definiamo un costo c

> 0.

Problema: Determinare il tour di costo minimo.

5 3

8 7

4 6

1 2

Insiemi ammissibili: tutti i possibili tour del grafo.

In un grafo con n nodi esistono (n-1)!/2 tour.

2

5 4 6 1

3

8 7

Problema del commesso viaggiatore

(TSP)

Proprietà dei problemi di OC

1. Tutti i problemi di OC sono definiti su insiemi ammissibili finiti e numerabili.

2. Il valore della funzione obiettivo può essere calcolato in corrispondenza di ogni insieme ammissibile.

Esiste un algoritmo “universale” per i problemi di OC che si chiama enumerazione totale.

E’ possibile utilizzare l’enumerazione totale nella pratica?

Proprietà dei problemi di OC

Le operazioni eseguite da un moderno calcolatore in un anno sono pari a 3.15 ×10

.

4.02×10

1.07 × 10

1000000 31.62

9.97 1000

9.33×10

1.27 × 10

10000 10.00

6.64 100

3.6×10

1.02×10

100 3.16

3.32 10

n!

2

n

n

log n

n

L’algoritmo di enumerazione totale impiegherebbe circa 2 anni per

risolvere un problema di commesso viaggiatore con 20 punti nel

piano.

Obiettivi di questo corso

Studiare tecniche matematiche che consentano di progettare algoritmi “efficienti” per i problemi di OC.

Cosa si intende per algoritmo efficiente?

1. Algoritmi ammissibili a complessità polinomiale (Assegnamento).

2. Algoritmi ammissibili a complessità pseudo-polinomiale (Zaino).

3. Algoritmi ammissibili a complessità non polinomiale (TSP).

4. Algoritmi approssimati a complessità polinomiale (Zaino).

5. Algoritmi euristici (Zaino, TSP).

Obiettivi di questo corso

Modellare problemi decisionali che derivano da

applicazioni del mondo industriale come

problemi di ottimizzazione.

Parte I:

Insiemi indipendenti e coperture

Problema 1: Il ballo (Berge)

• Ad un ballo sono presenti n ragazzi e n ragazze.

• Ciascun ragazzo riconosce k fidanzate tra le ragazze presenti.

Domanda: è possibile far ballare ciascun ragazzo con una delle sue fidanzate e ciascuna ragazza con uno dei suoi fidanzati?

• Ciascuna ragazza riconosce k fidanzati tra i ragazzi

presenti.

Problema 1: Il ballo (Berge)

Formulazione: 4 ragazzi/ragazze con 3 fidanzate/fidanzati.

Asia

Bianca

Chiara

Daria

Alessio

Bruno

Cristian

Davide

U = insieme degli archi del grafo

ℑ = famiglia degli insiemi di archi che

toccano ogni vertice esattamente

una volta.

Problema 2: Le torri

• Consideriamo una scacchiera n×n.

• Due torri si danno scacco se giacciono sulla stessa riga (colonna) della scacchiera.

Domanda: Qual è il massimo numero di torri che è

possibile disporre sulla scacchiera senza che esse si

diano scacco reciproco?

Problema 2: Le torri

Formulazione: Due torri si danno scacco se si trovano sulla stessa riga o colonna.

U = insieme degli archi del grafo

ℑ = famiglia degli insiemi di archi che

toccano ogni vertice non più di una volta.

A B C D 1

2 3 4

A

B

C

D

1

2

3

4

Grafo intersezione righe-colonne

Problema 3: La battaglia di Inghilterra (Berge)

• Nel 1941 le squadriglie inglesi erano composte di aerei biposto, ma alcuni piloti non potevano formare una coppia per problemi di lingua o di abitudini.

Domanda: Dati i vincoli di incompatibilità tra coppie di

piloti, qual è il massimo numero di aerei che è possibile

far volare simultaneamente?

Formulazione: Grafo di compatibilità dei piloti U = insieme degli archi del grafo

ℑ = famiglia degli insiemi di archi che toccano ogni vertice al più

una volta.

Problema 3: La battaglia di Inghilterra (Berge)

Alì

Bob

Charlie

David

Evgenij

Fëdor Alì

Charlie Bob

Evgenij

Abbinamento

Definizione: Dato un grafo G = (V, E), un abbinamento (matching) è un sottoinsieme A ⊆ E di archi a due a due non adiacenti.

In ciascuno dei problemi precedenti la soluzione corrisponde a un abbinamento su un grafo.

Asia

Bianca

Chiara

Daria

Alessio

Bruno

Cristian

Davide

A

B

C

D

1

2

3

4

Alì

Bob

David

Fëdor Alì

Charlie Bob

Evgenij

Tipologie di abbinamento

Definizione: Se |A| > |B| per ogni abbinamento B di G, allora A

si dice massimo.

Definizione: Se G è bipartito, allora anche A si dice bipartito.

Definizione: Se |A| = |V|/2, allora A si dice perfetto.

Asia

Bianca

Chiara

Daria

Alessio

Bruno

Cristian

Davide

A

B

C

D

1

2

3

4

Alì

Bob

David

Fëdor Alì

Charlie Bob

Evgenij

Insieme indipendente

Definizione: Dato un grafo simmetrico G = (V,E), un qualunque

sottoinsieme S di vertici si dice indipendente se esso è costituito da elementi a due a due non adiacenti.

• S è detto insieme stabile (stable set)

Definizione: Un insieme indipendente (abbinamento) X si dice

massimale se ogni elemento di V–X (A–X) è adiacente ad almeno un elemento di X.

Definizione: Un insieme indipendente X^*

si dice massimo se

|X

| > |X|, per ogni insieme indipendente X di G.

Esempi

Osservazione: L’insieme vuoto è un insieme indipendente.

Insieme indipendente massimale

Abbinamento massimale

Esempi

Insieme indipendente massimo

Abbinamento massimo

Copertura

Definizione: Dato un grafo simmetrico G = (V, E), un

qualunque sottoinsieme T di vertici (F di archi) tale che ogni spigolo di E (vertice di V) incide su almeno un elemento di T (di F) si dice copertura.

• T è detto insieme trasversale (vertex cover).

• F è detto edge-cover.

Definizione: Una copertura X si dice minimale

se X – {x} non è una copertura per ogni x∈X.

Definizione: Una copertura X^*

si dice minima se |X

| < |X|, per ogni

insieme copertura X di G.

Esempi

Osservazione: L’insieme dei nodi V e l’insieme degli archi E di

un grafo sono rispettivamente trasversale e edge-cover.

Trasversale minimale

Edge-cover minimale

Esempi

Trasversale minimo

Edge-cover minimo

Disuguaglianze duali deboli

Indichiamo con

• α(G) insieme stabile massimo di G.

• µ(G) abbinamento massimo di G.

• ρ(G) edge cover minimo di G.

• τ(G) trasversale minimo di G.

Teorema: Per un grafo G valgono le seguenti disuguaglianze 1. α(G) < ρ(G)

2. µ(G) < τ(G)

Disuguaglianze duali deboli

Dimostrazione: Siano

• X insieme indipendente di G, e

• Y edge-cover di G.

Poiché Y copre V, ogni elemento di X incide su almeno un elemento di Y.

D’altra parte, nessun elemento di Y copre contemporaneamente due elementi di X altrimenti i due elementi sarebbero adiacenti e quindi non potrebbero appartenere all’insieme indipendente X.

Pertanto, per ogni x∈X esiste un distinto y∈Y che lo copre, e quindi

|X| < |Y|.

Riscrivendo la precedente relazione per gli insiemi massimi X^* e Y^*, si ottiene

α(G) < ρ(G) Scambiando il ruolo di V ed E, si ottiene

µ(G) < τ (G)

Disuguaglianze duali deboli

Esempio

trasversale e abbinamento

µ(G) = 3 τ (G) = 3

µ(G) = 3 τ (G) = 3

Disuguaglianze duali deboli

Forse valgono sempre con il segno “=“ ?

Esempio

indipendente e edge-cover

α(G) = 3 ρ(G) = 3

α(G) = 3 ρ(G) = 3

Disuguaglianze duali deboli

NO!!!

Forse valgono sempre con il segno “=“ ?

α(G) = 2 ρ(G) = 3

Teorema (Gallai 1959):

Per ogni grafo G con n nodi si ha:

α(G) + τ(G) = n (1)

Se inoltre G non ha nodi isolati

µ(G) + ρ(G) = n (2)

Teorema di Gallai

Esempio (1)

Teorema di Gallai

Esempio (2)

Teorema (Gallai 1959):

Per ogni grafo G con n nodi si ha:

α(G) + τ(G) = n (1)

Se inoltre G non ha nodi isolati

µ(G) + ρ(G) = n (2)

Dimostrazione (1): Sia S un insieme indipendente di G. Allora V–S è un insieme trasversale.

τ(G) < |V–S^*| = n – α(G)

Dimostrazione

S

In particolare, |V–S|> τ (G).

Se consideriamo l’insieme indipendente massimo S^*, otteniamo da cui ricaviamo

α(G) + τ(G) < n.

Dimostrazione (1): Viceversa, sia T un insieme trasversale di G.

Allora V–T è un insieme indipendente.

α(G) > |V–T ^*| = n – τ(G) In particolare, |V–T|< α (G).

Se consideriamo l’insieme trasversale minimo T ^*, otteniamo

da cui ricaviamo

α(G) + τ(G) > n.

T

non coperto da T

α(G) + τ(G) = n.

Considerando la condizione ottenuta precedentemente, possiamo concludere che

Dimostrazione

Dimostrazione (2): Sia G un grafo privo di nodi isolati e sia A*

l’abbinamento massimo di G. Indichiamo con V_A* i nodi saturi rispetto ad A*.

Sia H un insieme minimale tale che ogni nodo in V–V_A* è estremo di qualche arco in H.

Segue che

Dimostrazione

V

|H| = |V–V_A*| = n – 2|A*|

Osserviamo che l’insieme C = H ∪ A* è un edge-cover di G.

Dimostrazione (2):

Sicuramente, |C| > ρ (G).

Quindi

Dimostrazione

ρ(G) < |C| = |A^*| + |H| = |A^*| + n – 2|A^*| = n – |A^*| = n – µ(G) da cui ricaviamo ρ (G) + µ(G) < n.

Dimostrazione (2): Sia C il minimo edge-cover su G (|C| = ρ(G)).

Sia H = (V, C) il sottografo indotto da C.

Valgono le seguenti proprietà:

1) H è un grafo aciclico.

Dimostrazione

Infatti, se H contenesse cicli allora C non sarebbe un edge-cover minimo.

Dimostrazione (2):

2) Ogni cammino in H è composto di al più due archi.

Dimostrazione

Infatti, se H contenesse un cammino con 3 archi sarebbe sempre possibile rimuovere un arco e ottenere ancora un edge-cover.

L’esistenza di un tale cammino contraddirebbe il fatto che C è minimo.

Dimostrazione (2):

Dalle proprietà precedenti concludiamo che il grafo H = (V, C)

Dimostrazione

• ha |V| = n vertici;

• ha |C| = ρ(G) archi;

• può essere decomposto in N componenti connesse aventi la forma di “stella”

Dimostrazione (2):

Consideriamo l’i-esima componente connessa di H. Essa avrà:

• s_i nodi, e

• s_i – 1 archi.

Dimostrazione

Pertanto

n =

Σ

i =1 N

ρ(G) =

Σ

i =1 N

Sia A un abbinamento con un arco per ogni componente di H. Si ottiene µ(G) > |A| = n – ρ(G) ⇒ ρ (G) + µ(G) < n

Considerando la condizione ottenuta precedentemente, possiamo concludere che

ρ (G) + µ(G) = n.

Massimo insieme stabile

Formulazioni di PLI

Dati: G = (V,E), |V| = n, |E| = m.

Variabili decisionali:

x

=

1 se il vertice i appartiene allo stabile S 0 altrimenti

Formulazione:

max Σ ^x

i∈V

x

+ x

< 1 ∀ (i, j) ∈ E

x

∈ {0,1} ∀ i ∈ V

Rilassamento lineare del massimo insieme stabile

Rilassamento lineare

max Σ ^x

i∈V

x

+ x

< 1 ∀ (i, j) ∈ E x

> 0 ∀ i ∈ V

STAB

Osservazione: La limitazione x

< 1 può essere omessa.

Indichiamo con α

(G) il valore della soluzione ottima di

STAB

.

Minimo edge cover

Formulazioni di PLI

Dati: G = (V,E), |V| = n, |E| = m.

Variabili decisionali:

y

=

1 se l’arco ij appartiene all’edge cover C 0 altrimenti

Formulazione:

min Σ ^y

ij∈E

y

∈ {0,1} ∀ (i, j) ∈ E

Σ ^y

^{> 1 ∀ i ∈ V}

ij∈∂(i)

Rilassamento lineare del minimo edge cover

Rilassamento lineare

y

> 0 ∀ (i, j) ∈ E

EDGE-C

Osservazione: La limitazione y

< 1 può essere omessa.

Indichiamo con ρ

(G) il valore della soluzione ottima di EDGE-C

.

min Σ ^y

ij∈E

Σ ^y

^{> 1 ∀ i ∈ V}

ij∈∂(i)

Dualità

Osservazione: I problemi STAB

e EDGE-C

costituiscono una coppia primale-duale.

Inoltre

α(G) < α

(G) e ρ

(G) < ρ(G) Pertanto

α(G) < α

(G) = ρ

(G) < ρ(G)

Massimo matching

Formulazioni di PLI

Dati: G = (V,E), |V| = n, |E| = m.

Variabili decisionali:

y

=

1 se l’arco ij appartiene al matching M 0 altrimenti

Formulazione:

max Σ ^y

ij∈E

y

∈ {0,1} ∀ (i, j) ∈ E

Σ ^y

^{< 1 ∀ i ∈ V}

ij∈∂(i)

Rilassamento lineare del massimo matching

Rilassamento lineare

y

> 0 ∀ (i, j) ∈ E

MATCHING

Osservazione: La limitazione y

< 1 può essere omessa.

Indichiamo con µ

(G) il valore della soluzione ottima di MATCHING

.

max Σ ^y

ij∈E

Σ ^y

^{< 1 ∀ i ∈ V}

ij∈∂(i)

Minimo trasversale

Formulazioni di PLI

Dati: G = (V,E), |V| = n, |E| = m.

Variabili decisionali:

x

=

1 se il vertice i appartiene al trasversale T 0 altrimenti

Formulazione:

min Σ ^x

i∈V

x

+ x

> 1 ∀ (i, j) ∈ E

x

∈ {0,1} ∀ i ∈ V

Rilassamento lineare del minimo trasversale

Rilassamento lineare

min Σ ^x

i∈V

x

+ x

> 1 ∀ (i, j) ∈ E x

> 0 ∀ i ∈ V

TRASV

Osservazione: La limitazione x

< 1 può essere omessa.

Indichiamo con τ

(G) il valore della soluzione ottima di

TRASV

.

Dualità

Osservazione: I problemi MATCHING

e TRASV

costituiscono una coppia primale-duale.

Inoltre

µ(G) < µ

(G) e τ

(G) < τ (G) Pertanto

µ(G) < µ

(G) = τ

(G) < τ (G)

Cammino alternante

Sia M un matching di G = (V, E).

Definizione: Un arco (i, j)∈E si dice

(libero) se

((i, j) ∉ M).

Definizione: Un vertice i∈V si dice

(libero) se su di esso incide (non incide) un arco di M.

Definizione: Un cammino P sul grafo G si dice alternante

rispetto a M se esso è costituito alternativamente da

spigoli accopiati e liberi.

Aumentare un matching

Teorema: Sia M un matching di G e sia P un cammino aumentante rispetto a M. La differenza simmetrica

M’ = (M – P) ∪ (P – M) = M ⊕ P

è un matching di cardinalità |M| + 1.

M-P

P-M P-M

Dimostrazione

Dimostrazione: Sia M un matching di G e sia P un cammino aumentante rispetto a M. L’insieme

M’ = (M – P) ∪ (P – M)

gode delle seguenti proprietà

1) M’ è un abbinamento. Infatti, se così non fosse allora esisterebbero almeno due archi adiacenti tra loro in M’.

Questi archi

1) Non possono appartenere entrambi ad M altrimenti M non sarebbe un matching.

2) Non possono appartenere entrambi a P–M perché P è alternante.

Dimostrazione

Dimostrazione:

Poiché stiamo supponendo che i due archi sono adiacenti, allora entrambi devono necessariamente appartenere a P, contraddicendo la definizione di M’.

Pertanto, l’unica possibilità è che un arco appartenga a

M e l’altro a P – M.

Dimostrazione

Dimostrazione:

2) M’ ha un elemento in più di M.

M – P

P – M

Teorema di Berge

Teorema (Berge,1957): Un M un matching di G è massimo se e solo se G non ammette cammini alternanti rispetto a M che siano anche aumentanti.

Dimostrazione (⇐): Segue immediatamente dal teorema precedente.

Dimostrazione (⇒): Supponiamo che G ammetta un matching M’ con un elemento in più di M.

Vogliamo dimostrare che allora esiste un cammino

aumentante per M.

Teorema di Berge

Dimostrazione (⇒):

Consideriamo il sottografo G’ di G individuato dall’insieme di archi

F = (M

∪M’)\ (M∩M’) e da tutti i loro estremi.

Poiché M e M’ sono matching, ogni vertice di G’ ha grado < 2.

Quindi le componenti connesse di G’ o sono percorsi o sono cicli.

Teorema di Berge

Dimostrazione (⇒):

Nessun ciclo può essere dispari altrimenti M e M’ non sarebbero due abbinamenti.

Non tutti i percorsi possono essere pari altrimenti |M| = |M’|.

Quindi, senza perdità di generalità, possiamo assumere che esista un percorso dispari che inizia e termina con un arco di

Questo percorso è aumentante per M.

Un possibile algoritmo

M = ∅ ∅ ∅; // Inizializzazione ∅ trovato = TRUE;

while (trovato) {

search (M, &trovato);

if (trovato)

aumenta (G, &M);

}

Come è fatta search (G, M, &trovato)?

Teorema del cammino aumentante

Consideriamo M ⊕ M*.

Teorema: Sia v un vertice esposto in un matching

esiste un cammino aumentante per

che parte da v, allora esiste un matching massimo avente v esposto.

Dimostrazione: Sia M* un matching massimo in cui v è

accoppiato.

Dimostrazione

Dimostrazione:

Poiché M e M* sono due abbinamenti e v è accoppiato in M*, si ha che M ⊕ M* non può contenere un cammino

v

perché aumentante per M.

v

Però, contiene un cammino

Pertanto, scambiando gli archi blu con quelli rossi è possibile ottenere da M* un altro abbinamento massimo con esposto.

Un possibile algoritmo (ΙΙ)

M = ∅ ∅ ∅; trovato = FALSE;//Inizializzazione ∅ for (v ∈ ∈ V) { ∈ ∈

if (v è esposto) {

search (v, M, &trovato, &q);

if (trovato)

aumenta (q, v, &M);

else

//cancella v e tutti gli //archi incidenti in v

cancella (v, &G);

}

Scopo della funzione search:

trovare un cammino aumentante rispetto a M, oppure dire che non esiste.

Parametri

v nodo esposto;

M matching;

trovato, variabile booleana;

q, vertice estremo del cammino aumentante.

Introduciamo un’etichetta per i vertici di V

= DISPARI

= NULL

Ricerca di cammini aumentanti

Ricerca di cammini aumentanti

search (v, M, *q, *trovato) { for (i ∈∈ V) ∈∈

label (i) = NULL;

LIST = {v};

label {v} = PARI;

while (LIST != ∅∅∅) {∅ pop (&i, LIST);

if (label (i) == PARI)

esplora_pari (i, M, q, trovato, &LIST);

else

esplora_dispari (i, M, &LIST);

if (trovato) return;

} }

Ricerca di cammini aumentanti (ΙΙ)

esplora_pari (i, M, *q, *trovato, *LIST) { for (j ∈∈ δ∈∈ δδδ(i)) {

if (j ∉∉ M) {∉∉

*q = j;

*trovato = TRUE;

pred (q) = i;

return;

}

if (j ∈∈ M && label (j) == NULL) {∈∈ pred (j) = i;

label (j) = DISPARI;

push (j, LIST);

} }

}

esplora_dispari (i, M, *LIST) {

j = vertice accoppiato ad i in M;

if (label (j) == NULL){

pred (j) = i;

label (j) = PARI;

push (j, LIST);

} }

Ricerca di cammini aumentanti (ΙΙΙ)

Esempio

v, PARI

DISPARI DISPARI DISPARI

PARI PARI PARI

q, ESPOSTO

Sia M il matching rosso

Esempio

v, PARI

DISPARI DISPARI DISPARI

PARI

PARI PARI

Sia M il matching rosso

Esempio

v

q

Un problema

v, P D

D

D P

P

D oppure P ?

Correttezza

Teorema: Se i vertici di G sono etichettati in modo

“unico” dalla procedura search rispetto ad un matching M, allora search termina con un cammino aumentante, se esso esiste.

Domanda: Esistono grafi che ammettono sempre

la proprietà di unicità delle etichette?

Grafi bipartiti

G (X, Y, E) grafo bipartito

Teorema di König

Teorema (König 1931): Se G = (X, Y, E) è un grafo bipartito allora µ (G) = τ(G).

Dimostrazione: Sia M* un matching massimo, e siano

• X

: insieme dei nodi x di X saturi rispetto ad M*.

• X

: insieme dei nodi x di X esposti rispetto ad M*.

Dimostrazione

X

X

Nodi raggiungibili

Definizione: Un nodo y ∈ Y

è

se esiste P alternante rispetto ad M* da x in X

tale che l’ultimo arco

Y₁

: insiemi dei nodi y di Y raggiungibili da x in X

.

Osservazione: Per definizione i nodi in Y

sono saturi, altrimenti

Infine: Y

: Y – Y

X

X

Dimostrazione

Y

Y

Y

X

X

Dimostrazione

Consideriamo il seguente insieme di nodi

Z = {z₁

, z

, …, z

} con

= y

se y

è raggiungibile

= x

altrimenti

e dimostriamo che è un trasversale.

Y

Y

Y

Dimostrazione

X

Y

Y

X

Dimostriamo che non esistono archi da nodi in X₂ verso nodi in Y non coperti da Z. Infatti,

1) Non può esistere un arco non coperto da Z tra un nodo in X₂ e un nodo in Y₂, altrimenti il matching non sarebbe massimo.

2) Non può esistere un arco non coperto da Z tra un nodo in X₂ e un nodo in Y₁ perché i nodi in Y₁ sono raggiungibili e quindi l’arco sarebbe coperto.

Y

Dimostrazione

X

Y

Y

X

Dimostriamo che non esistono archi da nodi in Y verso nodi in X₁ non coperti da Z.

Consideriamo l’arco 1, da X₁ a Y₂. Se non fosse coperto allora il nodo y₁, estremo dell’arco del matching, sarebbe raggiungibile.

Ma allora esisterebbe un cammino aumentante e il matching non sarebbe massimo.

1

y₁

Y

Dimostrazione

X

Y

Y

X

Consideriamo un arco da X

a Y

, ad esempio l’arco 2.

Se non fosse coperto allora il nodo y

non sarebbe raggiungibile, ovvero non apparterrebbe ad Y

(contraddizione).

y₂ x₁

2

Pertanto Z è un trasversale di cardinalità pari a µ(G).

Y