next up previous
Next: Soluzioni proposte

Matematica Discreta (II modulo)

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


Date: 15 luglio 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   Determinare tutte le soluzioni intere della congruenza $ x^{23}\cong 9 \quad{\rm mod}\ 31$. Si determini inoltre la minima soluzione positiva.
Soluzione

Esercizio 2   Sia $ X=I_9=\{n\in\mathbb{N}\mid n<9\}$ e sia $ Y=\{n\in I_9\mid n$    è pari$ \}$. Si calcolino le cardinalità dei seguenti insiemi:
  1. $ {\cal P}_1=\{A\in 2^X\mid Y\subseteq A \}$;
  2. $ {\cal P}_2=\{A\in 2^X\mid \left\vert Y\cap A\right\vert=2 \}$;
  3. $ {\cal P}_3=\{A\in 2^X\mid Y\cap A\ne\varnothing \}$.

Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

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

è 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.

\begin{figure}\begin{center}
\psfig{file=fig_a2_2_e4_2001.eps,width=.8\hsize} \end{center} \end{figure}


Soluzione

Domanda di teoria 1.  Dopo aver enunciato il principio di induzione nella seconda forma, si enunci e si provi il teorema di divisione euclidea tra numeri naturali.

Domanda di teoria 2.  Enunciare e provare il teorema di caratterizzazione degli alberi finiti.




next up previous
Next: Soluzioni proposte
Luminati Domenico 2002-07-19