Matematica Discreta Lezione del giorno 28 febbraio 2012 Grafi bipartiti

Matematica Discreta

Lezione del giorno 28 febbraio 2012 Grafi bipartiti

Un grafo non orientato è detto grafo bipartito se è possibile costruire una partizione dell’insieme V dei vertici in 2 sottoinsiemi A, B (quindi A, B sono sottoinsiemi non vuoti di V tali che AB=V, AB=) in modo che qualunque arco del grafo abbia sempre uno degli estremi in A e l’altro in B (in pratica non esistono 2 vertici di A adiacenti fra loro, e non esistono 2 vertici di B adiacenti fra loro).

Esempio. Il seguente grafo non orientato con 8 vertici a,b,c,d,e,f,g,h è un grafo bipartito:

a d e

b f (*) g

c h

La necessaria partizione dell’insieme dei vertici che soddisfa la condizione della definizione di grafo bipartito è immediatamente visibile: A={a,b,c}, B={d,e,f,g,h}.

Esempio. Il seguente grafo non orientato con 8 vertici a,b,c,d,e,f,g,h è un grafo bipartito:

a d e

b f (**) g

c h

In questo caso la partizione dell’insieme dei vertici è meno visibile, ma esiste egualmente:

A={a,c,h,g}, B={b,d,e,f}.

Come si vede dagli esempi, non sempre è facile decidere se un grafo non orientato è bipartito, quindi è bene trovare delle condizioni equivalenti alla definizione di grafo bipartito.

Teorema. Un grafo non orientato è bipartito  il grafo ha numero cromatico 2.

Dimostrazione:

() Per ipotesi esiste una partizione dell’insieme V dei vertici in 2 sottoinsiemi A, B tali che non

esistono 2 vertici di A adiacenti fra loro, e non esistono 2 vertici di B adiacenti fra loro: basta allora

usare 2 colori per colorare i vertici (uno per i vertici di A, l’altro per quelli di B) e si ottiene la tesi.

() Per ipotesi è possibile colorare i vertici con 2 colori 1,2, in modo che vertici adiacenti abbiano colori associati diversi. Costruiamo l’insieme A dei vertici colorati con il colore 1, e l’insieme B dei vertici colorati con il colore 2: otteniamo così una partizione dell’insieme V dei vertici in 2 sottoinsiemi A, B tali che non esistono 2 vertici di A adiacenti fra loro, e non esistono 2 vertici di B adiacenti fra loro, dunque il grafo è bipartito.

Da un Teorema precedente conosciamo una condizione equivalente affinchè un grafo non orientato abbia numero cromatico 2, da cui il seguente risultato:

Teorema. Un grafo non orientato è bipartito  tutti i cammini ciclici nel grafo hanno lunghezza dispari.

Il problema è che per verificare se tutti i cammini ciclici nel grafo hanno lunghezza dispari, dovremmo esaminarli tutti, e questo potrebbe essere dal punto di vista computazionale un lavoro molto pesante.

Per fortuna esiste un algoritmo, basato sulla matrice di adiacenza del grafo, che permette di risolvere il problema in modo efficiente, come ora vedremo.

Sia M la matrice di adiacenza di un grafo non orientato. Sappiamo, da un Teorema precedente, che per ogni numero naturale n la matrice potenza M

contiene, all’incrocio fra una riga e una colonna, il numero dei cammini di lunghezza n che collegano i vertici corrispondenti alla riga e alla colonna.

Poiché nella diagonale principale (sinistra alto-destra basso) di M

le caselle si trovano all’incrocio fra riga e colonna corrispondenti ad uno stesso vertice, nelle caselle della diagonale principale è contenuto il numero dei cammini ciclici di lunghezza nel grafo.

Dunque un possibile algoritmo che risolva il problema di decidere se tutti i cammini ciclici nel grafo hanno lunghezza pari (cioè se il grafo è bipartito) potrebbe essere il seguente (tenendo conto che il minimo cammino ciclico possibile di lunghezza dispari ha lunghezza 3): si verifica se uno degli elementi della diagonale principale nella matrice M

è ≠0 (in tale caso si conclude che esiste un cammino ciclico di lunghezza dispari 3); se tutti gli elementi della diagonale principale nella matrice M

