Matematica Discreta (II modulo)

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

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\equiv 20 \quad{\rm mod}\ 117 \\ x\equiv 11 \quad{\rm mod}\ 81 \\ \end{cases}$$

Soluzione

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

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 =\{5,7\}$. 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\}}^A\mid f$    è suriettiva$\}$.

Soluzione

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

1. Si provi che $T$ ha esattamente $7$ 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 {}12\mathbb{Z}... ...{{}_{\!\scriptstyle {}12\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}12\mathbb{Z}}}$ e

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

$$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 {}12\mathbb{Z}}} {{}_{\!\t... ...{{}_{\!\scriptstyle {}12\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}12\mathbb{Z}}}$ in modo che il grafo $G_3$ definito da $V(G_3)=\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}12\mathbb{Z}}} {{}_{\... ...{{}_{\!\scriptstyle {}12\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}12\mathbb{Z}}}$ e
   

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

   
   
   abbia esattamente $2$ 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.