Soluzioni proposte

Soluzione dell'esercizio 1  $(1386,180)=18\mathrel{\big\vert}18 = 15-(-3)$ quindi il sistema è risolubile. Inoltre, usando l'algoritmo di Euclide, si ottiene $18 = 3 \cdot 1386 + (-23) \cdot 180$ quindi

$$15-(-3) = 18 = 3 \cdot 1386 + (-23) \cdot 180 -16 \cdot 81$$

e pertanto $x_0= 15 -3\cdot 1386 = -3 + (-23) \cdot 180 = -4143$ è una soluzione del sistema.

L'insieme delle soluzioni è allora dato da $\{ -4143 + k [1386,180] \mid k\in\mathbb{Z}\}=\{ -4143 + k 13860 \mid k\in\mathbb{Z}\} =\{ 9717 + k 13860 \mid k\in\mathbb{Z}\} = \left[9717\right]_{13860}$.     

Soluzione dell'esercizio 2  (1). $\left\vert\{f\in B^{A}: \;\textrm{f \\lq e iniettiva}\}\right\vert = \frac{\left\... ... !}{(12 - \Phi(12))!}=\frac{12!}{(12 - 4)!}=12\cdot 11 \cdot 10 \cdot 9 = 11880$.

(2). Sia $B' = \mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}12\mathbb{Z}}} {{}_{\!\... ...12\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}12\mathbb{Z}}} \setminus \{\bar{0}\}$ e $A' = (\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}12\mathbb{Z}}} {{}_{\!... ...mathbb{Z}}} {{}_{\!\scriptscriptstyle {}12\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\... ...ft\vert\{f\in {B'}^{A'}: \;\textrm{f \\lq e iniettiva}\}\right\vert = 11!/8! = 990$.

(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^4 - 1 = 15$.     

Soluzione dell'esercizio 3 Se $G=(V,E)$ è un grafo tale che $\mathop{\rm score}\nolimits (G)=d_2$ allora $\left\vert V\right\vert=8$ e ci sono due vertci, chiamiamoli $u$ e $v$, di grado rispettivamente $5$ e $7$. Ma allora i vertci che sono adiacenti sia a $u$ che a $v$ devono essere almeno $4$ (in un insieme con $8$ elementi due sottinsiemi dicardinalità $5$ e $7$ hanno intersezione di cardinalità almeno $7+5 - 8 = 4$) e quindi ci dovrebbero essere almeno $4$ 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 $2$.

Per $d_1$ usiamo il teorema dello score:

$$\begin{array}{lcl} d_1 & = & (2, 2, 2, 2, 3, 3, 5, 5, 8, 8)\\ d_... ...& = & (0, 0, 1, 1, 1, 1, 3, 3)\\ d_1'''& = & (0, 0, 1, 1, 0, 0, 2) \end{array}$$

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

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 successivamente quelli rossi, quelli blu ed infine quelli verdi.

(1). La risposta è no. Ogni albero finito havertici di grado $1$, mentre in un tale grafo ogni vertice ha grado $\ge 2$..

(2). La risposta è no. Se $G=(V,E)$ è un grafo tale che $\mathop{\rm score}\nolimits (G)=d_1$ allora esiste $v\in V$ tale che $\deg(V)=8$, ossia ogni altro vertice, tranne uno, è adiacente e quindi congiungibile con $v$. D'altra parte l'unico vertice non ancora considerato ha grado positivo, e quindi deve essere congiungibile con almeno uno degli altri. Quindi $G$ è connesso.

(3). Che il grafo di figura 1 sia $2$-connesso lo si può vedere ad esempio mostrando che è ottenuto da un ciclo con successive 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_4$. Anche $G_2$ non è 2-connesso, dato che $G_2 - 5$ è isomorfo all'unione disgiunta di due $C_4$. Invece $G_3$ è hamiltoniano (e quindi $2$-connesso) in quanto contiene il ciclo $(A,B,C,E,F,I,H,G,D,A)$.

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

Anche $G_1 \not\oldcong G_2$, dato che in $G_1$ ogni vertice di grado $2$ è adiacente ad un altro vertice di grado $2$, mentre in $G_2$ i vertici $6$ e $8$ hanno grado $2$ ma sono adiacenti solo a vertici di grado $3$.