Next: Soluzioni proposte
Matematica Discreta (II modulo)
Secondo appello, a.a. 2001/2002
compito 2
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.
![$ (198,27)=9\mathrel{\big\vert}9 = 35-26$](img3.gif)
quindi il sistema e` risolubile.
Inoltre
![$ 9 = (1) \cdot 198 + (-7) \cdot 27$](img4.gif)
quindi
![$ 35-26= 9 \cdot 1 = (9) \cdot 1 + (198) \cdot -7$](img5.gif)
quindi
![$ x_0= 27$](img6.gif)
è una soluzione del sistema. Tutte le soluzioni sono allora
date da
Soluzione
Esercizio 3
Sia
![$ T$](img18.gif)
un albero che abbia soltanto vertici di grado
![$ 1$](img19.gif)
,
![$ 2$](img20.gif)
e
![$ 4$](img21.gif)
e con esattamente
![$ 3$](img22.gif)
vertici di grado
![$ 4$](img21.gif)
.
- Si provi che
ha esattamente
foglie (vertici di grado
).
- Si disegnino due di questi alberi che non siano isomorfi.
- 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$](img24.gif)
e
![$ G_2$](img25.gif)
i grafi definiti
![$ V(G_1)=V(G_2) = \mathbb{Z}\big/\mathchoice
{{}_{\!\displaystyle {}18\mathbb{Z}...
...{{}_{\!\scriptstyle {}18\mathbb{Z}}}
{{}_{\!\scriptscriptstyle {}18\mathbb{Z}}}$](img26.gif)
e
- Dire, motivando la risposta se i due grafi sono isomorfi oppure no.
- Determinare
in modo che il grafo
definito da
e
abbia esattamente
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.
Next: Soluzioni proposte
Domenico Luminati
2004-07-06