Soluzioni proposte

Soluzione dell'esercizio 1  $(156,108)=12\mathrel{\big\vert}-12 = 8-20$ quindi il sistema è risolubile. Inoltre, usando l'algoritmo di Euclide, si ottiene $12 = (-2) \cdot 156 + (3) \cdot 108$ quindi

$$8-20 = -12 = -((-2) \cdot 156 + (3) \cdot 108) = 2\cdot 156 - 3 \cdot 108$$

e pertanto $x_0= 332= 8+3\cdot 108 = 20 + 2\cdot 156$ è una soluzione del sistema.

L'insieme delle soluzioni è allora dato da $\{ 332 + k [156,108] \mid k\in\mathbb{Z}\}=\{ 332 + k 1404 \mid k\in\mathbb{Z}\}$     

Soluzione dell'esercizio 2 (1). Se $\left\vert X\right\vert=k$ e $\left\vert Y\right\vert=n$ allora l'insieme delle funzioni iniettive da $X$ in $Y$ ha cardinalità ${n \choose k}k!=\frac{n!}{(n-k)!}$. Nel nostro caso $n=8$, $k=6$, quindi

$$\left\vert\{f\in Y^X\mid f \text{ \\lq e iniettiva}\}\right\vert=\frac{8!}{(8-6)!}=8\cdot7\cdot6\cdot5\cdot4\cdot3=20160.$$

(2). Se consideriamo $X'=X\setminus\{1\}$ e $Y'=Y\setminus\{4\}$ alora l'insieme $\{f\in Y^X\mid f$    è iniettiva e $f(1)=4\}$ può essere messo in bigezione con l'insieme $\{f\in {Y'}^{X'}\mid f$    è iniettiva$\}$ mediante la restrizione. Ma allora, applicando la stessaa formula del punto precedente, si ottiene che la cardinalità cercate è pari a

$$\left\vert\{f\in Y^X\mid f \text{ \\lq e iniettiva e }f(1)=4\}\right... ...\\lq e iniettiva}\}\right\vert= \frac{7!}{(7-5)!}=7\cdot6\cdot5\cdot4\cdot3=2520.$$

(3). Dato che $f$ è iniettiva, $\left\vert f^{-1}(\{0,1\})\right\vert\le\left\vert\{0,1\}\right\vert=2$. D'altra parte, dato che $\left\vert Y\setminus\{0,1\}\right\vert = 6 \ge \left\vert X\right\vert \ge 2 =\left\vert\{0,1\}\right\vert$, possono essere assunti tutti i tre valori $0,1,2,3$. Costruiamo degli esempi:

$$f_i : X \longrightarrow Y \qquad\qquad i=0,1,2$$

$$f_0 : x \longrightarrow x+1$$

$$f_1 : x \longrightarrow x$$

$$f_2 : x \longrightarrow x-1$$

Si verifica immediatamente che per ogni $i=0,1,2$ si ha che $\left\vert f_i^{-1}(\{0,1\})\right\vert=i$.     

Soluzione dell'esercizio 3 Un grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d_2$ dovrebbe avere $9$ vertici, due vertici, chiamiamoli $u$ e $v$, di grado $8$, ossia adiacenti a tutti gli altri. Ma allora ogni vertice diverso da $u$ e $v$ questi due deve essere adiacente almeno ad uno di loro e quindi avere grado almeno $2$. Ma se $\mathop{\rm score}\nolimits (G)=d_2$ esiste almeno un vertce di grado $1$, che è in contraddizione con quanto appena provato. Quindi un tale $G$ non può esistere.

Per $d_1$ usiamo il teorema dello score:

