Next: Soluzioni proposte
Previous: Matematica Discreta - II modulo 2000/2001
Matematica Discreta, II modulo
Seconda prova in itinere, a.a. 2000/2001
4 giugno 2001
Da svolgersi in tre ore. Si richiede che vengano svolti a scelta quattro (e non
più di qyuattro) dei cinque esercizi e che si risponda alla domanda di teoria.
Esercizio 1
Sia
![$G=(V,E)$](img3.gif)
un grafo finito. Si provi che se
![$\left\vert E\right\vert > \left\vert V\right\vert$](img4.gif)
allora
esiste un vertice
![$v\in V$](img5.gif)
tale che
![$\deg(v)\ge 3$](img6.gif)
.
Soluzione
Esercizio 2
Sia
![$G=(V,E)$](img3.gif)
un grafo finito e sia
![$v\in V$](img5.gif)
tale che
![$\deg (v) = d$](img7.gif)
. Si
supponga che
![$G-v$](img8.gif)
abbia
![$k$](img9.gif)
componenti connesse. Si provi che allora
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
aciclico.
Soluzione
Esercizio 4
Dire quali tra i seguenti tre grafi sono tra loro isomorfi e quali no.
Soluzione
Esercizio 5
Provare che il grafo
![$G_4$](img13.gif)
rappresentato qui sotto, non è isomorfo al grafo
![$G_1$](img14.gif)
dell'esercizio precedente.
Soluzione
Domanda di teoria.
Si dia la definizione di albero e si provi che un grafo finito è un albero
se e solo se è connesso e i vertici sono uno più dei lati.
Next: Soluzioni proposte
Previous: Matematica Discreta - II modulo 2000/2001
Luminati Domenico
2002-05-16