Matematica Discreta (II modulo)

Quarto appello, a.a. 2003/2004

Date: 13 settembre 2004

Da svolgersi in tre ore. Al candidato si richiede di svolgere almeno un esercizio di ciascuno dei due gruppi e di rispondere ad almeno una delle domande teoriche. Tutte le risposte devono essere motivate.

Non è ammessa la consultazione di libri e/o appunti.

Esercizio 1   Dire, motivando la risposta, se il sistema di congruenze

$$\begin{cases} x \cong 20 \quad{\rm mod}\ 117 \\ x \cong 11 \quad{\rm mod}\ 81 \end{cases}$$

ammette soluzioni ed in tal caso determinarle tutte. $(117,81)=9\mathrel{\mathrel{\Big\vert}}-9 = 20$ quindi i - 11 sistema e` risolubile. Inoltre $9 = (-2) \cdot 117 + (3) \cdot 81$ quindi $20 - 11= 9 = (-2) \cdot 117 + (3) \cdot 81$ quindi $x_0= 254 = 20 + 2 \cdot 117 = 11 + 3 \cdot 81$ è una soluzione del sistema. Tutte le soluzioni sono allora date da $\{ 254 + k [81,117] \mid k\in\mathbb{Z}\}=\{ 254 + k 1053 \mid k\in\mathbb{Z}\}$     $\square$

Soluzione

Esercizio 2   Siano $A$ e $B$ due insiemi finiti con $\left\vert A\right\vert=n$ e $\left\vert B\right\vert=m$ e sia $a\in A$.

1. Denotato $k=\left\vert A\cap B\right\vert$, si determini, in funzione di $n$, $m$ e $k$, la cardinalità dell'insieme $\{Y\subseteq A\cup B\mid a\in Y\}$.
2. Sia $b\in B$. Si determini la cardinalità dell'insieme $\{f\in B^A\mid f(a)=b\}$.

Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

$$d_1 = (3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 12)\qquad d_2 = (1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4, 5)$$

è lo score di un grafo e quando ciò è possibile costruire un tale grafo. Si dica inoltre se

1. è possibile trovare un tale grafo che sia anche un albero
2. è possibile trovare un tale grafo che sia sconnesso
3. è possibile trovare un tale grafo che sia 2-connesso

Soluzione

Esercizio 4   Dire, motivando la risposta, quali tra i grafi rappresentati in figura sono tra loro isomorfi e quali no.

Soluzione

Domanda di teoria 1.  Si dia la definizione di Massimo Comun Divisore di numeri interi. Si enunci e si provi il teorema di esistenza e unicità del MCD.

Domanda di teoria 2.  Si diano le definizioni di relazione d'equivalenza e di cammino in un grafo. Si provi che la relazione di congiungibilità con cammini è una relazione d'equivalenza sull'insieme dei vertici di un grafo.