Matematica Discreta Lezione del 17 marzo 2010

(1)

Matematica Discreta Lezione del 17 marzo 2010

Abbiamo tradotto un problema di “strette di mano” nel seguente problema di teoria dei grafi:

dato un qualunque grafo semplice orientato G con n vertici, in cui n6, dimostrare che esiste almeno un ciclo di lunghezza 3 in G o nel grafo duale G’.

Prima di dimostrare tale affermazione, notiamo che se un grafo non orientato G ha n vertici, e se un vertice v in G ha grado k allora lo stesso vertice v nel grafo duale G’ ha grado n-1-k: infatti se v è adiacente ad un numero k di vertici nel grafo G (questi k vertici sono scelti fra gli (n-1) vertici diversi da v), allora v nel grafo duale G’ è adiacente ai restanti vertici diversi da v, che sono appunto in numero di n-1-k.

Dimostriamo ora l’affermazione precedente: dato un qualunque grafo semplice orientato G con n vertici, in cui n6, dimostrare che esiste almeno un ciclo di lunghezza 3 in G o nel grafo duale G’.

Dimostrazione:

Fissiamo a piacere un vertice v in G. Distinguiamo 2 casi (e in ambedue i casi dimostriamo la tesi):

I° caso: il grado k di v è 3; in questo caso vi sono almeno 3 vertici v

1

,v

2

,v

3

adiacenti a v nel grafo G

v v

1

v

2

(grafo G) v

3

In questo caso, se almeno due dei tre vertici v

1

,v

2

,v

3

sono adiacenti fra loro, in G esiste un ciclo di lunghezza 3 (con terzo vertice v) e si ha la tesi; se invece nessuno dei tre vertici v

1

,v

2

,v

3

è adiacente ad uno degli altri, allora v

1

,v

2

,v

3

sono tutti adiacenti fra loro nel grafo duale G’ quindi essi formano un ciclo di lunghezza 3 in G’, e di nuovo si ha la tesi;

II° caso: il grado k di v è <3 (quindi k=0,1,2); in questo caso il grado di v nel grafo duale G’, come osservato sopra, è n-1-k e poiché n6 tale grado è 6-1-k=5-k3 , dunque v nel grafo duale G’ ha grado 3; in questo caso vi sono almeno 3 vertici v

1

,v

2

,v

3

adiacenti a v nel grafo duale G’

v v

1

v

2

(grafo G’) v

3

e si può allora effettuare lo stesso ragionamento fatto primo caso (scambiando nel ragionamento i ruoli del grafo G e del grafo G’) per concludere che esiste un ciclo di lunghezza 3 nel grafo G’

oppure nel grafo G, ed ottenere di nuovo la tesi.

--- Esaminiamo un altro problema della categoria “handshaking problems”.

Il gruppo delle persone che si scambiano strette di mano è in questo caso formato da n coppie

marito-moglie (in tutto 2n persone), e si suppone (ovviamente) che nessuna delle persone stringa la

mano all’altra persona con cui forma coppia. Supponiamo anche che uno dei mariti chieda a tutte le

(2)

altre persone del gruppo (compresa sua moglie) quante strette di mano ha dato e ottenga tutte risposte differenti. Quante strette di mano hanno dato il marito in questione e sua moglie ?

Sembra un problema con informazioni insufficienti per avere una risposta univoca: in effetti invece dimostreremo che esiste una soluzione univoca ed è la seguente:

il marito e la moglie hanno entrambi dato (n-1) strette di mano.

Traduciamo di nuovo il problema in un problema di teoria dei grafi, costruendo un grafo semplice non orientato G in cui i vertici sono le 2n persone, e in cui 2 vertici distinti x,y sono adiacenti (quindi collegati da un arco) se x,y si sono stretti la mano.

Supponiamo che i vertici siano raggruppati “a coppie” (ciò corrisponde alla situazione “marito- moglie”): a

1

,b

1

; a

2

,b

2

; a

3

,b

3

;……; a

n

,b

n

