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)$ un grafo finito. Si provi che se $\left\vert E\right\vert > \left\vert V\right\vert$ allora esiste un vertice $v\in V$ tale che $\deg(v)\ge 3$.
Soluzione

Esercizio 2   Sia $G=(V,E)$ un grafo finito e sia $v\in V$ tale che $\deg (v) = d$. Si supponga che $G-v$ abbia $k$ componenti connesse. Si provi che allora

$$\left\vert E\right\vert + k \ge \left\vert V\right\vert + d -1$$

Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

$$\begin{eqnarray*} d_1 & = & (1,1,2,2,2,3,3,3,5,6,8,11) \\ d_2 & = & (1,1,2,2,2,2,3,3,3,3,4) \end{eqnarray*}$$

è 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$ rappresentato qui sotto, non è isomorfo al grafo $G_1$ 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.