Matematica Discreta (II modulo)

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

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^{17} \cong 3 \quad{\rm mod}\ 29$ 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 $10$ 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

$$d_1 = (2, 2, 3, 3, 4, 4, 7, 7)\qquad d_2 = (1, 1, 1, 1, 3, 3, 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.

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.