Soluzioni proposte

Soluzione dell'esercizio 1 Osserviamo innanzitutto che $(2,21)=1$, quindi $2$ è invertibile modulo $21$, per tanto la soluzione, se esiste, è un elemento invertibile. Osserviamo ancora che $\Phi(21)=\Phi(7\cdot 3)=6\cdot 2=12$, quindi $(5,\Phi(21))=(5,12)=1$ pertanto esiste $x$ tale che $5x\cong 1\quad{\rm mod}\ \Phi (21)$. Per il piccolo teorema di Fermat, $\left[2^x\right]_{21}$ è allora la soluzione della congruenza.

Determiniamo $x$. $1 =25 -24 = 5\cdot 5-2\cdot12$, quindi $x=5$. Ma allora la soluzione è data da $\left[2^5\right]_{21}=\left[32\right]_{21}=\left[11\right]_{21}$.     

Soluzione dell'esercizio 2 (1). Per induzione. Per $n=0,1$ è ovvio dalla definizione. Sia $n\ge2$ e supponiamo che la tesi sia vera per ogni $k<n$, allora $x_n=4 x_{n-1} - x_{n-2}$ è somma di un numero pari ($4 x_{n-1}$) e di un numero, $-x_{n-2}$, che, per ipotesi di induzione, è dispari. Quindi $x_n$ è dispari.

(2). Per induzione. Se $n=0$, $(x_1,x_0)=(5,1)=1$. Supponiamo la tesi vera per $n$ e proviamola per $n+1$. Dalla relazione di ricorrenza si ha che $(x_{n+2},x_{n+1})=(x_{n+1},-x_{n})=(x_{n+1},x_{n})$ e per ipotesi di induzione, quest'ultimo è $1$.

(3). Il polinomio caratteristico di tale equazione ricorsiva è dato da $t^2-4t+1$ le cui radici sono: $2+\sqrt{5}$ e $2-\sqrt{5}$. Quindi una generica soluzione della relazione ricorsiva è data da: $x_n=\alpha(2+\sqrt{5})^n+\beta(2-\sqrt{5})^n$. Determiniamo $\alpha$ e $\beta$ in modo che siano verificate le condizioni iniziali.

$$\left\{ \begin{array}{l} \alpha+\beta=1 \\ (2+\sqrt{5})... ...5}}{10} \\ \beta=\frac{5-3\sqrt{5}}{10} \end{array} \right.$$

Quindi un'espressione esplicita di $x_n$ è data da:

$$x_n=\frac{5+3\sqrt{5}}{10}(2+\sqrt{5})^n+\frac{5-3\sqrt{5}}{10}(2-\sqrt{5})^n.$$

    

Soluzione dell'esercizio 3 Indichiamo con $Y=\{1,\dots,n\}-X$. Per ogni $(\sigma,\tau)\in S_X\times S_y$ consideriamo l'applicazione $\varphi _{(\sigma,\tau)}:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$ definita da

$$\varphi _{(\sigma,\tau)}(i)=\Big\langle \begin{array}{lcl}... ...e }} i\in X \\ \tau(i) &&\hbox{\rm {se }} i\in Y \end{array}$$

Chiaramente, dato che $X\cap Y=\varnothing$ e $X\cup Y=\{1,\dots,n\}$ l'applicazione è ben definita.

