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,
dire, motivando la risposta, se il seguente sistema di congruenze
ammette soluzioni ed in tal caso determinarle tutte:
Soluzione
Esercizio 2
Sia
![$ T$](img5.gif)
un albero con
![$ n$](img6.gif)
lati. Si determini, in funzione di
![$ n$](img6.gif)
, il
numero di grafi diversi che ammettono
![$ T$](img5.gif)
come albero di copertura.
Soluzione
Esercizio 3
Dire, motivando la risposta, quale dei vettori
è lo score di un grafo e quando ciò è possibile costruire un tale
grafo. Si dica inoltre se
- è possibile trovare un tale grafo che sia anche un albero
- è possibile trovare un tale grafo che sia sconnesso
- è possibile trovare un tale grafo che sia 2-connesso
Soluzione
Esercizio 4
Siano
![$ H$](img8.gif)
e
![$ K$](img9.gif)
i grafi definiti
![$ V(H)=V(K) = (\mathbb{Z}\big/\mathchoice
{{}_{\!\displaystyle {}15\mathbb{Z}}}
...
..._{\!\scriptstyle {}15\mathbb{Z}}}
{{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$](img10.gif)
e
- 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}}})^*$](img18.gif)
si indichi con
![$ G(n)$](img19.gif)
il grafo definito da
![$ V(G(n))=(\mathbb{Z}\big/\mathchoice
{{}_{\!\displaystyle {}15\mathbb{Z}}}
{{}_...
..._{\!\scriptstyle {}15\mathbb{Z}}}
{{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$](img20.gif)
e
- Determinare l'insieme degli
per i quali si ha che
.
- Dire, motivando la risposta, se esiste
tale
che
e
.
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: Soluzioni proposte
Domenico Luminati
2004-08-19