Matematica Discreta Lezione del giorno 6 marzo 2012

(1)

Matematica Discreta

Lezione del giorno 6 marzo 2012

Un altro problema a cui si applica la teoria del matching perfetto in un grafo bipartito è il problema degli impiegati: in un’azienda vi sono n impiegati ed n diversi lavori da svolgere (in genere ognuno degli impiegati è in grado di svolgere solo alcuni dei lavori); è sempre possibile accoppiare gli n impiegati con gli n lavori da svolgere (impiegati diversi con lavori diversi), in modo che ogni impiegato svolga uno dei lavori che è in grado di svolgere ?

Anche in questo caso è possibile interpretare tale problema nella teoria dei grafi, costruendo un grafo non orientato in cui i vertici sono gli elementi di AB (dove A è l’insieme degli impiegati, B è l’insieme dei lavori da svolgere), e in cui sono adiacenti solo vertici di A con vertici di B, con la regola che un impiegato di A è collegato con un arco ai lavori di B che egli è in grado di svolgere.

Si ottiene così un grafo bipartito (con partizione appunto realizzata dai sottoinsiemi A,B) e la possibilità di accoppiare gli impiegati con i lavori da svolgere equivale all’esistenza in tale grafo di un matching perfetto.

E’ quindi interessante risolvere il problema seguente: quando in un grafo non orientato bipartito (con partizione realizzata dai sottoinsiemi A,B di eguale cardinalità n) esiste un matching perfetto ? Supponiamo che il matching perfetto sia stato costruito: se consideriamo un qualunque sottoinsieme non vuoto A

1

di A e costruiamo il sottoinsieme L(A

1

) di B contenente tutti i vertici che sono adiacenti ad almeno un vertice di A

1

, è ovvio che la cardinalità di A

1

deve essere necessariamente

≤ della cardinalità di L(A

1

) (infatti se per assurdo fosse A

1

>L(A

1

), non avremmo abbastanza vertici in B da “accoppiare” con i vertici di A

1

nel matching perfetto).

In pratica (interpretando tale condizione nel problema dei matrimoni) se vi fosse un certo numero di donne superiore al numero di uomini da esse scelti come possibili mariti, non sarebbe possibile realizzare i matrimoni rispettando le scelte delle donne, perché gli uomini scelti da questo gruppo di donne sarebbero “troppo pochi”.

Questo ragionamento porta dunque al seguente risultato:

se nel grafo non orientato bipartito (con partizione realizzata dai sottoinsiemi A,B di eguale cardinalità n) esiste un matching perfetto, allora per ogni sottoinsieme non vuoto A

1

di A, se consideriamo il sottoinsieme L(A

1

) di B contenente tutti i vertici che sono adiacenti ad almeno un vertice di A

1

, si ha sempre A

1

≤L(A

1

)

.

La cosa più interessante è che vale anche il viceversa, come afferma il seguente Teorema, di cui omettiamo la dimostrazione:

Teorema di Hall. Dato un grafo non orientato bipartito (con partizione realizzata dai sottoinsiemi A,B di eguale cardinalità n), si ha:

esiste nel grafo un matching perfetto  per ogni sottoinsieme non vuoto A

1

di A, se consideriamo il sottoinsieme L(A

1

) di B contenente tutti i vertici che sono adiacenti ad almeno un vertice di A

1

, si ha sempre A

1

≤L(A

1

).

La condizione enunciata dopo il simbolo  è detta anche condizione di Hall.

Esempio. Nel seguente esempio della lezione precedente di grafo non orientato bipartito, si è

dimostrato, con un certo ragionamento, che non esiste un matching perfetto:

(2)

a d e b f g c h

Come previsto dal Teorema di Hall, in tale grafo la condizione di Hall non è vera: considerato per esempio il sottoinsieme A

1

={a,b,c} di A, se costruiamo il sottoinsieme L(A

1

) di B contenente tutti i vertici che sono adiacenti ad almeno un vertice di A

1

, si ha L(A

1

)={e,f} dunque 3=A

1

>L(A

1

)=2.

Ovviamente la condizione di Hall per l’esistenza di un matching perfetto in un grafo bipartito non è semplice da verificare: si devono considerare tutti i sottoinsiemi non vuoti A

1

di A (che sono in numero di 2

ⁿ

-1 se n=A) e per ognuno di essi costruire il corrispondente sottoinsieme L(A

1

) di B e verificare che sia sempreA

1

≤L(A

1

).

Esempio. Abbiamo esaminato nella lezione precedente un esempio di grafo non orientato bipartito in cui esiste un matching perfetto:

a d e b f g c h

