Matematica Discreta (II modulo)

Primo appello, a.a. 2001/2002
compito 2

Date: 24 giugno 2002

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.

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

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

$$\begin{cases} x \cong 28 \quad{\rm mod}\ 45 \\ x \cong 46 \quad{\rm mod}\ 18 \end{cases}$$

ammette soluzioni ed in tal caso determinarle tutte. $(45,18)=9\mathrel{\big\vert}18 = 46-28$ quindi il sistema è risolubile. Inoltre, usando l'algoritmo di Euclide, si ottiene $9 = (1) \cdot 45 + (-2) \cdot 18$ quindi

$$46-28= 18 = 2 \cdot 9= 2((1) \cdot 45 + (-2) \cdot 18 )=2\cdot 45 - 4 \cdot 18$$

pertanto $x_0= 28 + 2\cdot 45 = 46 + 4 \cdot 18 = 118$ è una soluzione del sistema. L'insieme delle soluzioni è allora dato da $\{ 118 + k [18,45] \mid k\in\mathbb{Z}\}=\{ 118 + k 90 \mid k\in\mathbb{Z}\}$.     $\square$

Soluzione

Esercizio 2   Sia $X=\{1,2,3,4\}$ e $Y=X\cup\{0,5,6\}$. Si calcolino:

1. $\left\vert\{f\in Y^X\mid f \text{ \\lq e iniettiva}\}\right\vert$
2. $\left\vert\{f\in Y^X\mid f \text{ \\lq e iniettiva e }f(1)=4\}\right\vert$
3. Data $f\in Y^X$ iniettiva, dire, motivando la risposta, quali valori può assumere $\left\vert f^{-1}(\{0,1,6\})\right\vert$.

Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

$$d_1 = (1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 10, 10)\qquad d_2 = ( 0, 1, 1,2,2,2,2,6,8)$$

è 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 elemento invertibile in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\textst... ...} {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$, quindi si enunci e si provi il piccolo teorema di Fermat.

Domanda di teoria 2.  Si dia la definizione di albero di copertura di un grafo, quindi si enunci e si provi il teorema di esistenza dell'albero di copertura per i grafi finiti