Next: Soluzioni proposte
Matematica Discreta (II modulo)
Terzo appello, a.a. 2001/2002
Date: 19 settembre 2002
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.
Non è ammessa la consultazione di libri e/o appunti.
Esercizio 1
Dire, motivando la risposta, se il sistema di congruenze
ammette soluzioni ed in tal caso determinarle tutte.
![$ (603,144)=9\mathrel{\big\vert}18 = 27-9$](img14.gif)
quindi il sistema e` risolubile.
Inoltre
![$ 9 = (-5) \cdot 603 + (21) \cdot 144$](img15.gif)
quindi
![$ 27-9= 18 = 9 \cdot 2 = 603 \cdot (-10) + 144 \cdot 42$](img16.gif)
quindi
![$ x_0=-6021 = 27 -42 \cdot 144 = 9 -10\cdot 603 $](img17.gif)
è una soluzione del
sistema. Tutte le soluzioni sono allora date da
Soluzione
Esercizio 2
Su uno scaffale ci sono
![$ 7$](img20.gif)
libri,
![$ 3$](img21.gif)
sono libri di matematica e
![$ 4$](img22.gif)
sono libri
di scienze. In quanti modi si possono disporre i libri sullo scaffale perché
tutti i libri di matematica stiano assieme? [Charles M. Schulz]
Sapresti fornire, motivandola, una formula per lo soluzione dello stesso
problema nel caso generale di
libri di matematica e
libri di scienze?
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 2-connesso
- è possibile trovare un tale grafo che sia sconnesso
Soluzione
Esercizio 4
Sia
![$ G$](img26.gif)
un grafo aciclico con 10 vertici e
![$ 7$](img27.gif)
lati. Provare che è possibile
aggiungere a
![$ G$](img28.gif)
un lato in modo che il grafo rimanga aciclico.
Qual è il massimo numero di lati che si possono aggiungere a
in modo che
rimanga aciclico?
Soluzione
Domanda di teoria 1.
Si dia la definizione di rappresentabilità di un numero naturale rispetto ad
una base fissata. Quindi si enunci e si provi il teorema di
rappresentabilità dei numeri naturali rispetto ad una base fissata.
Domanda di teoria 2.
Scrivere e provare la formula che in un grafo finito lega i gradi dei vertici al
numero dei lati. Se ne enunci quindi qualche conseguenza
Next: Soluzioni proposte
Luminati Domenico
2002-09-19