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

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

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.