Compito di Matematica Discreta I (5 settembre 2008)
Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento
Esercizio 1. Si consideri il grafo semplice non orientato in cui i vertici sono le parole di lunghezza 6 sull’alfabeto {a,b,c,d} e in cui due vertici distinti x,y sono collegati da un arco quando la prima lettera della parola x e la prima lettera della parola y sono lettere consecutive nell’alfabeto italiano.
Il grafo è connesso ? (in caso di risposta negativa calcolare il numero di componenti connesse) (3 p.)
Qual è il numero cromatico del grafo ? (3 p.) Nel grafo esiste un cammino Euleriano ? (3 p.)
Esercizio 2. Calcolare il numero delle matrici quadrate 5x5 ad elementi nell’insieme {1,2,3,4,5,6,7,8} in cui nessuna delle 2 diagonali contiene esclusivamente numeri maggiori di 5. (5 p.)
Esercizio 3. Dimostrare che per ogni numero naturale n, il numero delle parole sull’alfabeto {0,1} di lunghezza n è 2n+1-2 . (5 p.)
Esercizio 4. Dato l’insieme A={a,b,c,d,e,f,g,h,i,o}, calcolare il numero dei sottoinsiemi C di A che hanno cardinalità 6 e che contengono esattamente 2 vocali (suggerimento: ognuno di tali sottoinsiemi C si ottiene dall’unione di un insieme di 2 vocali con …….). (6 p.)
Esercizio 5. Calcolare il numero di combinazioni con ripetizione degli elementi {1,2,3,4,5,6,7} presi a 20 a 20, che contengono il numero 2 ripetuto esattamente 5 volte e non contengono il numero 5. (5 p.)