Come previsto dal Teorema di Hall, in tale grafo la condizione di Hall non è vera, anche se non semplice da verificare: come detto sopra, si devono considerare tutti i sottoinsiemi non vuoti A

1

di A (che sono in numero di 2

⁴

-1=15 essendo 4=A) e per ognuno di essi costruire il corrispondente sottoinsieme L(A

1

) di B e verificare che sia sempreA

1

≤L(A

1

).

Per esempio se A

1

={a,c} si ha L(A

1

)={d,e,f} da cui A

1

=2<3=L(A

1

), e così via per le altre 14 verifiche.

Anche se abbiamo omesso la dimostrazione dell’implicazione  del Teorema di Hall, è interessante accennare un algoritmo con cui, supponendo vera la condizione di Hall, si costruisce nel grafo bipartito un matching perfetto.

Tale algoritmo costruisce un matching perfetto in modo induttivo: se sono stati già “accoppiati” k vertici a

1

,a

2

,…..,a

k

di A con k vertici adiacenti b

1

,b

2

,……,b

k

di B, e se a

k+1

A, b

k+1

B sono vertici non ancora “accoppiati”, si trova un modo (riordinando opportunamente i vertici) per ottenere un

“accoppiamento” fra i k+1 vertici a

1

,a

2

,…..,a

k

,a

k+1

di A e i k+1 vertici b

1

,b

2

,…..,b

k

,b

k+1

di A.

(3)

In questo modo (aggiungendo sempre nuovi vertici non ancora “accoppiati”) alla fine si perviene ad un matching perfetto che coinvolge tutti i vertici del grafo bipartito.

Facciamo un esempio: consideriamo il seguente grafo bipartito con partizione A={a

1

,a

2

,a

3

,a

4

,a

5

,a

6

}, B={b

1

,b

2

,b

3

,b

4

,b

5

,b

6

}

a

1

b

1

a

2

b

2

a

3

b

3

a

4

b

4

a

5

b

5

a

6

b

6

La condizione di Hall è vera (anche in questo caso è un pò lungo verificarla…..), quindi esiste nel grafo un matching perfetto.

E’ già visibile nel grafo un “accoppiamento” fra i 5 vertici a

1

,a

2

,a

3

,a

4

,a

5

di A e i 5 vertici b

1

,b

2

,b

3

,b

4

,b

5

di B (è un matching “parziale” che indicheremo con M)

a

1

b

1

a

2

b

2

a

3

b

3

(M) a

4

b

4

a

5

b

5

ma non si ha ancora un matching perfetto, perché restano non “accoppiati” i vertici a

6

di A e b

6

di B.

Ovviamente se questi 2 vertici fossero adiacenti avremmo subito un matching perfetto, ma non è questo il caso.

Sfrutteremo la condizione di Hall per costruire un matching perfetto (riordinando i vertici in modo opportuno).

Poniamoci un obiettivo intermedio (che si dimostrerà utile): costruire una cammino nel grafo che unisca i 2 vertici non “accoppiati” a

6

di A e b

6

di B e che sia formato alternativamente da archi che fanno parte del matching (M) e da archi che non ne fanno parte.

Se consideriamo il sottoinsieme A

1

={a

6

} di A, per la condizione di Hall si ha 1=A

1

≤L(A

1

), dunque L(A

1

) non è vuoto, ossia esiste qualche vertice in B adiacente al vertice a

6

, per esempio il vertice b

4

. Tenendo conto che b

4

è adiacente ad a

4

, abbiamo costruito un cammino:

a

6

b

4

a

4

Se consideriamo il sottoinsieme A

1

={a

6

,a

4

} di A, per la condizione di Hall si ha 2=A

1

≤L(A

1

), dunque L(A

1

) contiene almeno 2 vertici, e poiché già contiene b

4

(adiacente ad a

4

), contiene almeno un altro vertice diverso da b

4

: sarà un vertice adiacente ad almeno uno fra a

6

,a

4

, per esempio b

5

(che è adiacente ad a

4

).

Tenendo conto che b

5

è adiacente ad a

5

, abbiamo costruito un cammino (più lungo di quello

precedente):

(4)

a

6

b

4

a

4

b

5

a

5

Se consideriamo il sottoinsieme A

1

={a

6

,a

4

,a

5

} di A, per la condizione di Hall si ha 3=A

1

≤L(A

1

), dunque L(A

1

) contiene almeno 3 vertici, e poiché già contiene b

4

(adiacente ad a

4

) e b

5

(adiacente ad a

5

), contiene almeno un altro vertice diverso da b

4

e b

5

: sarà un vertice adiacente ad almeno uno fra a

6

,a

4

,a

5

per esempio b

2