(ogni a

i

,b

i

è una coppia di vertici). Le ipotesi del problema corrispondono alle seguenti ipotesi sul grafo: i vertici di una stessa coppia non sono adiacenti fra loro; tutti i vertici diversi da a

1

(supponendo che il vertice a

1

corrisponda al marito “interrogante”) hanno gradi tutti differenti. La tesi è: il grado di a

1

e il grado di b

1

sono entrambi uguali ad (n-1).

Dimostrazione: ragioniamo per induzione sulla variabile n. Per n=1 la tesi è banalmente vera:

siamo in presenza di una sola coppia di vertici a

1

,b

1

che non sono per ipotesi adiacenti fra loro, quindi entrambi hanno grado 0 ossia grado n-1, come vuole la tesi.

Supponiamo l’affermazione vera quando il un numero di coppie di vertici é n=k e dimostriamola vera per n=k+1. Abbiamo quindi un grafo G con k+1 coppie di vertici.

a

1

,b

1

; a

2

,b

2

; a

3

,b

3

;……; a

k

,b

k

; a

k+1

,b

k+1

che soddisfa le ipotesi: i vertici di una stessa coppia non sono adiacenti fra loro; tutti i vertici diversi da a

1

hanno in G gradi differenti.

La tesi è: il grado di a

1

e il grado di b

1

in G sono entrambi = (k+1)-1 cioè =k.

Ogni vertice v ha come minimo grado 0 e come massimo grado 2(k+1)-2=2k : infatti in totale i vertici sono 2(k+1) ma un vertice non è adiacente né a sé stesso (non vi sono cappi in un grafo non orientato) né all’altro vertice della coppia. Dunque i valori possibili dei gradi dei vertici sono i numeri 0,1,2,……,2k (sono in tutto 2k+1 valori possibili).

Per ipotesi tutti i vertici diversi da a

1

(che sono proprio in numero di 2(k+1)-1=2k+1) hanno gradi tutti differenti: dunque i valori dei gradi di questi vertici diversi da a

1

esauriscono tutti i valori possibili 0,1,2,……,2k. Dunque in particolare fra i vertici diversi da a

1

vi sarà un vertice w che ha grado 0 (il grado minimo possibile) e un vertice z che ha grado 2k (il grado massimo possibile).

Il vertice z è adiacente a 2k vertici, quindi è adiacente a tutti i vertici tranne 2, che devono essere necessariamente z stesso e l’altro vertice della coppia di cui z fa parte; poiché w è l’unico vertice di grado 0 (quindi l’unico vertice che non adiacente a nessun altro) concludiamo che w è l’altro vertice della coppia di cui z fra parte: z,w formano una delle coppie a

i

,b

i

.

Ovviamente (poiché z,w sono fra i vertici diversi da a

1

) tale coppia non è la coppia a

1

,b

1

. Quindi z,w formano una delle coppie a

2

,b

2

; a

3

,b

3

;……; a

k

,b

k

; a

k+1

,b

k+1

. Possiamo supporre (riordinando eventualmente le coppie) che z,w formino l’ultima coppia a

k+1

,b

k+1

.

Costruiamo allora un nuovo grafo non orientato G

1

ottenuto dal grafo G eliminando i vertici z,w (cioé la coppia a

k+1

,b

k+1

) ed eliminando anche tutti gli archi che li hanno come estremi (in pratica si eliminano solo gli archi che hanno z come estremo perché w ha grado 0).

Il nuovo grafo G

1

è dunque formato dalle k coppie di vertici:

a

1

,b

1

; a

2

,b

2

; a

3

,b

3

;……; a

k

,b

k

Poiché z era adiacente nel grafo G a tutti gli altri vertici (tranne che al vertice w con cui formava coppia) il grado di ogni vertice in G

1

è diminuito di una unità rispetto al grado dello stesso vertice in G. Dunque anche in questo nuovo grafo G

1

tutti i vertici diversi da a

1

hanno gradi differenti.

Possiamo allora applicare al grafo G

1

l’ipotesi che l’affermazione è vera per n=k: il grado di a

1

e il grado di b

1

in G

1

sono entrambi = k-1. Nel grafo G si avrà allora (aumentando di una unità il grado dei vertici) che il grado di a

