Matematica Discreta (II modulo)

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

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 20 \quad{\rm mod}\ 156 \\ x \cong 8 \quad{\rm mod}\ 108 \end{cases}$$

ammette soluzioni ed in tal caso determinarle tutte. $(156,108)=12\mathrel{\big\vert}-12 = 8-20$ quindi il sistema è risolubile. Inoltre, usando l'algoritmo di Euclide, si ottiene $12 = (-2) \cdot 156 + (3) \cdot 108$ quindi

$$8-20 = -12 = -((-2) \cdot 156 + (3) \cdot 108) = 2\cdot 156 - 3 \cdot 108$$

e pertanto $x_0= 332= 8+3\cdot 108 = 20 + 2\cdot 156$ è una soluzione del sistema.

L'insieme delle soluzioni è allora dato da $\{ 332 + k [156,108] \mid k\in\mathbb{Z}\}=\{ 332 + k 1404 \mid k\in\mathbb{Z}\}$     $\square$

Soluzione

Esercizio 2   Sia $X=\{1,2,3,4,5,6\}$ e $Y=X\cup\{0,7\}$. 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\})\right\vert$.

Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

$$d_1 = (2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 10, 11)\qquad d_2 = (1,1,1,1,1,1,2,8,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