Soluzioni proposte

Soluzione dell'esercizio 1  $(117,81)=9\mathrel{\mathrel{\Big\vert}}-9 = 20$ quindi i - 11 sistema e` risolubile. Inoltre $9 = (-2) \cdot 117 + (3) \cdot 81$ quindi $20 - 11= 9 = (-2) \cdot 117 + (3) \cdot 81$ quindi $x_0= 254 = 20 + 2 \cdot 117 = 11 + 3 \cdot 81$ è una soluzione del sistema. Tutte le soluzioni sono allora date da $\{ 254 + k [81,117] \mid k\in\mathbb{Z}\}=\{ 254 + k 1053 \mid k\in\mathbb{Z}\}$     

Soluzione dell'esercizio 2 (1). L'insieme $\mathcal{A}=\{Y\subseteq A\cup B\mid a\in Y\}$ è in bigezione con l'insieme $\{Y\subseteq A\cup B\setminus \{a\}\} = 2 ^{A\cup B\setminus \{a\}}$. Una bigezione è data ad esempio dalla funzione $\Phi :\mathcal{A} \to 2^{A\cup B\setminus \{a\}}$ definita da

$$\Phi(A) = A\setminus \{a\}$$

la cui inversa è data da $\Psi :2^{A\cup B\setminus \{a\}} \to \mathcal{A}$ definita da

$$\Psi(A) = A \cup \{a\}.$$

Ma allora $\left\vert\mathcal{A}\right\vert=\left\vert 2^{A\cup B\setminus \{a\}}\right\v... ...etminus \{a\}}\right\vert} = 2^{\left\vert{A\cup B}\right\vert-1} = 2^{n+m-k-1}$, dato che $\left\vert A\cup B\right\vert = \left\vert A\right\vert+\left\vert B\right\vert-\left\vert A\cap B\right\vert$.

(2). L'insieme $\mathcal{B} = \{f\in B^A\mid f(a)=b\}$ è in bigezione con l'insieme $B^{A\setminus \{a\}}$. Una bigezione è data ad esempio dalla funzione $\Phi : \mathcal{B} \to B^{A\setminus \{a\}}$ definita da

$$\Phi(f) = \setbox\restrictbox=\hbox{$\hbox{$f$}_{A\setminus\{a\}}... ...\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{A\setminus\{a\}}}$$

la cui inversa è la funzione $\Psi : B^{A\setminus \{a\}}\to \mathcal{B}$ definita da

$$\Psi(g) : x \mapsto \big\langle \begin{array}{lll} f(x) &\text{se } x \ne a \\ b &\text{se } x = a \end{array}$$

Ma allora $\left\vert\mathcal{B}\right\vert = \left\vert B^{A\setminus \{a\}}\right\vert = m^{n-1}$     

Soluzione dell'esercizio 3 $d_1$ non può essere lo score di un grafo, dato che contiene un numero dispari (9) di elementi dispari.

$d_2$ è lo score di un grafo, ad esempio se si usa il teorema dello score:

$$d_2 = (1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4, 5)$$

$$d_2' = (1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 2, 2, 3)$$

$$d_2' = (0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3)$$

$$d_2'' = (0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1)$$

Figura 1: Sulla sinistra il grafo costruito per la soluzione dell'esercizio 3 a partire dalla riduzione di $d_2$. La configurazione di partenza è data dai vertici $1,2,3,4,5,6,7, 8, 9, 10, 11, 12$, e dai lati $\{3,4\},\{5,6\},\{7,8\},\{9,10\},\{11,12\}$ che realizzano lo score $d_2''$ a cui sono successivamente aggiunti i vertici $13$ e $14$ ottenendo dei grafi, che realizzano, nell'ordine, gli score $d_2'$ e $d_2$. Sulla sinistra un albero che ha $d_2$ come score.

(1). La risposta è sì. Basta prendere ad esempio il grafo sulla destra di figura 1.

(2). La risposta è sì. Basta prendere ad esempio il grafo sulla sinistra di figura 1.

(3). La risposta è no, dato che in un grafo 2-connesso non possono esserci vertici di grado 1.

    

Soluzione dell'esercizio 4 $G_2$ è hamiltoniano, ad esempio $(a,g,b,c,d,e,f,a)$ è un ciclo hamiltoniano di $G_2$. In particolare $G_2$ è 2-connesso. $G_1$ e $G_3$ non sono 2-connessi, dato che $G_1-7$ e $G_3-G$ sono isomorfi all'unione disgiunta di due 3-cicli. Quindi $G_1 \not\oldcong G_2$ e $G_2\not\oldcong G_3$.

In $G_3$ gli unici due vertici di grado $2$ sono congiunti da un lato, mentre in $G_1$ i due vertici di grado $2$ non sono adiacenti. Quindi $G_1\not\oldcong G_3$.