sono =0, si passa a verificare se uno degli elementi della diagonale principale nella matrice M

è ≠0 (in tale caso si conclude che esiste un cammino ciclico di lunghezza dispari 5); e così via, esaminano le successive potenze di esponente dispari M

, M

, M

,... per verificare se esiste un cammino ciclico di lunghezza dispari 3,5,7....

L’evidente difetto di tale ragionamento (come in un problema simile già esaminato in una lezione precedente) è che, se a priori non esistesse nessun cammino ciclico di lunghezza dispari, l’algoritmo illustrato non avrebbe mai termine, perché troveremmo sempre un valore 0 in tutte le caselle della diagonale principale nelle matrici M

(con n=3,5,7,..), e non sapremmo quando fermare il procedimento per concludere con certezza che appunto non esiste nessun cammino ciclico di lunghezza dispari (e il grafo è dunque bipartito).

Per risolvere tale problema può essere utile il seguente:

Teorema. Sia dato un grafo non orientato e sia r il numero di vertici del grafo. Allora si ha:

se esiste nel grafo qualche cammino ciclico di lunghezza dispari, allora esiste certamente qualche cammino ciclico di lunghezza dispari che abbia lunghezza <r.

Dimostrazione:

Ragioniamo per assurdo: supponiamo che esista qualche cammino ciclico di lunghezza dispari, ma

che non esista nessun cammino ciclico di lunghezza dispari che abbia lunghezza ≤ r . Sia allora S

l’insieme (non vuoto) delle lunghezze di tutti i possibili cammini ciclico di lunghezza dispari. Per

l’Assioma del minimo esiste in S un minimo s: tale s sarà dunque la lunghezza minima di un

cammino ciclico di lunghezza dispari. Poiché (per assurdo) non esistono cammini ciclici di lunghezza dispari di lunghezza ≤ r, sarà certamente s > r.

Se consideriamo un cammino ciclico di lunghezza s, osserviamo che il numero di vertici toccati dal cammino é uguale al numero s degli archi. Da s > r segue che il cammino tocca un numero di vertici maggiore del numero totale r dei vertici distinti del grafo: si deduce che almeno due vertici toccati dal cammino coincidono. Se i vertici toccati ordinatamente dal cammino sono v

,v

,...,v

(dopo v

si ritorna al vertice di partenza v

) e se v

,v

sono 2 fra tali vertici che coincidono fra loro,

“cancellando” il settore del cammino compreso fra v

e v

=v

si otterrebbe un cammino ciclico (dal vertice v

a sé stesso) di lunghezza <s dunque di lunghezza pari (perché s è la minima lunghezza di un cammino ciclico di lunghezza dispari); ma anche il settore “cancellato” sarebbe un cammino ciclico (dal vertice v

a sé stesso) di lunghezza <s dunque di lunghezza pari (per lo stesso motivo):

poiché s si otterrebbe come somma delle lunghezze (pari) di questi 2 cammini, s sarebbe anch’esso pari , contraddizione perché s é dispari per ipotesi.

L’algoritmo illustrato sopra (per verificare se esiste qualche cammino ciclico di lunghezza dispari) si può allora migliorare come segue: si calcolano solo le potenze della matrice di adiacenza M con esponente dispari  3, ma solo quelle con esponente ≤ r (dove r è il numero dei vertici del grafo); se in una almeno di tali matrici vi è un elemento della diagonale principale ≠0, si conclude che esiste almeno un cammino ciclico di lunghezza dispari; se invece in ognuna di tali matrici tutti gli elementi della diagonale principale sono =0, si conclude che non esiste nessun cammino ciclico di lunghezza dispari (e quindi il grafo è bipartito).

Si può anche compattare l’algoritmo precedente mediante il concetto di somma di matrici (come visto in un caso simile in una lezione precedente): se N è la matrice ottenuta sommando tutte le potenze della matrice di adiacenza M con esponente dispari  3 e ≤ r (dove r è sempre il numero di vertici del grafo), ed M é la sua matrice di adiacenza) e se nella matrice N tutti gli elementi della diagonale principale sono =0, si conclude che non esiste nessun cammino ciclico di lunghezza dispari (e quindi il grafo è bipartito).

