Matching

Definizione Dato un grafo non orientato G = (V,A), unmatching su tale grafo è un sottinsieme M ⊆ A dell’insiemedi archi A tale che non ci sono in esso coppie di archiadiacenti, ovvero con un nodo in comune.

– p. 1/27

Matching di peso massimo

Se associamo ad ogni arco e ∈ A un peso we > 0 possiamoassociare un peso anche a un matching M pari alla sommadei pesi degli archi in M , cioè:

w(M) =∑

e∈M

we.

Nel problema di matching pesato si vuole determinare tratutti i possibili matching in un grafo quello di peso massimo,cioè si vuole risolvere il seguente problema:

maxM⊆A è un matching

w(M).

– p. 2/27

Applicazioni

Questo problema modella tutte le applicazioni in cuiabbiamo membri di un insieme (rappresentati dai nodi delgrafo) alcuni dei quali accoppiabili tra loro (i nodi collegatida archi). Ad ogni potenziale accoppiamento si associa unpeso (o profitto) e si vuole individuare quali coppie formare(tenendo conto che un membro dell’insieme può far parte almassimo di una coppia) in modo da massimizzare il peso(o profitto) totale

– p. 3/27

Esempio

Grafo non orientato G = (V,A) con:

V = {a, b, c, d, e, f},

A = {(a, b); (a, f); (b, c); (c, d); (c, e); (d, e); (e, f)}

e:

Arco (a, b) (a, f) (b, c) (c, d) (c, e) (d, e) (e, f)

Peso 4 2 3 6 2 5 1

Esempi di matching:

M1 = {(a, b); (c, e)} w(M1) = 4 + 2 = 6

M2 = {(a, b); (c, d); (e, f)} w(M2) = 4 + 6 + 1 = 11– p. 4/27

Matching di cardinalità massima

Caso particolare:we = 1 ∀ e ∈ A.

In tal caso il peso di un matching coincide con la suacardinalità | M | e si parla di problema di matching dicardinalità massima.

– p. 5/27

Modello matematico - variabili

Ad ogni arco e associamo una variabile binaria xe definitanel modo seguente:

xe =

