Compito di Matematica Discreta I (20 febbraio 2007) Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento Esercizio 1.

Compito di Matematica Discreta I (20 febbraio 2007)

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 tutte le parole sull’alfabeto {1,2,3,4,5} di lunghezza compresa fra 3 e 7 (inclusi), e in cui due vertici distinti x,y sono collegati da un arco se la somma della lunghezza di x e della lunghezza di y è pari.

Calcolare il numero di componenti connesse del grafo, e il numero di vertici di ogni componente. (3 p.)

Calcolare il numero cromatico del grafo (3 p.)

In ogni componente connessa (considerata come grafo a sé stante) dire se esiste un cammino Euleriano ciclico o non ciclico. (3 p.)

Esercizio 2. Si consideri l’insieme A delle matrici 3x4 (3 righe e 4 colonne) ad elementi nell’insieme {-3,-2,-1,+1,+2,+3,+4}. Calcolare il numero delle matrici in A tali che nessuno dei 3 gruppi di caselle (indicati sotto con gli asterischi) è interamente riempito con valori >0

(6 p.)

gruppo 1 gruppo 2 gruppo 3

* * *

*

*

*

* * * *

Esercizio 3. Si considerino l’insieme A={1,2,3,4,5,6,7}, e l’insieme B di tutte le funzioni da A in A. Calcolare il numero delle possibili funzioni f: A → B tali che l’immagine di ogni numero pari di A è biunivoca. (4 p.)

Esercizio 4. Calcolare il numero di combinazioni di classe 5 degli elementi {a,b,c,d,e,f,g,h} in cui compare necessariamente l’elemento c (almeno 1 volta), distinguendo il caso di combinazioni semplici e con ripetizione. (4 p.)

Esercizio 5. Dimostrare che per ogni numero naturale n, il numero 5

, rappresentato

in base 10, ha la cifra delle decine uguale a 2 e la cifra delle unità uguale a 5. (3 p.)

Esercizio 6. Calcolare il numero delle matrici booleane 4x5 (4 righe e 5 colonne) in

cui il numero di valori =1 è diverso dal numero di valori =0. (4 p.)