Matematica Discreta (II modulo)

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

Date: 29 giugno 2003

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   Dire, motivando la risposta, se il seguente sistema di congruenze ammette soluzioni ed in tal caso determinarle tutte.

$$\begin{cases} x \cong 26 \quad{\rm mod}\ 198 \\ x \cong 35 \quad{\rm mod}\ 27 \end{cases}$$

$(198,27)=9\mathrel{\big\vert}9 = 35-26$ quindi il sistema e` risolubile. Inoltre $9 = (1) \cdot 198 + (-7) \cdot 27$ quindi $35-26= 9 \cdot 1 = (9) \cdot 1 + (198) \cdot -7$ quindi $x_0= 27$ è una soluzione del sistema. Tutte le soluzioni sono allora date da $\{ 224 + k [224,198] \mid k\in\mathbb{Z}\}=\{ 27 + k 224 \mid k\in\mathbb{Z}\}$     $\square$

Soluzione

Esercizio 2   Siano $A = \{ x \in \mathbb{N}\mid 1 \le x \le 21$    e $(x,21) = 1 \}$ e $B = \{ x \in \mathbb{N}\mid 1 \le x \le 10 \}$.

1. Calcolare la cardinalità degli insiemi $\mathcal{F}_1 = \{ f \in B^A \mid f$    è iniettiva$\}$ e $\mathcal{F}_2 = \{ f \in A^B \mid f$    è iniettiva$\}$;
2. Sia $C =\{2,5\}$. Determinare la cardinalità dell'insieme $\mathcal{F}_3 = \{ f \in A^A \mid f$    è una permutazione e $f(C)=C\}$.
3. Determinare la cardinalità dell'insieme $\mathcal{F}_4=\{{\{1,2\}}^B\mid f$    è suriettiva$\}$.

Soluzione

Esercizio 3   Sia $T$ un albero che abbia soltanto vertici di grado $1$, $2$ e $4$ e con esattamente $3$ vertici di grado $4$.

1. Si provi che $T$ ha esattamente $8$ foglie (vertici di grado $1$).
2. Si disegnino due di questi alberi che non siano isomorfi.
3. Si dica, motivando la risposta se l'insieme di tali alberi a meno di isomorfismo è finito, ed in tal caso determinarne la cardinalità.

Soluzione

Esercizio 4   Siano $G_1$ e $G_2$ i grafi definiti $V(G_1)=V(G_2) = \mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}18\mathbb{Z}... ...{{}_{\!\scriptstyle {}18\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}18\mathbb{Z}}}$ e

$$E(G_1) = \{ \{i,j\} \mid i - j = \pm 7 \}$$

$$E(G_2) = \{ \{i,j\} \mid i - j = \pm 8 \}.$$

1. Dire, motivando la risposta se i due grafi sono isomorfi oppure no.
2. Determinare $k\in\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}18\mathbb{Z}}} {{}_{\!\t... ...{{}_{\!\scriptstyle {}18\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}18\mathbb{Z}}}$ in modo che il grafo $G_3$ definito da $V(G_3)=\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}18\mathbb{Z}}} {{}_{\... ...{{}_{\!\scriptstyle {}18\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}18\mathbb{Z}}}$ e
   

   $$E(G_3) = \{ \{i,j\} \mid i - j = \pm k \}$$

   
   
   abbia esattamente $3$ componenti connesse.

Soluzione

Domanda di teoria 1.  Dopo aver enunciato il principio di induzione nella seconda forma, si enunci e si provi il teorema di rappresentazione dei numeri naturali rispetto ad una base fissata.

Domanda di teoria 2.  Dopo aver definito l'albero di copertura di un grafo, si enunci e si provi il teorema di esistenza dell'albero di copertura per i grafi finiti.