ESERCIZI MATEMATICA DISCRETA (23/01/09) Soluzioni
Esercizio 1. Il grafo è connesso: basta notare che ogni vertice x è adiacente con il successivo x+1, dunque, comunque dati 2 vertici distinti x,y (per esempio con x<y) esiste un cammino da x a y passando per i vertici consecutivi x+1,x+2, etc….. fino ad arrivare al vertice y.
I vertici 1 e 1000 hanno grado 2 , i vertici 2 e 999 hanno grado 3, tutti gli altri vertici hanno grado 4:
essendo il grafo connesso ed esistendo esattamente 2 vertici di grado dispari, si conclude che nel grafo esiste un cammino Euleriano non ciclico (che inizia e finisce nei vertici 2 e 999).
Usando solo 2 colori non si può colorare il grafo (per esempio i vertici 1,2,3 necessitano di 3 colori diversi). Ma è possibile colorare il grafo con 3 colori: se i colori sono per esempio a,b,c, basta colorare il vertice 1 con a, il 2 con b, il 3 con c, il 4 con a, il 5 con b, il 6 con c etc….
Dunque il numero cromatico del grafo è 3.
Esercizio 2. Due vertici distinti x,y sono adiacenti se sono entrambi pari o entrambi dispari:
esistono dunque 2 componenti connesse (una contenente i 49 vertici pari, una contenente i 50 vertici dispari). In ogni componente tutti i vertici sono adiacenti fra loro, dunque richiedono colori tutti diversi: la prima componente ha numero cromatico 49, la seconda 50, dunque il numero cromatico del grafo è 50.
Nella prima componente ogni vertice ha grado 48 (pari): esiste in essa un cammino Euleriano ciclico. Nella seconda componente ogni vertice ha grado 49 (dispari): non esiste in essa un cammino Euleriano (ciclico o non ciclico).
Esercizio 3. Ogni vertice pari è adiacente a tutti gli altri (pari o dispari), mentre 2 vertici dispari non sono adiacenti fra loro: il grafo è allora connesso (perché dati comunque 2 vertici distinti x,y esiste sempre un cammino da x a y, passando per esempio per un vertice pari z): esiste nel grafo una sola componente connessa. I 49 vertici pari richiedono 49 colori diversi, ma si può usare un 50-esimo colore per colorare tutti i vertici dispari: il numero cromatico del grafo è dunque 50 . Ogni vertice pari ha grado 98 (pari) ma ogni vertice dispari ha grado 49 (pari), dunque non esiste nel grafo un cammino Euleriano (ciclico o non ciclico).