$\varphi _{(\sigma,\tau)}$ è una permutazione. Basta provare che è iniettiva (dato che l'insieme di definizione è finito e coincide con il codominio). Siano $i\ne j$: se $i,j\in X$ allora $\varphi _{(\sigma,\tau)}(i)=\sigma(i)\ne\sigma(j)=\varphi _{(\sigma,\tau)}(j)$, dato che $\sigma$ è una permutazione; se $i,j\in Y$ allora $\varphi _{(\sigma,\tau)}(i)=\tau(i)\ne\tau(j)=\varphi _{(\sigma,\tau)}(j)$, dato che $\tau$ è una permutazione; infine se $i\in X$ e $j\in Y$ allora $\varphi _{(\sigma,\tau)}(i)=\sigma(i)\in X$ e $\varphi _{(\sigma,\tau)}(j)=\tau(j)\in Y$ e $\sigma(i)\ne\tau(j)$ poiché $X\cap Y\ne\varnothing$.

Osserviamo ora che, per definizione, $\varphi _{(\sigma,\tau)}\in{\cal S}$, ossia abbiamo definito una applicazione $\varphi :S_X\times S_y\to {\cal S}$. Proviamo che tale applicazione è bigettiva.

$\varphi$ è iniettiva. Se $\sigma\ne\sigma'$ esiste $i\in X$ tale che $\sigma(i)\ne\tau(i)$ e quindi $\varphi _{(\sigma,\tau)}(i)=\sigma(i)\ne\sigma'(i)=\varphi _{(\sigma',\tau)}(i)$ e quindi $\varphi _{(\sigma,\tau)}\ne\varphi _{(\sigma',\tau)}$. Analogamente se $\tau\ne\tau'$ allora $\varphi _{(\sigma,\tau)}\ne\varphi _{(\sigma',\tau')}$.

$\varphi$ è surgettiva. Sia $\sigma\in {\cal S}$, allora $\setbox\restrictbox=\hbox{$\hbox{$\sigma$}_{X}$}\setbox0\hbox{$\sigma$} {{\sigm... ...depth\dp\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{X}}\in S_X$, e dato che $\sigma$ è bigettiva, anche $\sigma(Y)= Y$ e quindi $\setbox\restrictbox=\hbox{$\hbox{$\sigma$}_{Y}$}\setbox0\hbox{$\sigma$} {{\sigm... ...depth\dp\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{Y}}\in S_Y$. È immediato allora vedere che $\sigma=\varphi _{(\setbox\restrictbox=\hbox{$\hbox{$\sigma$}_{X}$}\setbox0\hbox... ...box depth\dp\restrictbox\, \hbox{\vrule depth\dp0 height \ht0 width0pt}_{Y}})}$.

Ma allora

$$\left\vert{\cal S}\right\vert=\left\vert S_X\times S_Y\righ... ...ft\vert S_X\right\vert\cdot\left\vert S_Y\right\vert=k!(n-k)!.$$

    

Soluzione dell'esercizio 4 Sia $v$ un vertice di grado $k$ (massimo possibile), allora $G-v$ è un grafo connesso, quindi contiene un albero generatore $T$ (ossia tale che $V(T)=V(G-v)$. Ma allora, per la relazione che lega il numero di vertici e il numero di lati di un albero,

$$\left\vert E(G-v)\right\vert \ge \left\vert(E(T)\right\vert=\left\vert V(T)\right\vert-1=\left\vert V(G-v)\right\vert-1.$$ (1)

D'altra parte, $\left\vert V(G-v)\right\vert=\left\vert V(G)\right\vert-1$, e dato che $\deg(v)=k$, $\left\vert E(G-v)\right\vert=\left\vert E(G)\right\vert-k$. Mettendo queste due relazioni nella 1 si ottiene

$$\left\vert E(G)\right\vert-k \ge \left\vert V(G)\right\vert-1 -1$$

da cui la tesi.

Il viceversa non è vero. Si consideri ad esempio il grafo rappresentato in figura 1:

Figura 1: L'esempio della soluzione dell'esercizio 4

per questo grafo si ha che $\left\vert E\right\vert=7$, $\left\vert V\right\vert=6$ e $k=\max\deg(v)=3$, e quindi $\left\vert E\right\vert=\left\vert V\right\vert+k-2$, però tale grafo non è $2$-connesso.     

Soluzione dell'esercizio 5 Usiamo il teorema dello score:

$$\begin{array}{lcl} d & = & (2,2,2,2,3,3,3,5,6)\\ d_1 & =... ...= & (1,1,1,1,1,1,2)\\ d_3 & = & (1,1,1,1,0,0)\\ \end{array}$$

Dato che $d_3$ è realizzabile come score di un grafo, anche $d$ lo è. La costruzione standard, condotta con un po' di attenzione, produce il grafo in figura, che è anche connesso e $2$-connesso.

Figura 2: Il grafo costruito della soluzione dell'esercizio 5. La configurazione di partenza è data dai vertici $1,2,3,4,5,6$, e dai due lati $\{2,3\},\{4,5\}$ che realizzano lo score $d_3$ a cui sono successivamente aggiunti i vertici $7,8,9$ ottenendo dei grafi, che realizzano, nell'ordine, gli score $d_2$, $d_1$ e infine $d$

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

Figura 3: Il grafo della soluzione dell'esercizio 5 è $2$-connesso

    

Soluzione dell'esercizio 6 Il primo grafo è hamiltoniano (in particolare quindi è $2$-connesso) in quanto c'è il ciclo $(a,b,c,d,e,f,g,a)$.

Il terzo grafo non è $2$-connesso, infatti se a questo grafo si toglie il vertice $G$ si ottengono i due cicli $(A,D,E)$ e $(B,C,F)$.

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

$$\begin{array}{rclcrcl} \alpha &\mapsto &A &\hbox{\kern1cm}... ... &D && \psi &\mapsto &G\\ \delta &\mapsto &C \\ \end{array}$$

Che tale funzione sia un isomorfismo segue dal fatto che il vertice $\psi$ e la sua immagine $G$ sono collegati con tutti gli altri vertici. I vertici $(\alpha,\gamma\epsilon$ oltre a essere collegati con $\psi$ sono collegati soltanto tra loro in tutti i modi possibili e anche le rispettive immagini $A,D,E$ sono collegati solo tra loro (in tutti i modo possibili) oltre che con $G$. Anche l'altra terna di vertici $\beta,\delta,\varphi$ e le rispettive immagini $B,C,F$ hanno la stessa proprietà, quindi i lati di un grafo sono messi in bigezione con i lati dell'altro.