Matematica Discreta (II modulo)

Terzo appello, a.a. 2004/2005 -- compito 2

Date: 7 settembre 2005

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. Tutte le risposte devono essere motivate.

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

Esercizio 1   Determinare tutte le soluzioni della congruenza $x^7 \cong 2 \quad{\rm mod}\ 35$ e dire se il sistema di congruenze

$$\begin{cases} x^7 \cong 2 & \quad{\rm mod}\ 35 \\ x \cong 16 & \quad{\rm mod}\ 55 \end{cases}$$

ammette soluzioni oppure no.
Soluzione

Esercizio 2   Siano $A = \mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\t... ...{{}_{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}}$ e $B = (\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\... ..._{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$. Si calcolino le cardinalità dei seguenti insiemi:

1. $\{ C \in 2^A \mid \left\vert C \cap B\right\vert = 6\}$;
2. $\{ f \in A^A \mid f(B)=B\}$;
3. $\{ f \in A^A \mid f(B)=B$    e $f$    è iniettiva$\}$.

Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

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

è lo score di un grafo e quando ciò è possibile costruire un tale grafo. Si dica inoltre se è possibile trovare un tale grafo che sia anche

1. un albero;
2. sconnesso;
3. hamiltoniano.

Soluzione

Esercizio 4   Si provi che in ogni albero con 13 vertici dei quali 10 siano di grado 1 esiste un vertice di grado maggiore o uguale a 5.
Soluzione

Domanda di teoria 1.  Dare la definizione di numero primo e provare che $p$ è primo se e solo se

$$\forall \; a,b\in\mathbb{Z}\quad p\mathrel{\big\vert}ab \Rightarrow p\mathrel{\big\vert}a$$    o $$p \mathrel{\big\vert}b.$$

Domanda di teoria 2. Si diano le definizioni di passeggiata, cammino e di grafo connesso. Si provi che in un grafo due vertici sono congiungibili con una passeggiata se e solo se sono congiungibili con un cammino.