Matematica Discreta
Lezione del giorno 11 febbraio 2011
Dalla teoria delle componenti connesse di un grafo, segue che, per calcolare il numero cromatico di un grafo, possiamo operare nel modo seguente: nella colorazione dei vertici del grafo possiamo colorare i vertici di ogni componente connessa, potendo riutilizzare gli stessi colori nelle diverse componenti (perché vertici in componenti diverse non sono mai adiacenti). Da tale ragionamento segue allora che il numero cromatico del grafo sarà il più grande dei numeri cromatici delle singole componenti connesse (la componente connessa che “pretende” più colori ha la prevalenza).
Esempio. Nel seguente grafo con 3 componenti connesse esaminato in un esempio precedente:
1 2 3
a b c d e f 4 5 6 7
g h i
si verifica facilmente che i numeri cromatici delle 4 componenti connesse sono rispettivamente 2, 2, 3, dunque il numero cromatico dell’intero grafo è 3 (il più grande dei tre numeri cromatici)..
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. 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 linearmente come segue:
v1 v2 v3 ……… vn
a1 a2
an
La lunghezza del cammino (numero degli archi percorsi) è per assurdo n dispari. 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 è 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 colorati con il colore 2, i vertici con indice dispari con il colore 1. Essendo n dispari, il vertice finale vn di indice dispari dovrebbe essere colorato con il colore 1, ma vn è collegato tramite l’arco an con il vertice v1, che era già stato colorato con il colore 1, contraddizione.
(): Poiché per ipotesi il numero cromatico è >1, per dimostrare che il numero cromatico è 2 basta dimostrare che sono sufficienti 2 colori per colorare il grafo. 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. 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 ha 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 V2 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 esiste 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 (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 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 (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
Teorema. In un grafo completo esiste sempre almeno un cammino Hamiltoniano.
Dimostrazione:
Nel caso non orientato è banale: se v1, v2,…., vn sono i vertici distinti del grafo, per ipotesi esiste un arco a1 che ha v1,v2 come estremi, esiste un arco a2 che ha v2,v3 come estremi, etc.., esiste un arco an- 1 che ha vn-1,vn come estremi, egli archi a1, a2,…., an-1 formano un cammino Hamiltoniano.
Nel caso orientato: scegliamo a piacere due vertici distinti v1, v2 : essendo il grafo completo, esiste almeno un arco da v1 a v2 o un arco da v2 a v1. Supponiamo per esempio che esista un arco da v1 a v2
v1 v2
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:
v1 v2 v3 ………….vk-1 vk
Sia dato un ulteriore vertice vk+1, distinto dai k vertici già toccati: vogliamo inserire tale vertice nel cammino.
Confrontiamo vk+1 con v1 : essendo il grafo completo, esisterà un arco da vk+1 a v1 o un arco da v1 a vk+1.
Nel caso esista un arco da vk+1 a v1, possiamo inserire il vertice vk+1 nel cammino in prima posizione, sfruttando appunto tale arco:
vk+1 v1 v2 ………….vk-1 vk
Poniamo invece il caso che esista un arco da v1 avk+1:
vk+1
v1 v2 v3 ………….vk-1 vk
In questo caso confrontiamo vk+1 con v2 : essendo il grafo completo, esisterà un arco da vk+1 a v2 o un arco da v2 avk+1.
Nel caso esista un arco da vk+1 a v2, possiamo inserire il vertice vk+1 nel cammino in seconda posizione, sfruttando appunto tale arco, e cancellando l’arco da v1 a v2 del cammino iniziale:
vk+1
v1 v2 v3 ………….vk-1 vk
Poniamo invece il caso che esista un arco da v2 avk+1 : vk+1
v1 v2 v3 ………….vk-1 vk
In questo caso confrontiamo vk+1 con v3 etc. etc.
Il procedimento può continuare: se non riusciamo mai ad inserire il vertice vk+1 nel cammino, alla fine avremo il caso di un arco da vk a vk+1 , e in tale caso potremo inserire vk+1 in ultima posizione, sfruttando appunto tale arco:
v1 v2 v3 ………….vk-1 vk vk+1
Esempio: Sia dato il seguente grafo orientato completo con 5 vertici:
v1
v2 v5
v4
v3
Costruiamo un cammino Hamiltoniano, seguendo il metodo iterativo indicato nella dimostrazione del teorema.
Partiamo da 2 vertici e da un arco che li ha come estremi, per esempio:
v1 v2
Procediamo allungando il cammino con l’inserimento di un nuovo vertice, per esempio v3: confrontiamo v3 con v1, e poiché esiste un arco da v3 verso v1, inseriamo v3 al primo posto nel cammino:
v3 v1 v2
Inseriamo ora per esempio il vertice v4: confrontando v4 con v3, si vede che non esiste un arco da v4
verso v3 ma un arco da v3 verso v4, quindi confrontiamo v4 con v1, e poiché esiste un arco da v4
verso v1, inseriamo v4 nel cammino fra v3 e v1 (elidendo l’arco da v3 verso v1):
v4
v3 v1 v2
Inseriamo ora l’ultimo vertice v5: confrontando v5 con v3, v4, v1, si vede che non esistono archi da v5
verso v3, v4, v1, ma esiste un arco da v1 verso v5, quindi confrontiamo v5 con v2, e poiché esiste un arco da v5 verso v2, inseriamo v5 nel cammino fra v1 ed v2 (elidendo l’arco da v1 verso v2), ottenendo infine il cammino Hamiltoniano cercato:
v4 v5
v3 v1 v2