(che è adiacente ad a

5

).

Tenendo conto che b

2

è adiacente ad a

2

, abbiamo costruito un cammino (ancora più lungo di quello precedente):

a

6

b

4

a

4

b

5

a

5

b

2

a

2

Se consideriamo il sottoinsieme A

1

={a

6

,a

4

,a

5

,a

2

} di A, per la condizione di Hall si ha 4=A

1

≤L(A

1

), dunque L(A

1

) contiene almeno 4 vertici, e poiché già contiene b

4

(adiacente ad a

4

), b

5

(adiacente ad a

5

) e b

2

(adiacente ad a

2

), contiene almeno un altro vertice diverso da b

4

,b

5

,b

2

: sarà un vertice adiacente ad almeno uno fra a

6

,a

4

,a

5

,a

2

per esempio b

6

(che è adiacente ad a

2

).

Abbiamo costruito un cammino (ancora più lungo di quello precedente):

a

6

b

4

a

4

b

5

a

5

b

2

a

2

b

6

In totale abbiamo raggiunto il nostro obiettivo intermedio: abbiamo costruito un cammino, che unisce i 2 vertici non “accoppiati” a

6

,b

6

, e che contiene archi che fanno parte del matching (M) (sono il secondo, il quarto e il sesto) alternati ad archi che non ne fanno parte (sono il primo, il terzo, il quinto e il settimo) : un tale cammino è detto appunto cammino alternante.

Cancelliamo ora nel matching (M) gli archi presenti in tale cammino alternante (sono quelli di estremi a

4

,b

4

, di estremi a

5

,b

5

, di estremi a

2

,b

2

), e inseriamo gli archi non facenti parte di (M) presenti nel cammino alternante (sono quelli di estremi a

6

,b

4

, di estremi a

4

,b

5

, di estremi a

5

,b

2

, di estremi a

2

,b

6

):

a

1

b

1

a

2

b

2

a

3

b

3

a

4

b

4

a

5

b

5

a

6

b

6

Riordinando otteniamo il matching perfetto cercato:

a

1

b

1

a

2

b

6

a

3

b

3

a

4

b

5

a

5

b

2

a

5

b

4

Grafi planari.

Partiamo da un problema pratico:

(5)

supponiamo di volere progettare un circuito elettronico, composto da “componenti” del circuito (transistors, resistenze etc..) collegati fra loro da “piste “ conduttrici di elettricità. Se vogliamo costruire il circuito in una basetta piana (quindi in 2 dimensioni) dobbiamo cercare di fare in modo che le “piste” che collegano fra loro i “componenti” del circuito non si intersechino fra loro, tranne che nei componenti che essi collegano (per evitare un corto circuito).

Non è detto che tale progetto sia sempre realizzabile.

Per studiare la realizzabilità o meno del progetto, lo si può tradurre formalmente in un grafo non orientato, in cui ogni componente rappresenta un vertice, e ogni pista rappresenta un arco che ha come estremi 2 componenti, cioè 2 vertici.

Esempio: Consideriamo un circuito elettronico in cui vi siano 4 componenti a,b,c,d e per ogni coppia di componenti vi sia esattamente una pista che li colleghi: la pista 1 collega a,b; la 2 collega b,c; la 3 collega b,d; la 4 collega a,d; la 5 collega c,d; la 6 collega a,c.

Una possibile rappresentazione piana del grafo corrispondente al circuito é in questo caso la seguente:

1 a b 4

6 3 2

c 5 d

Tale rappresentazione però non sarebbe utile per costruire il circuito: come si vede, in tale rappresentazione vi sono archi (l’arco 4 e l’arco 2) che nel piano si intersecano in un punto (al centro del disegno) che non é un vertice del grafo (quindi si incontrano in un punto che non è uno dei componenti, e ciò provocherebbe un corto circuito).

Si può però scegliere una diversa rappresentazione piana dello stesso grafo in cui ciò non succede, cioé in cui gli archi si intersecano solo in punti del piano che sono vertici del grafo, per esempio la seguente:

1 a b 4

6 3

2 c 5 d

La struttura del grafo (e quindi del circuito elettronico da costruire) è rimasta invariata, ma è stata scelta una più opportuna rappresentazione piana.

Diamo allora qualche definizione formale.

Dato un grafo non orientato, una sua rappresentazione piana è detta rappresentazione planare se in tale rappresentazione gli archi si intersecano solo in punti del piano che sono vertici del grafo.

Un grafo non orientato è detto grafo planare se esiste almeno una sua rappresentazione piana (fra le tante possibili) che sia una rappresentazione planare.

Dunque il grafo dell’esempio precedente é un grafo planare.

(6)