Matematica Discreta (II modulo)

Secondo appello, a.a. 1999/2000

10 luglio 2000

Esercizio 1   Si supponga di avere un mazzo con 15 carte e si eseguano le seguenti operazioni:

1. Si dispongano le carte in una matrice $3\times 5$ procedendo per colonne (da sinistra a destra e dall'alto in basso)
2. si raccolgano le carte procedendo per righe (dall'alto in basso e da sinistra a destra)

Dire, motivando la risposta, se dopo un numero finito (positivo) di tali operazioni il mazzo torna nella posizione iniziale. In caso di risposta affermativa, calcolare il minimo tale numero.
Soluzione

Esercizio 2   Si determini l'insieme delle soluzioni del sistema di congruenze:

$$\left\{ \begin{array}{ll} x \cong 396 &\quad{\rm mod}\ 385 \\ x \cong 32 &\quad{\rm mod}\ 504 \end{array} \right.$$

Soluzione

Esercizio 3   Sia $x_n$ la soluzione dell'equazione ricorsiva lineare

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

con dati iniziali $x_0=2$ e $x_1=2$. Si provi che

1. Si provi che $x_n\le 3^n$ per ogni $n\ge 1$.
2. Si determini $(x_{n+1},x_n)$ per ogni $n$.
3. Si determini una forma esplicita della soluzione dell'equazione.

Soluzione

Esercizio 4   Siano $d_1=(1,1,1,2,2,4,4,4,6.8)$ e $d_2=(1,1,1,1,2,2,3,5)$. Dire, motivando la risposta, per quali $i=1,2$ esiste un grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d_i$. In caso di risposta affermativa costruire un tale grafo e dire, motivando la risposta, se tale score è realizzabile da un albero.
Soluzione

Esercizio 5   Sia $G$ un grafo 2-connesso. Si provi che $G$ non ha foglie. Dire, motivando la risposta, se è vero che un grafo finito, connesso, senza foglie e con almeno tre vertici è necessariamente $2$-connesso.
Soluzione

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

1. $G_1=(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}6\mathbb{Z}}} {{}_{\!\... ...{\!\scriptstyle {}6\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}6\mathbb{Z}}},E_1)$, essendo $E_1=\big\{\{n,m\}\bigm\vert n-m=1 \hbox{\rm { in }} \mathbb{Z}\big/\mathchoice... ...\!\scriptstyle {}6\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}6\mathbb{Z}}}\big\}$
2. $G_2=(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}6\mathbb{Z}}} {{}_{\!\... ...{\!\scriptstyle {}6\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}6\mathbb{Z}}},E_2)$, essendo $E_2=\big\{\{n,m\}\bigm\vert n-m=2 \hbox{\rm { in }} \mathbb{Z}\big/\mathchoice... ...\!\scriptstyle {}6\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}6\mathbb{Z}}}\big\}$
3. $G_3=((\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}7\mathbb{Z}}} {{}_{\!... ...\scriptstyle {}7\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}7\mathbb{Z}}})^*,E_3)$, essendo $E_3=\big\{\{n,m\}\bigm\vert n=3m \hbox{\rm { in }} \mathbb{Z}\big/\mathchoice ... ...\!\scriptstyle {}7\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}7\mathbb{Z}}}\big\}$

Soluzione