Matematica Discreta (II modulo)

Terzo appello, a.a. 200/2001

17 settembre 2001

Esercizio 1   Si determinino le soluzioni della congruenza $x^7\cong 5 \quad{\rm mod} 77$.
Soluzione

Esercizio 2   Dire, motivando la risposta, se il seguente sistema di congruenze ammette soluzione ed in tal caso determinarle:

$$\left\{ \begin{array}{rcl} x & \cong & 37 \quad{\rm mod} 168 \\ x & \cong & 51 \quad{\rm mod} 770 \end{array}\right.$$

Soluzione

Esercizio 3  

1. Siano $n_1,n_2\in \mathbb{N}$, $n_1,n_2\ge 0$. Si provi che
   
   $${n_1 \choose 2} + {n_2 \choose 2} \le {n_1 + n_2 - 1 \choose 2}$$
   
   

2. Si usi il punto precedente per provare che se $G=(V,E)$ è un grafo finito tale che
   
   $$\left\vert E\right\vert > {\left\vert V\right\vert-1 \choose 2}$$
   
   
   allora $G$ è connesso.
3. Trovare un esempio di un grafo sconnesso $G=(V,E)$ tale che
   
   $$\left\vert E\right\vert = {\left\vert V\right\vert-1 \choose 2}$$
   
   

Soluzione

Esercizio 4   Dire, motivando la risposta, se esistono grafi il cui score sia $d=(1,1,1,1,2,3,3,3,5)$.

In caso di risposta affermativa, se ne determinino, se possibile, uno connesso e uno sconnesso.
Soluzione

Esercizio 5   Provare che i tre grafi in figura non sono a due a due isomorfi:

Soluzione