Matematica Discreta (II modulo)

Terzo appello, a.a. 1999/2000

4 settembre 2000

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

Esercizio 2   Si determini la soluzione dell'equazione ricorsiva lineare

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

con dati iniziali $x_0=-2$ e $x_1=3$.

Si provi che se $n$ è pari allora $x_n$ è un intero pari e che se $n$ è dispari, allora $x_n$ è un intero dispari.
Soluzione

Esercizio 3   Siano $X$ e $Y$ insiemi finiti e $A\subset X$, $B\subset Y$. Si determini, in funzione delle cardinalità di $X$, $Y$, $A$ e $B$, la cardinalità degli insiemi

$$\begin{eqnarray*} {\cal F}_1 & = & \big \{ f \in Y^X \bigm\vert f(A) \subseteq ... ...{\cal F}_1 \hbox{\rm { e }} f \hbox{\rm { \\lq e iniettiva}}\big\} \end{eqnarray*}$$

.
Soluzione

Esercizio 4   Sia $d=(2,2,2,2,,4,4,6,6)$. Si provi che esiste un grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d$ e se ne determini uno esplicitamente.

1. Si provi che ogni tale grafo $G$ è euleriano.
2. Si determini un percorso euleriano per il grafo costruito esplicitamente.

Soluzione

Esercizio 5   Dati un grafo $G=(V,E)$ e $w\notin V$ denotiamo con $C_w(G)$ il grafo definito da:

$$\begin{eqnarray*} V(C_w(G)) & = & V\cup\{w\} \\ E(C_w(G)) & = & E \cup \big\{\{w,v\}\bigm\vert v\in V\big\} \end{eqnarray*}$$

Si provi che se $G$ è connesso e ha più di due vertici, allora $C_w(G)$ è 2-connesso.
Soluzione

Esercizio 6   Dire quali dei tre seguenti grafi sono tra loro isomorfi e quali no.

Soluzione