Compito di Matematica Discreta I (6 giugno 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 tutte le matrici 2x2 ad elementi nell’insieme {-2,-1,0,1,2}, e in cui due vertici distinti x,y sono collegati da un arco quando il prodotto del primo elemento della prima riga di x per il primo elemento della prima riga di y è 0.
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 3x3 ad elementi nell'insieme {0,1,2,3,4} che non soddisfano simultaneamente nessuna delle seguenti proprietà:
a) il primo elemento della prima riga è = 4;
b) gli elementi della terza riga sono tutti uguali fra loro (5 p.)
Esercizio 3. Si consideri la seguente successione di numeri interi che ha termine iniziale uguale a 2, e in cui ogni termine si ottiene dal precedente sottraendo 5:
a1=2, a2= -3, a3= -8, a4= -13,...
Dimostrare che:
a) per ogni naturale n, il termine an di posto n è uguale al numero 7-5n
b) per ogni naturale n, la somma a1+a2+....+an dei primi n termini è = (9n-5n2)/2 (5 p.)
Esercizio 4. Dato l’insieme A={a,b,c,d,e,f,g,h} e il sottoinsieme B={a,b,c,d}, é più grande il numero dei sottoinsiemi di A che contengono B o il numero dei sottoinsiemi di A che sono contenuti in B ? (ogni insieme è da considerare contenente sé stesso).
(5 p.)
Esercizio 5. Dato l’insieme A={1,2,3,4,5,6,7} e l’insieme B di tutte le matrici booleane 3x3, calcolare il numero delle funzioni f: A B tali che per ogni numero pari xA l’immagine f(x) è una matrice con 3 valori =1. (6 p.)
