Matematica Discreta

Matematica Discreta

Siamo ora in grado di dimostrare il teorema che caratterizza i grafi con numero cromatico 2:

Teorema. Sia dato un grafo in cui non tutti i vertici sono isolati (quindi con numero cromatico >1) . Allora:

il numero cromatico del grafo è 2  tutti i cammini ciclici nel grafo hanno lunghezza pari.

Dimostrazione:

(): Supponiamo per assurdo che esista nel grafo un cammino ciclico di lunghezza dispari, che rappresentiamo schematicamente come segue:

v

1

v

2

v

3

……… v

n

a

1

a

2

a

n

La lunghezza del cammino (numero degli archi percorsi) è per assurdo n dispari. Per ipotesi è possibile colorare i vertici del grafo usando solo 2 colori 1,2: ma se per esempio il vertice v

1

è colorato con 1, necessariamente il vertice v

2

è colorato con 2, il vertice v

3

è colorato con 1 e così via, cioè i vertici con indice pari sono colorati con il colore 2, i vertici con indice dispari con il colore 1. Essendo n dispari, il vertice finale v

n

di indice dispari dovrebbe essere colorato con il colore 1, ma v

n

è collegato tramite l’arco a

n

con il vertice v

1

, che era già stato colorato con il colore 1, contraddizione.

(): Poiché per ipotesi il numero cromatico del grafo è >1, basta dimostrare che 2 colori (indicati con 1,2) sono sufficienti per colorarlo. Per considerazioni fatte in precedenza, possiamo limitarci a colorare ogni singola componente connessa con i colori 1,2. Fissiamo dunque a piacere una componente connessa del grafo, e scegliamo a caso nella componente un vertice v “di riferimento”, colorandolo con il colore 1. Esponiamo ora una strategia che useremo per colorare tutti i vertici della componente diversi da v. Scelto nella componente un qualunque vertice w≠v, coloriamo w con la seguente regola: essendo v,w nella stessa componente, certamente esiste qualche cammino da v a w; ma non può esistere contemporaneamente un cammino da v a w di lunghezza pari e anche un cammino da v a w di lunghezza dispari (altrimenti, percorrendo di seguito i 2 cammini, otterremmo in totale un cammino ciclico di lunghezza pari+dispari=dispari, contro l’ipotesi); dunque i cammini da v a w sono tutti di lunghezza pari o tutti di lunghezza dispari; coloriamo allora w con il colore 1 se i cammini da v a w sono tutti di lunghezza pari, altrimenti coloriamo w con il colore 2, se i cammini da v a w sono tutti di lunghezza dispari. Facendo variare il vertice w (fra quelli ≠v), coloriamo in tale modo tutti i vertici della componente. Dobbiamo però verificare che due vertici w,z adiacenti (cioè collegati da un arco) non abbiano mai lo stesso colore. Se uno dei vertici w,z è il vertice di riferimento v allora è ovvio (se v è collegato con un arco ad un altro vertice w, allora esiste un cammino di lunghezza dispari 1 da v a w, quindi per la nostra strategia il vertice w ha colore 2 diverso dal colore 1 del vertice v). Supponiamo dunque che i vertici w,z (adiacenti) siano entrambi ≠v: se per assurdo w,z avessero per esempio lo stesso colore 2 (nella nostra strategia di colorazione), esisterebbe da w a v un cammino di lunghezza dispari, e da z a v un cammino di lunghezza dispari; ma allora (percorrendo di seguito questi 2 cammini e poi l’arco che unisce w e z) si otterrebbe in totale un cammino ciclico di lunghezza dispari+dispari+1=dispari , contro l’ipotesi.

Analoga contraddizione si ottiene se si suppone per assurdo che w,z abbiano lo stesso colore 1.

Grafi semplici e multipli.

Nella definizione più formale di grafo, abbiamo detto che esiste una funzione (detta funzione di adiacenza) dall’insieme A degli archi all’insieme V

2

di tutti gli insiemi contenenti 2 vertici: in pratica tale funzione associa ad ogni arco i 2 vertici estremi dell’arco.

