Matematica Discreta (II modulo)

Quarto appello, a.a. 1999/2000

18 settembre 2000

Esercizio 1   Dire se il seguente sistema di congruenze

$$\left\{ \begin{array}{ll} x \cong 4 &\quad{\rm mod}\ 168 \\ x \cong 25 &\quad{\rm mod}\ 119 \end{array} \right.$$

ammette soluzione ed in tal caso determinarle tutte.
Soluzione

Esercizio 2   Sia $x_n$ la successione definita dell'equazione ricorsiva lineare

$$x_{n+2}=x_{n+1}+2x_n$$

con dati iniziali $x_0=1$ e $x_1=1$.

1. Si provi che $x_{n}+x_{n+1} = 2^{n+1}$ per ogni $n \in \mathbb{N}$.
2. Si provi che $x_{n} \ge 2^{n-1}$ per ogni $n \ge 2$.
3. Si determini una espressione esplicita di $x_n$.

Soluzione

Esercizio 3   Sia $X$ un insieme finito e $A,B\subseteq X$. Si determini, in funzione delle cardinalità di $X$,$A$ e $B$, la cardinalità dell'insieme ${\cal S} =\big\{\sigma\in S_{X} \bigm \vert \sigma(A)\subseteq B\big\}$.
Soluzione

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

Dire, motivando la risposta,

1. se un tale $G$ può essere connesso;
2. se un tale $G$ può avere dei cicli.

Soluzione

Esercizio 5   Sia $G$ un grafo finito, connesso e tale che $\deg(v)=2$ per ogni vertice $v$. Si provi che $G\oldcong C_n$ essendo $n=\left\vert V(G)\right\vert$.
Soluzione

Esercizio 6   Dire quali tra i seguenti grafi sono isomorfi e quali no:

1. $G_1$ definito da $V(G_1)=\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}8\mathbb{Z}}} {{}_{\... ... {{}_{\!\scriptstyle {}8\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}8\mathbb{Z}}}$, $E(G_1)=\big\{\{n,m\}\bigm\vert n-m=3 \hbox{\rm { in }}\mathbb{Z}\big/\mathchoi... ...\!\scriptstyle {}8\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}8\mathbb{Z}}}\big\}$.
2. $G_2$ definito da $V(G_2)=\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}8\mathbb{Z}}} {{}_{\... ... {{}_{\!\scriptstyle {}8\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}8\mathbb{Z}}}$, $E(G_2)=\big\{\{n,m\}\bigm\vert n-m=2 \hbox{\rm { in }}\mathbb{Z}\big/\mathchoi... ...\!\scriptstyle {}8\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}8\mathbb{Z}}}\big\}$.
3. $G_3$ definito da $V(G_3)=(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_... ...{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$, $E(G_3)=\big\{\{n,m\}\bigm\vert n=2m \hbox{\rm { in }}\mathbb{Z}\big/\mathchoic... ...\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}}\big\}$.

Soluzione