358473  143321 

Lezione del giorno 19 aprile 2011

Nella lezione precedente abbiamo notato che restava insoluto un problema: se fissiamo 2 vertici di un grafo v=x

, w=x

, come decidere se esiste almeno un cammino (di lunghezza opportuna non precisata) dal vertice v al vertice w ?

Se M è la matrice di adiacenza del grafo, avevamo anche osservato che una soluzione intuitiva consisteva nell’esaminare nelle matrici M

, M

, M

,…… l’elemento all’incrocio fra la riga i e la colonna j (se tale elemento è non nullo, esiste dal vertice v al vertice w un cammino di lunghezza 1, 2, 3….).

Il difetto di tale algoritmo é che, se a priori non esistesse nessun cammino dal vertice v al vertice w, esso non avrebbe mai termine.

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. Fissati nel grafo due vertici v, w si ha:

se non esistono cammini di lunghezza <r dal vertice v al vertice w, allora non esistono cammini dal vertice v al vertice w.

Dimostrazione:

Ragioniamo per assurdo: supponiamo che esista almeno un cammino dal vertice v al vertice w, e sia S l’insieme delle lunghezze di tutti i possibili cammini da v a w. Per l’Assioma del minimo esiste in S un minimo s: tale s sarà dunque la lunghezza minima di un cammino da v a w. Poiché per ipotesi non esistono cammini di lunghezza <r dal vertice v al vertice w, sarà certamente s  r.

Se consideriamo un cammino di lunghezza s da v a w, osserviamo che il numero di vertici toccati dal cammino é s+1 (perché tale numero è sempre di 1 unità superiore al numero di archi percorsi nel cammino). Ma da s  r segue s+1>r, dunque 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

,...,w=v

e se v

,v

sono 2 fra tali vertici che coincidono fra loro, “elidendo” il settore del cammino compreso fra v

e v

si otterrebbe un cammino dal vertice v al vertice w di lunghezza <s, contraddizione perché s é la lunghezza minima di un cammino dal vertice v al vertice w.

L’algoritmo precedente si può allora raffinare come segue: fissati i vertici v=x

, w=x

, si calcolano solo le potenze della matrice di adiacenza M con esponente 1,2,....,r-1 (cioé con esponente <r dove r è il numero dei vertici del grafo), e in ognuna di esse si verifica se l’elemento nella riga i e colonna j é non nullo; se in una almeno di tali matrici tale elemento é non nullo, si conclude che esiste almeno un cammino dal vertice v al vertice w (la lunghezza di tale cammino coincide con l’esponente di M); se invece in ognuna di tali matrici tale elemento é nullo, si conclude che non esiste nessun cammino dal vertice v al vertice w (perché non ne esiste nessuno di lunghezza <r).

Si può anche compattare l’algoritmo precedente mediante il concetto di somma di matrici: date due matrici M,N entrambe con n righe ed m colonne, la loro somma N+M é la matrice in cui l’elemento generico in riga i e colonna j é ottenuto dalla somma dei 2 elementi di M ed N nella stessa posizione.

Esempio: date le matrici 2x3

M= _



 





1 4 3

3 2

1 N= _



 





2 1 5

1 5 2

la loro somma é la matrice:

M+N= _



 

















2 1 1 4 5 3

1 3 5 2 2

1 = _



 





3 5 8

4

7

3

Se allora nell’algoritmo precedente consideriamo la somma delle matrici:

N=M+M

+M

+...+M

(dove r è sempre il numero di vertici distinti del grafo, ed M é la sua matrice di adiacenza) e se nella matrice N l’elemento nella riga i e colonna j é non nullo, si conclude che esiste almeno un cammino dal vertice v al vertice w; se tale elemento é nullo, si conclude che non esiste nessun cammino dal vertice v al vertice w.

Questo algoritmo può anche essere utilizzato per verificare se il grafo non orientato è connesso: la proprietà che per ogni coppia di vertici esiste almeno un cammino che li collega sarà equivalente alla proprietà che la matrice N=M+M

+M

+...+M

ha tutti gli elementi non nulli.

Esempio.

Consideriamo il grafo non orientato già visto in una delle lezioni precedenti:

1

x

