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

Matematica Discreta

Lezione del giorno 8 marzo 2010

Abbiamo visto nella lezione precedente che, dato un grafo non orientato con r vertici:

x

,x

,…….,x

con matrice di adiacenza M, e 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 fra v e w, dunque se tale elemento è 0 si può concludere che esiste qualche cammino di lunghezza n fra v e w.

Abbiamo poi dimostrato che, se esiste almeno un cammino fra v e w, ne esiste certamente uno di lunghezza minore di r (numero dei vertici), dunque per verificare se esiste almeno un cammino fra v e w si può procedere con il seguente algoritmo:

si calcolano solo le potenze della matrice di adiacenza M con esponente 1,2,....,r-1 (cioé con esponente <r), 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 x al vertice y.

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 é 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 x al vertice y; se tale elemento é nullo, si conclude che non esiste nessun cammino dal vertice x al vertice y.

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 nel piano.

---

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 una pista che li colleghi. Il circuito si può tradurre in un grafo non orientato definito formalmente dall’insieme di vertici V={a,b,c,d}, dall’insieme di archi A={1,2,3,4,5,6} e dalla funzione di adiacenza f: A  V

(dove V

é l’insieme dei sottoinsiemi di cardinalità 2 di V) definita da f(1)={a,b}, f(2)={b,c}, f(3)={b,d}, f(4)={a,d}, f(5)={d,c}, f(6)={a,c}

(quindi l’arco 1 rappresenta la pista che collega i componenti 1 e 2, etc…).

Sappiamo che da tale definizione formale del grafo possono poi essere costruite diverse possibili rappresentazioni del grafo nel piano.

Una possibile rappresentazione nel piano del grafo é in questo caso la seguente:

1

a b 4

6 3 2

c d 5

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 d 5

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

Diamo allora qualche definizione formale.

Dato un grafo non orientato, una sua rappresentazione nel piano in cui gli archi si intersecano solo

in punti del piano che sono vertici del grafo é detta rappresentazione planare del grafo: dunque il

grafo dell’esempio precedente ha una rappresentazione planare (vedremo che non per tutti i grafi ne esiste una).

Un grafo planare é un grafo non orientato che ha almeno una rappresentazione planare.

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

Anche il grafo semplice non orientato associato ad una qualunque mappa geografica (in cui i vertici sono le regioni e i vertici corrispondenti a due regioni confinanti sono collegati da un arco) è un grafo planare, come si può dimostrare formalmente utilizzando ragionamenti geometrici (intuitivamente basta “rimpicciolire” ogni regione fino a ridurla ad un punto, tenendola collegata con un arco con ognuna delle regioni confinanti).

Se un grafo non orientato è planare può avere più di una rappresentazione planare.

Per esempio il grafo corrispondente al circuito visto sopra ha anche altre rappresentazioni planari, oltre quella indicata prima, per esempio la seguente:

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 nel piano del grafo K

,

è la seguente:

A B C

K

,

a b c

Questa però non è una rappresentazione planare. Ne esiste una o no ?

Dimostreremo in seguito che il grafo K

non è planare, dunque 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 nel piano 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. Tale rappresentazione non è ovviamente una rappresentazione planare.

Problema: il grafo K

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

La formula di Eulero per i grafi planari.

Per rispondere ad alcune delle domande fatte, è necessario dimostrare prima alcune proprietà dei grafi planari: la più importante è la cosiddetta formula di Eulero.

Prima di dimostrarla dobbiamo premettere alcune nozioni relative a particolari grafi non orientati, detti alberi.

Dato un grafo non orientato, chiameremo ciclo (o circuito) un qualunque cammino ciclico nel grafo, nel quale tutti gli archi percorsi sono distinti.

Esempio: Nel grafo dei ponti di Konisberg

a 6

1 2 b

5 d

3 4

c 7

il seguente cammino ciclico è un ciclo:

a 1 b 3 c 4 b 2 a

mentre il seguente cammino ciclico non è un ciclo (l’arco 1 è percorso più di una volta):

a 1 b 3 c 4 b 1 a

Con tale terminologia un cammino ciclico Euleriano in un grafo non orientato non è altro che un ciclo che percorre tutti gli archi del grafo.

Un albero è un grafo non orientato connesso e in cui non esistono cicli.

Esempio: Il grafo dei ponti non è un albero, mentre il seguente grafo non orientato è un albero:

a 1 2 b c 3 d

4 5

e f

In un albero ogni vertice di grado 1 è detto foglia.

Nell’esempio precedente le foglie sono 3: i vertici b,e,f .

Nel prossimo Teorema dimostreremo che in ogni albero esiste sempre almeno una foglia.