Soluzioni proposte

Soluzione dell'esercizio 1  $(315,1386)=63\mathrel{\big\vert}63 = 54-(-9)$ quindi il sistema è risolubile. Usando l'algoritmo di Euclide, si ottiene $63 = 9 \cdot 315 + (-2) \cdot 1386$ quindi

$$54-(-9)= 63 =\cdot 9 \cdot 315 + (-2) \cdot 1386$$

pertanto $x_0= 54 - 9 \cdot 315 = -9 -2 \cdot 1386 = -2781$ è una soluzione del sistema. L'insieme delle soluzioni è allora dato da $\{ -2781 + k [1386,315] \mid k\in\mathbb{Z}\}=\{ -2781 + k 6930 \mid k\in\mathbb{Z}\} = \{ 4149 + k 6930 \mid k\in\mathbb{Z}\} = \left[4149\right]_{6930}$.

    

Soluzione dell'esercizio 2 (1). $\left\vert\{f\in B^{A}: \;\textrm{f \\lq e iniettiva}\}\right\vert = \frac{\left\... ...!}= \frac{18!}{12!} = 18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13 =13366080$.

(2). Sia $B' = \mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}18\mathbb{Z}}} {{}_{\!\... ...18\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}18\mathbb{Z}}} \setminus \{\bar{0}\}$ e $A' = (\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}18\mathbb{Z}}} {{}_{\!... ...mathbb{Z}}} {{}_{\!\scriptscriptstyle {}18\mathbb{Z}}})^* \setminus \{\bar{1}\}$, allora l'insieme $\{f\in B^{A}: \;\textrm{f \\lq e iniettiva}, f(\bar 1)=\bar{0}\}$ è evidentemente in bigezione con $\{f\in {B'}^{A'}: \;\textrm{f \\lq e iniettiva}\}$ e quindi $\left\vert\{f\in B^{A}: \;\textrm{f \\lq e iniettiva}, f(\bar 1)=\bar{0}\}\right\... ...vert\{f\in {B'}^{A'}: \;\textrm{f \\lq e iniettiva}\}\right\vert = 17!/12! =742560$.

(3). L'insieme $\{f\in B^{A}: f(A)=C \}$ coincide con l'insieme $f \in C^A \mid f$   non è costante$\}$. Quindi la sua cardinalità è pari a $\left\vert C\right\vert ^ {\left\vert A\right\vert} - 1 = 2^6 - 1 = 63$.     

Soluzione dell'esercizio 3 Un grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d_1$ dovrebbe avere $10$ vertici, di cui due, chiamiamoli $u$ e $v$, di grado rispettivamente $7$ e $9$. Ma allora i vertci che sono adiacenti sia a $u$ che a $v$ devono essere almeno $6$ (in un insieme con $10$ elementi due sottinsiemi di cardinalità $7$ e $9$ hanno intersezione di cardinalità almeno $9+7 - 10 = 6$) e quindi ci dovrebbero essere almeno $6$ vertici diversi da $u$ e $v$ con grado almeno $2$. Ciò è in contraddizione con il fatto che di vertici di grado $\ge 2$ e diversi da $u$ e $v$ ce ne dovrebbero essere soltanto $4$.

Per $d_2$ usiamo il teorema dello score:

$$\begin{array}{lcl} d_2 & = & (2, 2, 3, 3, 4, 4, 7, 7)\\ d_2' & = & (1, 1, 2, 2, 3, 3, 6)\\ d_2'' & = & (0, 0, 1, 1, 2, 2) \end{array}$$

Dato che $d_2''$ è realizzabile come score di un grafo, anche $d_2$ lo è. La costruzione standard produce il grafo in figura.

Figura 1: Il grafo costruito per la soluzione dell'esercizio 3. La configurazione di partenza è data dai vertici e lati neri a cui si aggiungono quelli rossi e quelli blu.

(1). La risposta è no. Dato che non ha vertici di grado $1$.

(2). La risposta è no. Cè un vertice (anzi due) adiacente a tutti gli altri.

(3). La risposta è di. Il grafo in figura è 2-connesso. Non è difficile mostrare che lo si può ottenere da un ciclo mediante aggiunzioni e suddivisioni di lati.     

Soluzione dell'esercizio 4  $G_1$ non è $2$-connesso, infatti $G_1-e$ è dato dall'unione disgiunte di due $C_5$. Anche $G_3$ non è 2-connesso, dato che $G_2 - 5$ è isomorfo all'unione disgiunta di due $C_5$. Invece $G_2$ è hamiltoniano (e quindi $2$-connesso) in quanto contiene il ciclo $(A,B,C,D,E,M,L,I,H,G,F,A)$.

Di conseguenza $G_1\not\oldcong G_2$ e $G_2\not\oldcong G_3$.

Anche $G_1 \not\oldcong G_3$, dato che in $G_3$ ogni vertice di grado $3$ è adiacente ad un altro vertice di grado $3$, mentre in $G_1$ i vertici $7$ e $9$ hanno grado $3$ ma sono adiacenti a vertici di grado $2$ e $4$.