Matematica Discreta (12 Crediti) Programma 2012 15 Maggio 2012
1. Provare che la cardinalit`a dell’insieme dei k-sottoinsiemi di un n-insieme `e nk.
2. Nell’insieme N × N si definisca, per ogni (a, b), (c, d) ∈ N × N, la relazione
(a, b) (c, d) ⇔ 3a5b 3c5d ≤ 1.
Dire se
(a) la relazione `e un ordinamento parziale su N × N;
(b) la funzione f : N × N → N, definita da f (a, b) = 3a5b, `e iniettiva.
3. (a) Sia A una matrice invertibile. Si consideri la matrice (A|I), dove I e’ la matrice identica. Si dimostri che la matrice, ottenuta trasformando (A|I) nella sua forma a scala per righe, e’ uguale a (I|A−1).
(b) Usando il metodo descritto al punto (a), si calcoli la matrice inversa della matrice
A =
1 2 −1
3 8 2
4 9 −1
4. Determinare se e’ possibile costruire un albero con 11 vertici di grado 1,
2 vertici di grado 2, 3 vertici di grado 3, 4 vertici di grado 4,
nessun vertice di grado strettamente maggiore di 4.
Se possibile, lo si costruisca nella forma G = (V, E), indicando linsieme dei vertici V e linsieme dei lati E.
1