$$\begin{array}{lcl} d_1 & = & (2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 10, 1... ...1, 2, 3, 3, 9) \\ d_1'' & = & (1, 0, 0, 0, 0, 0, 0, 1, 2, 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 $1,2,3,4,5,6,7,8,9,10$, e dai lati $\{7,8\},\{8,9\},\{9,10\}$ che realizzano lo score $d_1''$ a cui sono successivamente aggiunti i vertici $11,12$ ottenendo dei grafi, che realizzano, nell'ordine, gli score $d_1'$ e $d_1$.

(1). La risposta è no. Se $G=(V,E)$ è un grafo tale che $\mathop{\rm score}\nolimits (G)=d_1$ allora $\left\vert V\right\vert=12$ e $\left\vert E\right\vert=\frac{1}{2}\sum\limits_{v\in V} \deg{v}=\frac{1}{2}(2+ 2+ 2+ 2+ 2+ 2+ 2+ 3+ 4+ 4+ 10+ 11)=23$. Ma allora $\left\vert E\right\vert=23\ne 11 =\left\vert V\right\vert-1$, quindi $G$ non può essere un albero.

(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)=11$, ossia ogni altro vertice è adiacente e quindi congiungibile con $v$. Ne consegue che $G$ è connesso.

(3). Che il grafo di figura 1 sia $2$-connesso lo si può vedere mostrando che è ottenuto da un ciclo con successive aggiunzioni e suddivisioni di lati (cfr. figura).

Figura 2: Il grafo di figura 1 è ottenuto da un ciclo mediante aggiunzione e suddivisione di lati, quindi è $2$-connesso

Un altro modo di provare la $2$-connessione di questo grafo è il seguente. Sia $G$ il grafo e sia$w$ il vertice di grado $11$. Chiaramente, per ogni $v\ne w$ si ha che $G-v$ ha un vertice di grado $10$ (e $11$ vertici) e quindi è connesso. D'altra parte $G$ ha anche un vertice $u$ di grado $10$ e quindi $u$ ha grado $9$ in $G-w$ (è adiacente a tutti i suoi vertici tranne uno) e dato che ogni vertice di $G$ ha grado almeno $2$, ogni vertice di $G-w$ ha grado almeno $1$. Ma allora l'unico vertice $v$ di $G-w$ non adiacente a $u$ sarà adiacente almeno ad un altro vertice $t$ e quindi $P=(u,t,v)$ è un cammino tra $u$ e $v$ in $G-w$. Ne consegue che tutti i vertici di $g-w$ sono congiungibili a $u$ e quindi anche $G-w$ è connesso. Questo ragionamento prova in realtà che ogni grafo tale che $\mathop{\rm score}\nolimits (G)=d_1$ è $2$-connesso.     

Soluzione dell'esercizio 4 Il primo grafo non è $2$-connesso, infatti se a questo grafo si toglie il vertice $G$ si ottengono i due cicli disgiunti $(A,B,F,A)$ e $(C,D,E,C)$, mentre il secondo grafo è hamiltoniano (e quindi quindi è $2$-connesso) in quanto c'è il ciclo $(a,b,e,f,g,c,d,a)$.

Di conseguenza il primo ed il secondo grafo non sono isomorfi.

Il secondo e il terzo grafo sono isomorfi (conseguentemente il primo e il terzo non lo sono). Un isomorfismo è dato ad esempio dalla funzione $f$ definita da:

$$\begin{array}{rclcrcl} a &\mapsto &\chi &\hbox{\kern1cm}& e &\map... ...apsto &\epsilon && g &\mapsto &\varphi \\ d &\mapsto &\delta \\ \end{array}$$

Che tale funzione sia un isomorfismo segue da una semplice verifica. L'insieme dei lati del secondo grafo è dato da

$$\big\{ \{b,a\}, \{a,d\}, \{d,c\}, \{c,b\}, \{g,c\}, \{a,e\}, \{b,g\}, \{g,f\}, \{f,e\}, \{e,b\} \big\}$$

i cui trasformati tramite $f$ sono

$$\big\{ \{\gamma,\chi\}, \{\chi,\delta\}, \{\delta,\epsilon\}, \{\... ...mma,\varphi \}, \{\varphi ,\alpha\}, \{\alpha,\beta\}, \{\beta,\gamma\} \big\}$$

che sono proprio tutti e soli i lati del terzo grafo.