Esempio. Se la matrice di adiacenza di un grafo non orientato è la seguente matrice 5x5 (quindi r=5 è il numero dei vertici):

M =

0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0

 

 

 

 

 

 

 

 

calcolando le potenze M

, M

con il prodotto righe per colonne e poi la somma si ottiene:

N=M

+M

=

0 22 28 0 0

22 0 0 22 12

28 0 0 28 16

0 22 28 0 0

0 12 16 0 0

 

 

 

 

 

 

 

 

Poiché in tale somma gli elementi della diagonale principale sono tutti =0, si conclude che non

esiste nessun cammino ciclico di lunghezza dispari (e quindi il grafo è bipartito).

In effetti, se v

,v

,v

,v

,v

sono i vertici corrispondenti in ordine a righe e colonne, la partizione dell’insieme dei vertici ottenuta con i sottoinsiemi A={v

,v

,v

}, B={v

,v

} è tale che non esistono 2 vertici di A adiacenti fra loro, e non esistono 2 vertici di B adiacenti fra loro.

Matching perfetto e Teorema di Hall.

Consideriamo un grafo non orientato bipartito, con la partizione dell’insieme V dei vertici nei 2 sottoinsiemi A, B tali che non esistono 2 vertici di A adiacenti, e non esistono 2 vertici di B adiacenti. Supponiamo inoltre che i 2 sottoinsiemi A,B abbiano la stessa cardinalità n.

In tale grafo chiameremo matching perfetto (ossia “accoppiamento perfetto”) un modo di ordinare i vertici di A e B:

A = {a

,a

,……,a

} B= {b

,b

,….,b

}

n modo che ogni vertice a

sia adiacente al vertice b

avente lo stesso indice:

Schema di un matching perfetto:

a

b

a

b

…. ….

…. ….

a

b

Non in tutti i grafi bipartiti (sempre con l’ipotesi che i 2 sottoinsiemi A,B abbiano la stessa cardinalità n) esiste un matching perfetto.

Esempio. Nell’esempio (**) di grafo bipartito con 8 vertici a,b,c,d,e,f,g,h (dato all’inizio della lezione):

a d e b f g c h

(con la partizione realizzata dai sottoinsiemi A={a,c,h,g}, B={b,d,e,f}), esiste un matching perfetto realizzato con il seguente ordinamento dei vertici di A e B:

A = {a,c,h,g} B = {d,e,b,f}

Lo schema del matching perfetto in questo caso è il seguente:

a

d c e h b g f

Esempio. Nel seguente esempio di grafo bipartito con 8 vertici a,b,c,d,e,f,g,h:

a d b e

(***) c f

g h

(con la partizione realizzata dai sottoinsiemi A={a,b,c,g}, B={d,e,f,h}) non esiste un matching perfetto: per assurdo, in un matching perfetto, il vertice b di A dovrebbe essere “accoppiato”

necessariamente con il vertice f di B (l’unico a cui b è adiacente); il vertice c di A dovrebbe essere

“accoppiato” necessariamente con il vertice e di B (l’unico a cui c è adiacente); ma allora il vertice a di A non potrebbe essere “accoppiato” con nessun vertice di B (perché è adiacente solo ai vertici e,f che sono già “impegnati”).

Il problema dell’esistenza di un matching perfetto in un grafo bipartito è legato ad alcuni problemi matematici, come il problema dei matrimoni: sono dati 2 insiemi A, B, dove A contiene n donne, B contiene n uomini; ogni donna di A compila una “lista” di potenziali mariti da sposare (da scegliere in B); è sempre possibile combinare n matrimoni fra le n donne di A e gli n uomini di B in modo che ogni donna sposi uno dei mariti della sua “lista” ?

Interpretando tale problema nella teoria dei grafi, possiamo costruire un grafo non orientato in cui i

vertici sono gli elementi di AB, e in cui sono adiacenti solo vertici di A con vertici di B, con la

regola che una donna di A è collegata con un arco ad ogni uomo di B che sia nella sua “lista“ di

potenziali mariti. Si ottiene così un grafo bipartito (con partizione appunto realizzata dai

sottoinsiemi A,B) e la possibilità di combinare gli n matrimoni equivale all’esistenza in tale grafo

di un matching perfetto.