Notiamo però che, nella nostra definizione di grafo, non è detto che la funzione di adiacenza sia iniettiva, cioè può avvenire anche che 2 archi diversi abbiano gli stessi vertici estremi (per esempio nel caso del grafo dei ponti, gli archi 1,2 hanno gli stessi estremi a,b). Se la funzione di adiacenza è iniettiva si dice che il grafo è semplice, mentre se la funzione di adiacenza non è iniettiva si dice che il grafo è multiplo (o è un multigrafo) : in un grafo semplice, comunque presi due vertici distinti, vi è al massimo 1 arco che li ha come estremi, quindi o essi non sono adiacenti (nessun arco li ha come estremi) oppure esattamente 1 arco li ha come estremi..

Grafi orientati

Nei grafi fino ad ora considerati, gli archi non hanno un “verso” di percorrenza: tali grafi sono anche detti grafi non orientati.. Daremo ora la definizione di una categoria differente di grafi, i cosiddetti grafi orientati, in cui invece gli archi che uniscono i vertici sono “orientati”, quindi hanno un verso di percorrenza.

Formalmente un grafo orientato è una struttura formata da 2 insiemi: V (detto insieme dei vertici), A (detto insieme degli archi), e da una funzione (detta di adiacenza) f: A  VxV che associa ad ogni arco aA una coppia ordinata di vertici (v,w) appartenente al prodotto cartesiano VxV.

Se l’arco aA è associato da f alla coppia di vertici (v,w)VxV, si dice che v è la coda dell’arco a, e w è la testa dell’arco a; si dice anche che l’arco a va dal vertice v al vertice w, e che v,w sono gli estremi dell’arco (si distinguono il primo estremo v e il secondo estremo w).

Notiamo che nella definizione di grafo orientato è consentito che ad un arco sia associata una coppia ordinata (v,v) di 2 vertici coincidenti, nel qual caso l’arco è un cappio, in cui coda e testa coincidono (ricordiamo che nella nostra definizione di grafo non orientato ad ogni arco è associato un insieme {v,w} di 2 vertici distinti, dunque i cappi non sono consentiti).

Una rappresentazione di un grafo orientato nel piano si ottiene rappresentando ogni vertice con un punto del piano e ogni arco con un arco orientato (freccia) che va dalla coda verso la testa dell’arco.

Per esempio, dato il grafo orientato con insieme dei vertici V={a,b,c,d}, insieme degli archi A={1,2,3,4,5,6}, funzione di adiacenza f definita da f(1)=(a,a), f(2)=(a,b), f(3)=(b,c), f(4)=(c,b), f(5)=(c,d), f(6)=(d,d), una sua possibile rappresentazione nel piano é.

1 6

a d 2 3 5

b c

4

Un cammino in un grafo orientato è una successione di n archi in cui la testa di ogni arco coincide

con la coda dell’arco successivo: in pratica la definizione è uguale a quella data per i grafi non

orientati, ma con il rispetto del verso di percorrenza degli archi. Si dice anche che il cammino va dal vertice v

1

(vertice di partenza) al vertice v

n+1

(vertice di arrivo).

La lunghezza di un cammino è sempre il numero di archi percorsi nel cammino stesso (contando più volte quelli percorsi più di 1 volta).

Nel grafo precedente un esempio di cammino di lunghezza 6 dal vertice a al vertice d è dato dalla successione di archi:

1, 2, 3, 4, 3, 5

Cammini Hamiltoniani

I cammini Hamiltoniani nei grafi (orientati o non orientati) sono un concetto speculare di quello di cammino Euleriano.

L’origine storica del concetto di cammino Hamiltoniano si fa risalire al matematico Hamilton che propose un gioco in cui, dato un dodecaedro (solido con 12 facce pentagonali) si doveva partire da uno dei vertici e percorrere alcuni spigoli toccando tutti i vertici ognuno una sola volta.

Rappresentando il dodecaedro in 2 dimensioni (nel piano), una possibile soluzione era:

Interpretando nella teoria dei grafi tale problema si arriva alla seguente definizione: dato un qualunque grafo (orientato o no) un cammino Hamiltoniano è un cammino che tocca tutti i vertici del grafo, ognuno una sola volta (notare che un cammino Hamiltoniano percorre certamente archi tutti diversi fra loro, ma non è detto che percorra tutti gli archi del grafo, quindi non è detto che sia un cammino Euleriano).