x

x

2 3

4 5 6 x

7

con matrice di adiacenza (rispetto all’ordine x

,x

,x

,x

dei vertici):

M =



 









 







0 0 1 1

0 0 2 2

1 2 0 1

1 2 1 0

Si ha:

M

= MxM =



 









 







2 4 1 1

4 8 2 2

1 2 6 5

1 2 5 6

M

= M

xM =



 









 







2 4 11 11

4 8 22 22

11 22 10 11

11 22 11 10

dunque:

N = M+M

+M

=



 









 







4 8 14 14

8 16 26 26

14 26 16 17

14

26

17

16

Poiché la matrice N ha tutti gli elementi non nulli, possiamo concludere che il grafo è connesso, come d’altronde era già evidente dalla sua rappresentazione planare.

---

La matrice di adiacenza si può anche definire per un grafo non orientato, ma in tale caso si deve tenere conto che ogni arco ha un verso dal vertice di origine (“coda”) al vertice di arrivo (“testa”).

Dato un grafo orientato con r vertici ordinati come segue:

x

,x

,…….,x

definiamo matrice di adiacenza del grafo la matrice quadrata rxr in cui in ogni casella all’incrocio fra riga i e colonna j inseriamo il numero degli archi che hanno coda nel vertice v=x

e testa nel vertice w=x

(quindi archi che vanno da v verso w).

Ovviamente nel caso orientato la matrice di adiacenza non è in genere più simmetrica (se esiste un arco da v verso w non è detto che ne esista uno da w verso v). Inoltre le caselle della diagonale principale possono contenere valori non nulli, perché sono consentiti i cappi.

Esempio:

Dato il grafo orientato con 4 vertici x

, x

, x

, x

e 7 archi:

x

1 x

2 x

3 4 5

7 x

6

la sua matrice di adiacenza 4x4 (rispetto all’ordine x

, x

, x

, x

dei vertici) è la seguente:



 









 







1 0 1 0

0 1 0 0

0 2 0 1

1 0 0 0

Si dimostra facilmente che continuano a valere i risultati sull’esistenza di cammini di lunghezza n:

- in un grafo orientato con r vertici e matrice di adiacenza M, fissati 2 vertici v=x

, w=y

, per ogni numero naturale n il valore in riga i e colonna j della matrice potenza M

rappresenta il numero di cammini di lunghezza n che hanno v come vertice iniziale del cammino e w come vertice finale del cammino, dunque se tale elemento è 0 si può concludere che esiste qualche cammino di lunghezza n che ha v come vertice iniziale del cammino e w come vertice finale del cammino.

- se esiste almeno un cammino che ha v come vertice iniziale del cammino e w come vertice finale del cammino, ne esiste certamente uno che ha v come vertice iniziale del cammino e w come vertice finale del cammino di lunghezza minore di r (numero dei vertici)

- se si calcolano solo le potenze della matrice di adiacenza M con esponente 1,2,....,r-1 (cioé con

esponente <r=numero dei vertici), e in una almeno di esse si verifica che l’elemento nella riga i e

colonna j é non nullo, si può concludere che esiste almeno un cammino che ha v come vertice

iniziale del cammino e w come vertice finale del cammino, mentre in caso contrario un tale

cammino non esiste.

Grafi planari

Partiamo da un problema pratico:

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

Diamo allora qualche definizione formale.

Dato un grafo non orientato, esso è detto grafo planare se esiste almeno una sua rappresentazione planare in cui gli archi si intersecano solo in punti del piano che sono vertici del grafo.

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

Esempio: il grafo dei ponti di Konisberg é un grafo planare, avendo, come visto più volte, la seguente rappresentazione planare:

a 6 1 2

b

5 d

3 4

c 7

Se un grafo non orientato è planare può avere più di una rappresentazione planare in cui gli archi si intersecano solo in punti del piano che sono vertici del grafo.

Per esempio il grafo corrispondente al circuito visto sopra ha anche la seguente rappresentazione planare in cui gli archi si intersecano solo in punti del piano che sono vertici del grafo:

a

6 1 4 b

2 3

c 5 d

Vedremo poi esempi di grafi non orientati che non sono planari: il grafo K

,

