27 27   27 

ESERCIZI MATEMATICA DISCRETA I (14/12/07) (Soluzioni)

1) Ogni vertice positivo è adiacente a tutti i vertici negativi e al vertice 0; ogni vertice negativo è adiacente a tutti i vertici positivi e al vertice 0; quindi il vertice 0 è adiacente a tutti gli altri vertici (positivi e negativi).Il grafo è allora connesso perché dati 2 vertici distinti x,y è sempre possibile costruire un cammino da x a y (passando per esempio per il vertice 0). Colorazione del grafo: il vertice 0 deve avere un colore individuale (perché è adiacente a tutti gli altri), ma possiamo usare un secondo colore per ogni vertice positivo, e un terzo colore (diverso dal secondo) per ogni vertice negativo, quindi il numero cromatico è 3. Ogni vertice positivo ha grado 31, ogni vertice negativo ha grado 31, il vertice 0 ha grado 60: nel grafo non esiste un cammino Euleriano ciclico, perché non è vero che tutti i vertici hanno grado pari né che 2 esattamente hanno grado dispari.

2) Ogni vertice è adiacente ai 2 che lo precedono (se essi esistono) e ai 2 che lo seguono (se essi esistono). In particolare due vertici consecutivi (3 e 4, 4 e 5, 5 e 6 etc.) sono adiacenti, quindi dati 2 vertici distinti x,y è sempre possibile costruire un cammino da x a y (passando per i vertici consecutivi che separano x e y): il grafo è allora connesso. Colorazione del grafo: i vertici 1,2,3 sono tutti adiacenti fra loro, quindi dobbiamo colorarli con 3 colori diversi a,b,c; ma questi 3 colori bastano per colorare tutti i vertici (colorando 4 con a, 5 con b, 6 con c, 7 con a, 8 con b, 9 con c etc.) quindi il numero cromatico è 3. Ogni vertice ha grado 4 tranne i vertici 1 e 100 che hanno grado 2, e i vertici 2 e 99 che hanno grado 3: poiché il grafo è connesso e tutti i vertici hanno grado pari tranne 2 vertici che hanno grado dispari, esiste nel grafo un cammino Euleriano non ciclico.

3) I sottoinsiemi di A che hanno intersezione vuota con B non sono altro che i sottoinsiemi del complementare A-B: poiché il complementare ha cardinalità 3, i suoi sottoinsiemi sono in numero di 2

. Dunque, essendo 2

il numero totale di sottoinsiemi di A, quelli che hanno intersezione non vuota con B sono in numero di 2

-2

.

4) Dobbiamo calcolare:

a) quanti sono i modi di colorare i pali senza usare il rosso

b) quanti sono i modi di colorare i pali usando il rosso esattamente per un palo c) quanti sono i modi di colorare i pali usando il rosso esattamente per 2 pali e poi sommare i risultati.

Per ognuno dei casi possiamo usare il principio delle scelte multiple.

Per il caso a) si devono colorare i 7 pali ognuno con 1 colore scelto fra 4 colori: i modi possibili sono 4

. Per il caso b) si deve scegliere la posizione del palo rosso (7 scelte possibili) e poi colorare i 6 pali rimanenti ognuno con 1 colore scelto fra 4 colori (4

scelte possibili): i modi possibili sono 64

. Per il caso c) si devono scegliere le 2 posizioni dei 2 pali rossi ( _



 



 2

7 scelte possibili) e poi

colorare i 5 pali rimanenti ognuno con 1 colore scelto fra 4 colori (4

scelte possibili): i modi possibili sono _



 



 2

7 4

. La risposta è la somma 4

+64

+ _



 





2

7 4

.