Matematica Discreta - Prova d'esame Giugno 2012

Esame di matematica discreta - 18 giugno 2012

Esercizio 1

Sia f: ℕxℕ -> ℤ la relazione così definita f(m,n) = m + n.

Verificare se f è una funzione o una relazione. Se f è una funzione dire se è iniettiva, suriettiva e biettiva (motivando la risposta). Se f è una relazione dire quali proprietà rispetta (motivando la risposta).

Esercizio 2

a) Si descriva l’algoritmo RSA e si enuncino i teoremi e gli algoritmi alla base del suo funzionamento.

b) Risolvere il seguente sistema di congruenze lineari, determinando l’inverso della seconda congruenza con l’algoritmo di Euclide.

• 3x ≡ 9 (mod 5)
• 71x ≡ 11 (mod 17)
• 5x ≡ 3 (mod 13)

Esercizio 3

a) Quante sono le permutazioni delle lettere C,A,S,A,D,I,L,L,U,C,A in cui non si legge né la parola “CASA”, né la parola “DI”, né la parola “LUCA”.

b) Provare che: (k + 1) (k + 1) = n (n-1) k k

Esercizio 4

a) Si dimostri che data una matrice quadrata A di ordine n. Essa è invertibile se e solo se rk(A) = n.

b) Studiare il seguente sistema lineare al variare di k ∈ ℝ.

• kx - y - kz + kt = 0
• (k + 2)y - (k + 1)z = 0
• (k + 1)x - 4y + (2 - k)z = 0
• (k + 1)y - kz - kt = 0

Esercizio 5

a) Dire se i seguenti grafi sono isomorfi.

Esercizio 6

a) Dire se il grafo G1 riportato di seguito è bipartito.

b) Dire se il grafo G1 riportato di seguito è planare.

Esercizio 7

a) L’indice cromatico del grafo G2 assume un valore compreso nel seguente intervallo a ≤ χ(G2) ≤ b. Determinare i migliori valori possibili di a e b e dire di quanti colori ho bisogno esattamente per colorare il grafo G2 (motivando la risposta). N.B. La risposta può essere data senza effettuare la colorazione del grafo.

b) Si dia la definizione di grafo connesso e si enuncino i metodi conosciuti per verificare la connessione di un grafo.

c) Si verifichi la connessione del grafo G2 utilizzando uno dei metodi conosciuti.