{

0 se e non viene inserito nel matching1 altrimenti

– p. 6/27

Modello matematico-vincoli

Per garantire che le variabili xe con valore pari a 1 forminoeffettivamente un matching introduciamo dei vincoli.

Per avere un matching su ogni nodo del grafo deve incidereal massimo un arco del matching.

Indichiamo per ogni nodo i ∈ V il seguente insieme degliarchi incidenti su di esso:

δ(i) = {e ∈ A : e incide su i}.

Se vogliamo che al massimo un nodo del matching incidasu ogni nodo i del grafo, dovremo imporre i seguenti vincoli:

∑

e∈δ(i)

xe ≤ 1 ∀ i ∈ V.

– p. 7/27

Nell’esempio

Nodo a:xab + xaf ≤ 1

Nodo b:xab + xbc ≤ 1

Nodo c:xbc + xcd + xce ≤ 1

Nodo d:xcd + xde ≤ 1

Nodo e:xce + xde + xef ≤ 1

Nodo f :xaf + xef ≤ 1

– p. 8/27

Modello matematico - obiettivo

L’obiettivo del problema è il peso totale del matching che èdato dalla seguente espressione:

∑

e∈A

wexe.

Nell’esempio:

4xab + 2xaf + 3xbc + 6xcd + 2xce + 5xde + xef

– p. 9/27

Modello matematico finale

max∑

e∈A wexe∑

e∈δ(i) xe ≤ 1 ∀ i ∈ V

xe ∈ {0, 1} ∀ e ∈ A

– p. 10/27

Nell’esempio

max 4xab + 2xaf + 3xbc + 6xcd + 2xce + 5xde + xef

xab + xaf ≤ 1

xab + xbc ≤ 1

xbc + xcd + xce ≤ 1

xcd + xde ≤ 1

xce + xde + xef ≤ 1

xaf + xef ≤ 1

xab, xaf , xbc, xcd, xce, xde, xef ∈ {0, 1}

– p. 11/27

In forma matriciale

Siano:

x il vettore di ordine | A | le cui componenti sono levariabili xe, e ∈ A;

w il vettore di ordine | A | le cui componenti sono i pesiwe, e ∈ A;

C la matrice dei vincoli di ordine | V | × | A |: coincidecon la matrice di incidenza nodo-arco del grafo;

0 e 1 rispettivamente il vettore le cui componenti sonotutte pari a 0 e quello le cui componenti sono tutte paria 1;

I la matrice identica.

– p. 12/27

Modello in forma matriciale

max wx

Cx ≤ 1

Ix ≤ 1

x ≥ 0 intero

dove:

wx ↔∑

e∈A wexe;

Cx ≤ 1 ↔∑

e∈δ(i) xe ≤ 1 ∀ i ∈ V ;

Ix ≤ 1 e x ≥ 0 intero ↔ xe ∈ {0, 1} ∀ e ∈ A

– p. 13/27

Nell’esempio

Vettore pesi w:(4 2 3 6 2 5 1)

Matrice C:

xab xaf xbc xcd xce xde xef

a 1 1 0 0 0 0 0

b 1 0 1 0 0 0 0

c 0 0 1 1 1 0 0

d 0 0 0 1 0 1 0

e 0 0 0 0 1 1 1

f 0 1 0 0 0 0 1

– p. 14/27

Complessità

Il problema di matching appartiene alla classe P , ovveroesiste una procedura di complessità polinomiale che lorisolve.

Nel caso di grafi bipartiti, dove C è TU, possiamo sfruttare ilsolito risultato sulle matrici TU.

Non possiamo invece in generale dimostrare questoutilizzando i risultati visti sulle matrici TU (per grafi nonorientati generici la matrice di incidenza nodo-arco C non ènecessariamente TU).

– p. 15/27

Chiusura convessa

Per grafi generici i vincoli già introdotti non sono sufficientiper definire la chiusura convessa, occorre introdurre altrivincoli.

Dato U ⊆ V , indichiamo con E(U) l’insieme di tutti gli archidel grafo con entrambi gli estremi in U . I vincoli aggiuntivisono i seguenti:

∑

e∈E(U)

xe ≤

⌊

| U |

2

⌋

∀ U ⊆ V, | U | dispari

– p. 16/27

Nell’esempio

U = {a, b, c} → xab + xbc ≤ 1

U = {a, b, d} → xab ≤ 1

U = {a, b, e} → xab ≤ 1

U = {a, b, f} → xab + xaf ≤ 1

U = {a, c, d} → xcd ≤ 1

U = {a, c, e} → xce ≤ 1

U = {a, c, f} → 0 ≤ 1

eccetera ...

– p. 17/27

Problema (Pconv)

max∑

e∈A wexe∑

e∈δ(i) xe ≤ 1 ∀ i ∈ V

∑

e∈E(U) xe ≤⌊

|U |2

⌋

∀ U ⊆ V, | U | dispari

xe ≥ 0 ∀ e ∈ A

– p. 18/27

Nota bene

Il numero dei vincoli aggiuntivi è esponenziale rispetto alladimensione del problema di matching.

Tuttavia, il problema (Pconv) è risolvibile in tempopolinomiale in quanto, dato un generico vettorex ∈ R|A|, x ≥ 0, è possibile stabilire in tempo polinomiale sequesto soddisfa o meno i vincoli aggiuntivi.

– p. 19/27

Grafi bipartiti: cardinalità massima

In tutte le applicazioni in cui gli elementi accoppiabili tra loroappartengono a due classi distinte (ad esempio, lavoratorida una parte e lavori dall’altra), il grafo corrispondenteG = (V,A) è un grafo bipartito con le due classi dibipartizione V1 e V2.

Faremo inoltre l’ulteriore ipotesi che tutti i pesi siano ugualia 1 ovvero consideremo il problema di matching dicardinalità massima su grafi bipartiti.

– p. 20/27

Un esempio

Grafo bipartito G = (V1 ∪ V2, A) con:

V1 = {a1, a2, a3, a4}

V2 = {b1, b2, b3, b4}

A = {(a1, b1); (a2, b2); (a2, b3); (a2, b4); (a3, b2); (a4, b1)}

– p. 21/27

Un matching iniziale

Un matching di partenza (non necessariamente dicardinalità massima) può essere ottenuto con la seguentesemplice procedura:

Inizializzazione Si ponga M = ∅.

1. Se esiste un arco e ∈ A \ M che non sia adiacente adalcun arco in M , allora porre M = M ∪ {e} e ripetere ilpasso 1. Altrimenti: STOP.

– p. 22/27

Algoritmo di risoluzione

Inizializzazione Sia M un matching di partenza(eventualmente individuato con la procedura vista).

Passo 0 Tutti i vertici del grafo sono non etichettati.

Passo 1. Se non c’è alcun vertice del grafo in V1 chesoddisfa le seguenti proprietà

è non etichettato;su di esso non incide alcun arco in M ,

allora: STOP. Altrimenti si seleziona un vertice del grafoin V1 con tali proprietà e gli si assegna etichetta (E,−).Si inizializzi l’insieme R dei vertici analizzati con R = ∅.

– p. 23/27

Passo 2. Se tutti i vertici etichettati sono stati analizzati,ritornare al Passo 1; altrimenti selezionare un vertice k

etichettato ma non analizzato ed analizzarlo, cioè siponga R = R ∪ {k}. Analizzare un vertice vuol direcompiere le seguenti operazioni:

Se la prima componente dell’etichetta di k è una E,allora si assegna un’etichetta (O, k) a tutti i vertici delgrafo adiacenti a k e non ancora etichettati; quindi siripete il Passo 2.Se la prima componente dell’etichetta di k è una O,allora sono possibili due casi

Caso 1 C’è un arco marcato incidente su k: in talcaso si assegna l’etichetta (E, k) al vertice unito ak dall’arco in M e si ripete il Passo 2.;Caso 2 Non ci sono archi in M incidenti su k. In talcaso si va al Passo 3. – p. 24/27

Continua

Passo 3. Utilizzando la seconda componente delleetichette risalire dal vertice k in cui ci si è bloccati alPasso 2 fino al vertice s con seconda componente paria −. In questo modo si è individuato un cammino da s ak che inizia con un arco non appartenente a M ,prosegue alternando archi in M e archi nonappartenenti a M , e termina in k con un arco nonappartenente a M . A questo punto si aggiorna M

invertendo l’appartenenza e non appartenenza a M peri soli archi lungo tale cammino. Quindi, tutti gli archi nonappartenenti a M lungo il cammino vengono inseriti inM e viceversa. Infine si cancellano tutte le etichetteripartendo dal Passo 1.

– p. 25/27

Complessità dell’algoritmo

Si può dimostrare che questo algoritmo richiede un numerodi operazioni O(min(| V1 |, | V2 |) | A |) e ha quindicomplessità polinomiale.

Va sottolineato che non è il meglio che si possa ottenereper questo problema. Esiste infatti anche un altro algoritmo,che non vedremo, la cui complessità è pari aO(| V |1/2| A |).

– p. 26/27

Un’osservazione

Il problema di matching di cardinalità massima su grafibipartiti può essere visto come caso particolare di problemadi flusso massimo. Come?

– p. 27/27