Matematica Discreta (II modulo)

quinto appello, a.a. 1999/2000

22 gennaio 2001

Esercizio 1   Si consideri la funzione $\sigma :\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}17\mathbb{Z}}} {{}_... ...{}_{\!\scriptstyle {}17\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}17\mathbb{Z}}}$ definita da $\sigma(\left[x\right])=\left[13\right]\left[x\right]$. Dopo aver dimostrato che $\sigma$ è una permutazione, se ne trovi la decomposizione in cicli disgiunti. Si dica infine qual'è il minimo $k>0$ tale che $\sigma^k={\rm id}$.
Soluzione

Esercizio 2   Sia $x_n$ la successione definita per ricorrenza da:

$$\left\{ \begin{array}{lcl} x_{n+2}= 3 x_{n+1} + 2 x_{n} &... ...x{\rm {se }}n\ge 0 \\ x_1=5 \\ x_0=15 \end{array} \right.$$

1. Provare che $x_n$ è dispari per ogni $n$
2. Determinare il massimo comun divisore $(x_{n+1},x_{n})$ per ogni $n$.

Soluzione

Esercizio 3   Siano $n,m,k\in\mathbb{Z}$. Si provi che se $(n,m)=1$ allora $(n,mk)=(n,k)$. Dire, motivando la risposta se è vero il viceversa.
Soluzione

Esercizio 4   Si provi che se un albero ha un vertice di grado $k$, allora ha almeno $k$ foglie.

Dire, motivando la risposta con una dimostrazione o un contresempio, se è vero il viceversa.
Soluzione

Esercizio 5   Siano $d_1=(3,3,3,4,4,5,6)$ e $d_2=(1,1,1,1,4,4)$. Dire in quale dei due casi esiste un grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d$. In caso di risposta affermativa, dire se un tale grafo

1. può essere sconnesso
2. può essere senza cicli

Soluzione

Esercizio 6   Dire quali tra i grafi rappresentati in figura sono tra loro isomorfi e quali no:

Soluzione