Compito di Matematica Discreta I (4 luglio 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 tutti i numeri naturali di 6 cifre (in base 10) con cifre scelte fra 1,2,3,4,5,6,7 e in cui due vertici distinti x,y sono collegati da un arco quando la somma della prima cifra di x e della prima cifra di y è dispari..
Quante componenti connesse ha il grafo ? (3 p.) Qual è il numero cromatico del grafo ? (3 p.)
Considerata una generica componente connessa del grafo come grafo a sé stante, esiste in essa un cammino Euleriano ? (3 p.)
Esercizio 2. Calcolare il numero delle matrici con 3 righe e 5 colonne ad elementi nell’insieme {1,2,3,4,5} in cui almeno 3 caselle consecutive della prima riga contengono tutte numeri pari. (6 p.)
Esercizio 3. Dimostrare che per ogni numero naturale n, il numero n7-n+21 è multiplo di 7. (4 p.)
Esercizio 4. Dato l’insieme A={a,b,c,d,e,f,g,h,i,l} e il sottoinsieme B={a,b,c,d,e}, calcolare il numero dei sottoinsiemi C di A tali che CB={a,b,c} (suggerimento:
ognuno di tali sottoinsiemi C si ottiene dall’unione di {a,b.c} con …….). (5 p.) Esercizio 5. Sia dato un grafo non orientato semplice e completo con 10 vertici e si fissi un vertice v. Partendo dal vertice v quanti cammini diversi di lunghezza 6 si possono costruire ? (6 p.)
