ESERCIZI MATEMATICA DISCRETA (15/01/10) Esercizio 1.

ESERCIZI MATEMATICA DISCRETA (15/01/10)

Esercizio 1. Si consideri il grafo semplice non orientato in cui i vertici sono tutti i numeri naturali da 1 a 1000, e in cui due vertici distinti v,w sono adiacenti (cioè collegati da un arco) se la differenza fra il maggiore e il minore dei due è <3.

Quante componenti connesse ha il grafo ? Qual è il numero cromatico del grafo? Esiste nel grafo un cammino Euleriano ?

Esercizio 2. Si consideri il grafo semplice non orientato in cui i vertici sono tutte le parole di lunghezza 4 sull’alfabeto {a,b,c,d,e} e in cui due vertici distinti v,w sono adiacenti (cioè collegati da un arco) se v,w iniziano con la stessa lettera..

Quante componenti connesse ha il grafo ? Qual è il numero cromatico del grafo?

In ogni componente connessa (considerata come grafo a sé stante) esiste un cammino Euleriano ? Esercizio 3. Si consideri il grafo semplice non orientato in cui i vertici sono tutte le parole di lunghezza 5 sull’alfabeto {a,b,c} e in cui due vertici distinti v,w sono adiacenti (cioè collegati da un arco) se v,w iniziano con lettere consecutive nell’alfabeto..

Quante componenti connesse ha il grafo ? Qual è il numero cromatico del grafo?

In ogni componente connessa (considerata come grafo a sé stante) esiste un cammino Euleriano ? Esercizio 4. Si consideri il grafo semplice non orientato in cui i vertici sono tutti i numeri naturali da 1 a 99, e in cui due vertici distinti v,w sono adiacenti (cioè collegati da un arco) se la somma v+w è pari.

Quante componenti connesse ha il grafo ? Qual è il numero cromatico del grafo?

In ogni componente connessa (considerata come grafo a sé stante) esiste un cammino Euleriano ? Esercizio 5. Si consideri il grafo semplice non orientato in cui i vertici sono tutti i numeri naturali da 2 a 100, e in cui due vertici distinti v,w sono adiacenti (cioè collegati da un arco) se il prodotto vw è pari.

Quante componenti connesse ha il grafo ? Qual è il numero cromatico del grafo?

In ogni componente connessa (considerata come grafo a sé stante) esiste un cammino Euleriano ?

ESERCIZI MATEMATICA DISCRETA (15/01/10) (Soluzioni)

Esercizio 1. Il grafo è connesso: basta notare che ogni vertice v è adiacente con il successivo v+1, dunque, comunque dati 2 vertici distinti v,w (per esempio con v<w) esiste un cammino da v a w passando per i vertici consecutivi v+1,v+2, etc….. fino ad arrivare al vertice w. Dunque il grafo ha 1 sola componente connessa.

Usando solo 2 colori non si può colorare il grafo (per esempio i vertici 1,2,3 necessitano di 3 colori diversi perché sono reciprocamente adiacenti). 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.

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, per il teorema di Eulero, che nel grafo esiste un cammino Euleriano non ciclico (che inizia e finisce nei vertici 2 e 999).

Esercizio 2. Due vertici distinti v,w sono collegati da un cammino se se solo se hanno la stessa lettera iniziale, quindi esistono 5 componenti connesse, una per ogni lettera dell’alfabeto (la prima componente contiene i vertici che cominciano con la lettera a, etc…..).

Ogni componente contiene 5

vertici (basta applicare il principio delle scelte multiple) e ha tutti i vertici reciprocamente adiacenti fra loro, quindi essi devono essere colorati con colori tutti diversi:

il numero cromatico di ogni componente (e dell’intero grafo) è dunque 125.

In ogni componente ogni vertice è adiacente a tutti gli altri, quindi ha grado 124 (pari): per il teorema di Eulero in ogni componente esiste un cammino Euleriano ciclico.

Esercizio 3. Tutti i vertici che cominciano con la lettera a sono adiacenti a tutti quelli che cominciano con la lettera b, che a loro volta sono adiacenti tutti quelli che cominciano con la lettera c. Il grafo è allora connesso: dati infatti comunque 2 vertici distinti v,w, esiste un cammino da v a w (se v,w cominciano con la stessa lettera, esiste un cammino di lunghezza 2 passando per un vertice z che comincia con una lettera consecutiva nell’alfabeto; se v,w cominciano con lettere diverse, esiste un cammino da v a w di lunghezza 1 se le lettere sono consecutive, o di lunghezza 2 se sono non consecutive). In conclusione il grafo ha 1 sola componente connessa.

Bastano 2 colori per colorare il grafo (1 colore per tutti i vertici che cominciano con la lettera a oppure c, ed un secondo colore per tutti i vertici che cominciano con la lettera b): il numero cromatico del grafo è dunque 2.

I vertici che cominciano con la lettera b hanno grado 3

+3

(pari), ma i vertici che cominciano con la lettera a oppure c hanno grado 3

(dispari): poiché esistono più di 2 vertici di grado dispari, per il Teorema di Eulero non esiste nel grafo (unica componente connessa) un cammino Euleriano.

Esercizio 4. Due vertici distinti v,w sono adiacenti se e solo se sono entrambi pari o entrambi dispari perciò due vertici distinti v,w sono collegati da un cammino se e solo 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): per il Teorema di Eulero esiste in essa un cammino Euleriano ciclico. Nella seconda componente ogni vertice ha grado 49 (dispari): per il Teorema di Eulero non esiste in essa un cammino Euleriano.

Esercizio 5. 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 v,w esiste

sempre un cammino da v a w, passando per esempio per un vertice pari z). Esiste quindi nel grafo

una sola componente connessa. I 50 vertici pari richiedono 50 colori diversi, ma si può usare un

ulteriore diverso colore per colorare tutti i vertici dispari: il numero cromatico del grafo è dunque

51. Ogni vertice pari ha grado 98 (pari) ed ogni vertice dispari ha grado 50 (pari), dunque per il

Teorema di Eulero esiste nel grafo (unica componente connessa) un cammino Euleriano ciclico.