Matematica Discreta (II modulo)

Primo appello, a.a. 1999/2000

19 giugno 2000

Agli esercizi sono assegnati i seguenti punteggi: Esercizio 1: 5, Esercizio 2: 2+3+2, Esercizio 3: 5, Esercizio 4: 4+2, Esercizio 5: 2+2+1, Esercizio 6: 6

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

Esercizio 2   Sia $x_n$ la successione definita ricorsivamente da

$$\left\{ \begin{array}{l} x_{n+2} = 4 x_{n+1} - x_n \\ x_1 = 5 \\ x_0 = 1 \end{array} \right.$$

1. Si provi che $x_n$ è dispari per ogni $n\in\mathbb{N}$;
2. Si provi che $(x_{n+1},x_n)=1$ per ogni $n\in\mathbb{N}$;
3. Si determini una forma esplicita di $x_n$.

Soluzione

Esercizio 3   Sia $X\subseteq\{1,2,\dots,n\}$, con $\left\vert X\right\vert=k\le n$. Si determini la cardinalità dell'insieme ${\cal S}=\{\sigma\in S_n\mid \sigma(x)\in X\ \forall x\in X\}$.
Soluzione

Esercizio 4   Sia $G$ un grafo 2-connesso finito. Si provi che allora $\left\vert E\right\vert\ge \left\vert V\right\vert +k-2$ essendo $k=\max\limits_{v\in V(G)} \deg(v)$. Dire se vale il viceversa.
Soluzione

Esercizio 5   Sia $d=(2,2,2,2,3,3,3,5,6)$. Provare che esiste un grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d$ e determinarne uno. Dire se

1. è possibile determinarne uno che sia $2$-connesso.
2. è possibile determinarne uno che sia connesso.

Soluzione

Esercizio 6   Dei tre grafi rappresentati in figura, dire, motivando la risposta, quali sono tra loro isomorfi e quali no.

Soluzione