Fino ad ora i matematici non sono riusciti a trovare per i cammini Hamiltoniani l’analogo del Teorema di Eulero per i cammini Euleriani, quindi non è ancora nota una condizione necessaria e sufficiente per l’esistenza di un cammino Hamiltoniano in un grafo.

Ma si può essere certi dell’esistenza di un cammino Hamiltoniano in certe categorie particolari di grafi, per esempio nei grafi completi.

Un grafo (orientato o non orientato) è detto completo se, comunque dati 2 vertici distinti v, w, esiste sempre almeno un arco che ha v,w come estremi.

Esempio: il seguente grafo orientato con 4 vertici è completo a b

c d

Teorema. In un grafo completo esiste sempre almeno un cammino Hamiltoniano.

Dimostrazione:

Nel caso non orientato è banale: se v

1

, v

2

,…., v

n

sono i vertici distinti del grafo, per ipotesi esiste un arco a

1

che ha v

1

,v

2

come estremi, esiste un arco a

2

che ha v

2

,v

3

come estremi, etc.., esiste un arco a

n- 1

che ha v

n-1

,v

n

come estremi, e gli archi a

1

, a

2

,…., a

n-1

formano un cammino Hamiltoniano.

Nel caso orientato: scegliamo a piacere due vertici distinti v

1

, v

2

: essendo il grafo completo, esiste almeno un arco da v

1

a v

2

o un arco da v

2

a v

1

. Supponiamo per esempio che esista un arco da v

1

a v

2

v

1

v

2

Se il numero totale dei vertici è 2, abbiamo già costruito un cammino Hamiltoniano, che passa per tutti i vertici, ognuno una sola volta.

Poniamoci quindi nel caso in cui il numero dei vertici sia >2.

Illustreremo un procedimento iterativo con cui, supponendo di avere già costruito un cammino che passi per k vertici distinti, riusciamo sempre, se esiste un ulteriore vertice nel grafo, ad inserirlo nel cammino, costruendone uno più lungo. Applicando tale procedimento più volte, potremo, da un cammino che passa per 2 vertici distinti, costruirne uno che passa per 3 vertici distinti; da questo potremo costruirne uno che passa per 4 vertici distinti, finché otterremo un cammino che passa per tutti i vertici del grafo, ognuno una sola volta, ossia un cammino Hamiltoniano.

Supponiamo quindi di avere già costruito un cammino che passi per k vertici distinti:

v

1

v

2

v

3

v

k-1

v

k

………….

Sia dato un ulteriore vertice v

k+1

, distinto dai k vertici già toccati: vogliamo inserire tale vertice nel cammino, costruendo un cammino che passi per i k vertici precedenti ed anche per v

k+1

.

Confrontiamo v

k+1

con v

1

: essendo il grafo completo, esisterà un arco da v

k+1

a v

1

o un arco da v

1

a v

k+1

.

Nel caso esista un arco da v

k+1

a v

1

, possiamo inserire il vertice v

k+1

nel cammino in prima posizione, sfruttando appunto tale arco:

v

k+1

v

1

v

2

v

k-1

v

k

………….

Poniamo invece il caso che esista un arco da v

1

a v

k+1

:

v

k+1

v

1

v

2

v

3

v

k-1

v

k

…………

In questo caso confrontiamo v

k+1

con v

2

: essendo il grafo completo, esisterà un arco da v

k+1

a v

2

o un arco da v

2

a v

k+1

.

Nel caso esista un arco da v

k+1

a v

2

, possiamo inserire il vertice v

k+1

nel cammino in seconda posizione, sfruttando appunto tale arco, e cancellando l’arco da v

1

a v

2

del cammino iniziale:

v

k+1

v

1

v

2

v

3

v

k-1

v

k

………….

Poniamo invece il caso che esista un arco da v

2

a v

k+1

: v

k+1

v

1

v

2

v

3

v

k-1

v

k

………….

In questo caso confrontiamo v

k+1

con v

3

etc. etc.

Il procedimento può continuare: nel caso peggiore, se non riusciamo mai ad inserire il vertice v

k+1

nel cammino, alla fine avremo il caso di un arco da v

k

a v

k+1

, e in tale caso potremo inserire v

k+1

in ultima posizione, sfruttando appunto tale arco:

v

1

v

2

v

3

v

k-1

v

k

v

k+1

…………..