1

e il grado di b

1

in G

1

sono entrambi = k (come vuole la tesi).

Esaminiamo ora un altro famoso problema risolubile con la teoria dei grafi:

(3)

2) Il problema del postino cinese (studiato dal matematico cinese Kwan nel 1962). Sia dato un quartiere con edifici collegati da strade. La situazione può essere rappresentata da un grafo non orientato in cui gli incroci sono gli edifici e le strade che le collegano sono gli archi.

Supponiamo anche che, comunque scelti 2 edifici, esista sempre almeno un cammino che li collega:

il grafo corrispondente è dunque connesso.

Un postino, partendo dall’ufficio postale (che è uno degli edifici), vuole distribuire la posta a tutte le abitazioni del quartiere, e, per essere certo di ciò, vuole percorrere tutte le strade del quartiere (una strada può anche essere percorsa più di una volta) e tornare alla fine all’edificio di partenza, ma percorrendo il minimo numero di strade possibile.

In termini di teoria dei grafi, si vuole trovare (in un grafo non orientato connesso) un cammino ciclico di lunghezza minima che percorra tutti gli archi del grafo (eventualmente percorrendo qualche arco più di una volta): notare che non si pretende che il cammino sia Euleriano, ossia che percorra tutti gli archi del grafo ognuno una sola volta (sappiamo, per il teorema di Eulero, che un tale cammino non sempre esiste).

Prima di esporre l’algoritmo di Kwan che risolve il problema, dimostriamo un interessante risultato formale, dal quale segue che in un cammino come quello richiesto non è necessario ripercorrere le stesse strade un numero “eccessivo” di volte.

Infatti Kwan dimostrò che in un cammino ciclico di lunghezza minima (fra quelli che percorrono tutti gli archi di un grafo non orientato connesso) nessun arco viene percorso più di 2 volte.

Dimostriamo tale affermazione.

Per assurdo sia dato un cammino ciclico di lunghezza minima (fra quelli che percorrono tutti gli archi del grafo) e che percorra l’arco di estremi u,v almeno 3 volte.

Supponiamo per esempio che l’arco di estremi u,v sia percorso durante il cammino 3 volte tutte nella stessa direzione da u verso v.

Dunque, schematizzando tale cammino ciclico, si ha:

si percorre l’arco da u verso v; si percorre un settore A (formato da diversi archi) che parte da v ed arriva ad u; si percorre per la seconda volta l’arco da u verso v; si percorre un altro settore B che parte da v ed arriva ad u; si percorre per la terza volta l’arco da u verso v; si percorre infine un altro settore C che parte da v ed arriva ad u, chiudendo il cammino ciclico.

Gli archi dei 3 settori A,B,C, e l’arco di estremi u,v esauriscono per ipotesi tutti gli archi del grafo.

Ora costruiamo il seguente cammino ciclico:

si percorre l’arco da u verso v; si percorre il settore A (del cammino precedente) che parte da v ed arriva ad u; si percorre il settore B (del cammino precedente, ma in senso inverso) che parte da u ed arriva a v; si percorre il settore C (del cammino precedente) che parte da v ed arriva ad u, chiudendo il ciclo.

Il cammino così costruito contiene esattamente gli stessi archi del precedente, ma con la doppia cancellazione dell’arco di estremi u,v: dunque (come il precedente) è certamente un cammino ciclico che percorre tutti gli archi del grafo, ma ha lunghezza inferiore di 2 unità, e ciò è una contraddizione, perché avevamo supposto che il cammino originario ciclico fosse di lunghezza minima (fra quelli che percorrono tutti gli archi del grafo).

Per completare la dimostrazione si dovrebbero esaminare gli altri casi: quello per esempio in cui l’arco di estremi u,v sia percorso durante il cammino 2 volte nella stessa direzione da u verso v ed 1 volta nella direzione contraria da v verso u (etc……). Ma in ognuno di tali casi si ragiona in modo simile, “incollando” opportunamente i 3 settori A,B,C del cammino per ottenere un cammino di lunghezza minore di quella minima (contraddizione).