next up previous
: Soluzioni proposte

Matematica Discreta (II modulo)

Secondo appello, a.a. 2004/2005 -- compito 1


Date: 21 luglio 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   Dire se la congruenza $ x^5 \cong 2 \quad{\rm mod}\ 23$ ammette soluzioni ed in tal caso determinarle tutte.
Soluzione

Esercizio 2   Sia $ A$ un insieme finito con $ n$ elementi.
  1. Determinare $ n$ in modo tale che $ A$ abbia $ 4$ sottinsiemi di cardinalità $ 3$.
  2. Mostrare che se $ n$ è pari, il numero dei sottinsiemi di $ A$ con $ 3$ elementi è pari.
  3. Dire se esistono numeri $ n$ dispari per cui $ A$ abbia un numero pari di sottinsiemi di cardinalità $ 3$.
  4. Determinare tutti i numeri $ n$ che verificano le condizioni del punto precedente.

Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

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

è 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.
\begin{figure}\begin{center}
\psfig{file=fig_a2_1_e4_2004.eps,width=.8\hsize}
\end{center} \end{figure}

Soluzione

Domanda di teoria 1.  Si diano le definizioni di relazione d'equivalenza e di congruenza $ \quad{\rm mod}\ n$. Si provi che la congruenza $ \quad{\rm mod}\ n$ è una relazione d'equivalenza.

Domanda di teoria 2. Si dia la definizione di grafo, di grafo finito e di grado di un vertice. Si provi quindi che in ogni grafo finito la somma dei gradi dei vertici è uguale al doppio del numero dei lati.




next up previous
: Soluzioni proposte
domenico luminati 平成17年9月6日