Matematica Discreta
Lezione del giorno 5 dicembre 2011
Caratterizziamo ora i grafi con “basso” numero cromatico. E’ ovvio che un grafo ha numero cromatico 1 se e solo se ha solo vertici isolati (quindi se e solo se non vi sono archi nel grafo). Per il numero cromatico 2 vi è il seguente risultato:
Teorema. Il numero cromatico di un grafo è 2 tutti i cammini ciclici nel grafo hanno lunghezza pari.
Dimostrazione:
(): Supponiamo di avere un qualunque cammino ciclico di lunghezza n (quindi che percorre n archi) nel nostro grafo: la tesi è che n è pari. Rappresentiamo linearmente tale cammino come segue:
v1 v2 v3 ……… vn
a1 a2
an
Per ipotesi è possibile colorare i vertici del grafo usando solo 2 colori (indichiamo tali colori con 1,2): ma se per esempio il vertice v1 è stato colorato con 1, necessariamente il vertice v2 è colorato con 2, il vertice v3 è colorato con 1 e così via, cioè i vertici con indice pari sono stati colorati con il colore 2, i vertici con indice dispari con il colore 1. Poiché il vertice vn è adiacente al vertice v1, necessariamente vn è stato colorato con il colore 2, dunque l’indice n (che è anche la lunghezza del cammino) è pari (tesi)..
(): Per dimostrare che il numero cromatico è 2 basta dimostrare che sono sufficienti 2 colori per colorare il grafo: siano 1,2 tali colori. Considerando le componenti connesse del grafo, basta dimostrare che sono sufficienti 2 colori per colorare ciascuna di esse. Supponiamo quindi di dovere colorare i vertici di una componente connessa. Scegliamo a caso nella componente un vertice v “di riferimento” e coloriamolo con il colore 1. Ora indichiamo una “strategia” per colorare tutti i vertici
≠v della componente. Consideriamo nella componente un qualunque vertice w≠v: 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; usiamo allora la seguente strategia per colorare w:
coloriamo w con il colore 1 se tutti i cammini da v a w sono di lunghezza pari, altrimenti coloriamo w con il colore 2, se tutti i cammini da v a w sono di lunghezza dispari. Facendo variare il vertice w (fra quelli ≠v nella componente), coloriamo in tal modo tutti i vertici della componente (utilizzando solo i colori 1,2). Dobbiamo però verificare che due vertici w,z adiacenti (cioè collegati da un arco) non abbiano mai lo stesso colore. Supponiamo dunque per assurdo che i vertici w,z adiacenti siano stati colorati con lo stesso colore 2 (nella nostra strategia di colorazione): in tale caso (vista la strategia usata) 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 ha se si suppone per assurdo che w,z abbiano lo stesso colore 1.
Grafi semplici e multipli.
Un grafo è detto semplice, se, 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 esiste un solo arco che 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 (sono come delle strade “a senso unico”).
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 aA una coppia ordinata di vertici (v,w) appartenente al prodotto cartesiano VxV.
Se l’arco aA è 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): in tale caso rappresenteremo spesso l’arco aA con il simbolo vw
.
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 della forma:
a1=v1v2 , a2=v2v3 , a3=v3v4 ,……., an=vnvn1
(quindi 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 v1 (vertice di partenza) al vertice vn+1 (vertice di arrivo).
Il numero n di archi percorsi nel cammino è detto lunghezza del cammino.
Nel grafo precedente un esempio di cammino di lunghezza 6 dal vertice a al vertice d è la seguente 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 il seguente cammino tracciato in rosso:
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 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 (dunque, nel caso orientato, se esiste almeno un arco dal vertice v al vertice w oppure un arco dal vertice w al vertice v).
Esempio: il seguente grafo orientato con 4 vertici è un grafo completo a b
c d
Nella prossima lezione dimostreremo il seguente:
Teorema. In un grafo completo esiste sempre qualche cammino Hamiltoniano.
