Matematica Discreta (II modulo)

Terzo appello, a.a. 2003/2004
compito 1

Date: 26 luglio 2004

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. Tutte le risposte devono essere motivate.

Non è ammessa la consultazione di libri e/o appunti.

Esercizio 1   Dopo aver risolto la congruenza,

$$x^{33} \equiv 2 \quad{\rm mod}\ 55$$

dire, motivando la risposta, se il seguente sistema di congruenze ammette soluzioni ed in tal caso determinarle tutte:

$$\begin{cases} x^{33} \equiv 2 \quad{\rm mod}\ 55 \\ x\equiv 3 \quad{\rm mod}\ 115 \end{cases}$$

Soluzione

Esercizio 2   Sia $T$ un albero con $n$ vertici. Si determini, in funzione di $n$, il numero di grafi diversi che ammettono $T$ come albero di copertura.
Soluzione

Esercizio 3   Dire, motivando la risposta, quale dei vettori

$$d_1 = (3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 12)\qquad d_2 = (1, 2, 3, 4, 5, 6, 7, 8, 8)$$

è lo score di un grafo e quando ciò è possibile costruire un tale grafo. Si dica inoltre se

1. è possibile trovare un tale grafo che sia anche un albero
2. è possibile trovare un tale grafo che sia sconnesso
3. è possibile trovare un tale grafo che non sia 2-connesso

Soluzione

Esercizio 4   Siano $H$ e $K$ i grafi definiti $V(H)=V(K) = (\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} ... ..._{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ e

$$E(H) = \{ \{i,j\} \mid i = 2 j j = 2 i \}$$

$$E(K) = \{ \{i,j\} \mid i = 11 j j = 11 i \}.$$

1. Dire, motivando la risposta se i due grafi sono isomorfi oppure no.

Per ogni $n\in(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\... ..._{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ si indichi con $G(n)$ il grafo definito da $V(G(n))=(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_... ..._{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ e

$$E(G(n)) = \{ \{i,j\} \mid i = n j j = n i \}$$

1. Determinare l'insieme degli $n\in(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\... ..._{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ per i quali si ha che $G(n) \oldcong H$.
2. Dire, motivando la risposta, se esiste $n\in(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\... ..._{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ tale che $G(n) \not\oldcong H$ e $G(n) \not\oldcong K$.

Soluzione

Domanda di teoria 1.  Dopo aver dato la definizione di insieme finito, si enunci il ``Lemma dei cassetti'' e lo si usi per definire la cardinalità degli insiemi finiti.

Domanda di teoria 2.  Dopo aver definito le passeggiate euleriane, si enunci e si provi il teorema di caratterizzazione dei grafi euleriani.