Matematica Discreta - Esercizi

Esame di matematica discreta - 12 luglio 2012 - (Prof. Sterle Claudio)

Esercizio 1

a) Si considerino le seguenti funzioni:

f: ℝⁿ -> ℝ    f(x) = x⁴

g: ℝⁿ -> ℝ    g(x) = x⁴

h: ℝ -> ℝ²⁰     h(x) = x⁴

l: ℝ²⁰ -> ℝ²⁰     l(x) = x⁴

Dire, motivando le risposte, per ogni funzione se è iniettiva (utilizzando la definizione di funz. iniettiva), suriettiva, biiettiva e invertibile.

Esercizio 2

Si fornisca la rappresentazione tabellare e la rappresentazione su grafo delle seguenti relazioni:

• Relazione non riflessiva, simmetrica.
• Relazione riflessiva, non simmetrica, non asimmetrica.

Esercizio 3

a) Si risolva la seguente congruenza con il metodo dell'esponenziazione modulare: 2²²³ mod 225.

b) Trovare il MCD di (220, 121) ed esprimerlo come combinazione lineare dei due numeri.

Esercizio 4

a) In quanti modi si possono colorare 7 caselle allineate disponendo 3 colori se si chiede di usare un solo colore per casella e in modo che ognuno di essi venga utilizzato almeno una volta?

b) In quanti modi si possono colorare 10 caselle allineate disponendo di 4 colori se si chiede di usare un solo colore per casella e che caselle consecutive abbiano colori diversi?

Esercizio 5

a) Data una matrice A(6x8), trovare il numero di minori di ordine 2 in essa contenuti.

b) Data una matrice A(6x8), trovare il numero di minori di ordine 3 orlati del minore di ordine due contenuto nelle prime due righe e nelle prime due colonne della matrice.

c) Calcolare il rango della seguente matrice utilizzando o il metodo degli orlati o il metodo di Gauss.

A = 3   1   -2   4
2   3   -1
5   2   1   3
0   3   -2   3
7   -1   0   1

Esercizio 6

a) Dire se i seguenti grafi G1 e G2 (senza considerare i pesi sugli archi) sono isomorfi e, nel caso lo siano, costruire la corrispondenza tra di essi.

G1                                             G2

Esercizio 7

a) Si enuncino gli algoritmi noti per la determinazione dell'albero minimo, evidenziandone le differenze fondamentali.

b) Si determini l'albero minimo per il grafo G2.

c) È possibile avere un circuito o un percorso euleriano sul grafo G2? Se sì, si spieghi il perché.

d) È possibile avere un circuito hamiltoniano sul grafo G2? Se sì, si spieghi il perché.