dei 3 servizi e il grafo semplice completo K

con 5 vertici.

Il grafo K

,

dei servizi.

Problema dei 3 servizi: Siano A, B, C tre abitazioni ed a, b, c tre centrali che forniscono servizi (luce, acqua, gas), si vorrebbe collegare ognuna delle centrali con ognuna delle abitazioni mediante una linea: è possibile fare in modo che le 9 linee da costruire non si intersechino, se non nelle abitazioni stesse e nelle centrali ?

Tale problema fu posto per la prima volta negli Stati Uniti nel 1913 come gioco enigmistico dal titolo “Water, Gas and Electricity”.

Si può tradurre anche questo problema (come quello dei circuiti elettronici) in teoria dei grafi:

costruiamo un grafo non orientato in cui A,B,C,a,b,c, sono 6 vertici, e in cui ognuno dei 3 vertici A,B,C è collegato ad ognuno dei vertici a,b,c da un arco (tale tipo di grafo è spesso indicato con il simbolo K

,

e detto appunto “grafo dei servizi”).

Il progetto precedente (collegare ognuna delle centrali con ognuna delle abitazioni mediante una linea in modo che le 9 linee da costruire non si intersechino, se non nelle abitazioni stesse e nelle centrali) sarà realizzabile solo se il grafo K

è un grafo planare.

Una possibile rappresentazione planare del grafo K

,

è la seguente:

A B C

K

,

a b c

In questa rappresentazione planare però non è vero che gli archi si intersecano solo in punti del piano che sono vertici del grafo. Ne esiste una con tale proprietà ?

Dimostreremo in seguito che la risposta è negativa, quindi che il grafo K

non è planare, ed il problema dei 3 servizi non ha soluzione.

Il grafo completo K

.

Ricordiamo che un grafo è completo se, comunque presi 2 vertici distinti, esiste almeno un arco che li unisce. Consideriamo il grafo non orientato completo semplice con 5 vertici (detto anche grafo K

): dunque i 5 vertici sono a 2 a 2 reciprocamente collegati da un arco, per un totale di 10 archi.

Una possibile rappresentazione planare del grafo K

si ottiene disegnando un pentagono e tutte le sue possibili diagonali: i vertici sono i 5 vertici del pentagono, e gli archi sono i 5 lati del pentagono e le 5 diagonali. In tale rappresentazione palnare ovviamente non è vero che gli archi si intersecano solo in punti del piano che sono vertici del grafo.

Problema: il grafo K

è planare ? Dimostreremo che anche in questo caso la risposta è negativa.

---

Per rispondere ad alcune delle domande fatte sopra, è necessario dimostrare prima alcune proprietà dei grafi planari: se un grafo non soddisferà tutte le proprietà che troveremo, potremo concludere che non è un grafo planare.

Sia dato un grafo planare, e una sua qualunque rappresentazione planare in cui gli archi si intersecano solo in punti del piano che sono vertici del grafo.

Sia A l’insieme dei punti del piano che siano diversi dai vertici e non appartenenti a nessuno degli archi. Dal punto di vista geometrico la rappresentazione planare determina una partizione dell’insieme A in sottoinsiemi del piano detti facce (due punti del piano appartengono alla stessa faccia se è possibile tracciare una linea continua, anche non rettilinea, che li unisce senza attraversare gli archi e i vertici).

Notiamo anche che una delle facce è di area infinita (ed è detta appunto faccia infinita), mentre le altre sono di area finita (e sono dette appunto facce finite).

Esempio: nella solita rappresentazione planare del grafo dei ponti di Konisberg:

6 1  2 

5 

3  4  7

si distinguono 5 facce (le facce “finite” ,,, e la faccia “infinita” ).

La frontiera (o contorno) di una faccia è l’insieme degli archi i cui punti “toccano” (in senso geometrico) alcuni punti della faccia (si possono dare definizioni geometriche formalmente più precise, che ometteremo per semplicità).

Esempio: nella rappresentazione planare del grafo dei ponti di Konisberg vista sopra, il contorno

della faccia  è per esempio formato dagli archi 6,2,5; invece il contorno della faccia (infinita)  è

formato dagli archi 6,1,3,7.