Next: Soluzioni proposte
Previous: Matematica Discreta - II modulo 1999/2000
Matematica Discreta, II modulo
Seconda prova in itinere, a.a. 1999/2000
9 giugno 2000
Da svolgersi in due ore. Ai cinque esercizi sono assegnati rispettivamente i
seguenti punteggi in trentesimi:
Esercizio 1:
, Esercizio 2:
, Esercizio 3:
,
Esercizio 4:
, Esercizio 5:
.
Esercizio 1
Sia
![$G=(V,E)$](img15.gif)
un grafo finito. Si provi che se
![$\left\vert E\right\vert\ge\left\vert V\right\vert$](img16.gif)
allora il
grafo contiene dei cicli.
Si dica, motivando la risposta, se è vero il viceversa.
Soluzione
Esercizio 2
Sia
![$d=(1,1,1,2,4,4,4,5,5,7)$](img17.gif)
. Provare che esiste un grafo
![$G$](img18.gif)
tale che
![$\mathop{\rm score}\nolimits (G)=d$](img19.gif)
e determinarne uno. Dire, motivando la risposta, se
- è possibile determinarne uno connesso?
- è possibile determinarne uno che non abbia cicli?
Soluzione
Esercizio 3
Sia
![$G$](img18.gif)
il grafo definito da:
Si scriva la matrice di incidenza di
![$G$](img18.gif)
. Usando tale matrice si determini
l'insieme dei vertici che hanno distanza
![$2$](img21.gif)
dal vertice
![$6$](img13.gif)
.
Soluzione
Esercizio 4
Dire, motivando la risposta, se i due grafi rappresentati in figura sono
isomorfi
Soluzione
Esercizio 5
Si dia la definizione di grafo euleriano e si enunci il teorema di
caratterizzazione dei grafi euleriani. Si dia inoltre uno schizzo della
dimostrazione di tale teorema.
Soluzione
Next: Soluzioni proposte
Previous: Matematica Discreta - II modulo 1999/2000
Luminati Domenico
2002-05-16