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: $6+4$, Esercizio 2: $3+2+3$, Esercizio 3: $3+4$, Esercizio 4: $6$, Esercizio 5: $2+2+5$.

Esercizio 1   Sia $G=(V,E)$ un grafo finito. Si provi che se $\left\vert E\right\vert\ge\left\vert V\right\vert$ 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)$. Provare che esiste un grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d$ e determinarne uno. Dire, motivando la risposta, se

1. è possibile determinarne uno connesso?
2. è possibile determinarne uno che non abbia cicli?

Soluzione

Esercizio 3   Sia $G$ il grafo definito da:

$$\begin{eqnarray*} V(G) & = & \{1,2,3,4,5,6\}\\ E(G) & = & \big\{\{i,j\}\bigm\vert \left\vert i-j\right\vert\le 2\big\} \end{eqnarray*}$$

Si scriva la matrice di incidenza di $G$. Usando tale matrice si determini l'insieme dei vertici che hanno distanza $2$ dal vertice $6$.
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