Matematica Discreta (II modulo)

Primo appello, a.a. 2000/2001

13 giugno 2001

Da svolgersi in tre ore. Al candidato si richiede di svolgere cinque (e non più di cinque) dei sei esercizi. A chi deve recuperare una delle prove in itinere, si richiede di svolgere tutti gli esercizi della corrispondente parte e di rispondere alla domanda di teoria.

Esercizio 1   Dire se il sistema di congruenze

$$\left\{ \begin{array}{ll} x \cong 71 &\quad{\rm mod} 148 \\ x \cong 67 &\quad{\rm mod} 180 \end{array} \right.$$

ammette soluzioni ed in tal caso determinarle.
Soluzione

Esercizio 2   Si determinino le soluzioni della congruenza $x^7\cong 8 \quad{\rm mod} 77$.
Soluzione

Esercizio 3   Sia $X=\{1,2,\dots,n\}$ con $n\ge 2$.

1. Si determini la cardinalità dell'insieme ${\cal F}=\{f\in X^X \mid \hbox{\rm {\\lq e bigettiva e }} f(1)= 2\}$.

Sia $A\subseteq X$ e sia $g:X\to X$ una funzione bigettiva.

1. Si determini la cardinalità dell'insieme ${\cal G}=\{f\in X^X \mid \hbox{\rm {\\lq e bigettiva e }} \setbox\restrictbox=\hb... ...box depth\dp\restrictbox \hbox{\vrule depth\dp0 height \ht0 width0pt}_{A}}\}$.

Soluzione

Domanda di teoria.  Si dia la definizione di elemento invertibile in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$, quindi si enunci e si provi il piccolo teorema di Fermat.

Esercizio 4   Sia $T=(V,E)$ un albero e per ogni $i$ si denoti con $V_i=\{v\in V\mid \deg(v)=i\}$.

Si provi che se $T$ ha solo verici di grado $1$ e $5$ allora $\left\vert V_1\right\vert=2+3\left\vert V_5\right\vert$.

Dire motivando la risposta se è vero il viceversa.
Soluzione

Esercizio 5   Dire, motivando la risposta, quale dei vettori

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

è 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 anche 2-connesso

Soluzione

Esercizio 6   Dire, motivando la risposta, se i due grafi rappresentati in figura sono tra loro isomorfi oppure no.

Soluzione

Domanda di teoria.  Si dia la definizione di grafo 2-connesso, quindi si provi che in un grafo 2-connesso ogni coppia di vertici è contenuta in un ciclo..