next up previous
Next: Soluzioni proposte

Matematica Discreta (II modulo)

Terzo appello, a.a. 2003/2004
compito 2


Date: 26 luglio 2004

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   Dopo aver risolto la congruenza,

$\displaystyle x^{23} \equiv 2 \quad{\rm mod}\ 51
$

dire, motivando la risposta, se il seguente sistema di congruenze ammette soluzioni ed in tal caso determinarle tutte:

\begin{displaymath}
\begin{cases}
x^{23} \equiv 2 \quad{\rm mod}\ 51 \\
x\equiv 4 \quad{\rm mod}\ 99 \\
\end{cases}\end{displaymath}


Soluzione

Esercizio 2   Sia $ T$ un albero con $ n$ lati. Si determini, in funzione di $ n$, il numero di grafi diversi che ammettono $ T$ come albero di copertura.
Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

$\displaystyle d_1 = (2, 2, 3, 3, 3, 3, 3, 4, 4, 11, 11, 11)\qquad
d_2 = (1, 1, 1, 1, 2, 2, 2, 2, 3, 3)
$

è 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   Siano $ H$ e $ K$ i grafi definiti $ V(H)=V(K) = (\mathbb{Z}\big/\mathchoice
{{}_{\!\displaystyle {}15\mathbb{Z}}}
...
..._{\!\scriptstyle {}15\mathbb{Z}}}
{{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ e
$\displaystyle E(H)$ $\displaystyle =$ $\displaystyle \{ \{i,j\} \mid i = 4 j$    o $\displaystyle j = 4 i \}$  
$\displaystyle E(K)$ $\displaystyle =$ $\displaystyle \{ \{i,j\} \mid i = 7 j$    o $\displaystyle j = 7 i \}.$  

  1. Dire, motivando la risposta se i due grafi sono isomorfi oppure no.
Per ogni $ n\in(\mathbb{Z}\big/\mathchoice
{{}_{\!\displaystyle {}15\mathbb{Z}}}
{{}_{\!\...
..._{\!\scriptstyle {}15\mathbb{Z}}}
{{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ si indichi con $ G(n)$ il grafo definito da $ V(G(n))=(\mathbb{Z}\big/\mathchoice
{{}_{\!\displaystyle {}15\mathbb{Z}}}
{{}_...
..._{\!\scriptstyle {}15\mathbb{Z}}}
{{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ e
$\displaystyle E(G(n))$ $\displaystyle =$ $\displaystyle \{ \{i,j\} \mid i = n j$    o $\displaystyle j = n i \}$  

  1. Determinare l'insieme degli $ n\in(\mathbb{Z}\big/\mathchoice
{{}_{\!\displaystyle {}15\mathbb{Z}}}
{{}_{\!\...
..._{\!\scriptstyle {}15\mathbb{Z}}}
{{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ per i quali si ha che $ G(n) \oldcong H$.
  2. Dire, motivando la risposta, se esiste $ n\in(\mathbb{Z}\big/\mathchoice
{{}_{\!\displaystyle {}15\mathbb{Z}}}
{{}_{\!\...
..._{\!\scriptstyle {}15\mathbb{Z}}}
{{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ tale che $ G(n) \not\oldcong H$ e $ G(n) \not\oldcong K$.

Soluzione

Domanda di teoria 1.  Dopo aver dato la definizione di insieme finito, si enunci il ``Lemma dei cassetti'' e lo si usi per definire la cardinalità degli insiemi finiti.

Domanda di teoria 2.  Dopo aver definito le passeggiate euleriane, si enunci e si provi il teorema di caratterizzazione dei grafi euleriani.




next up previous
Next: Soluzioni proposte
Domenico Luminati 2004-08-19