Soluzioni proposte

Soluzione dell'esercizio 1 

    

Soluzione dell'esercizio 2 $(77,8)=1$, quindi $8$ è invertibile modulo $77$, per tanto la soluzione, se esiste, è un elemento invertibile. Inoltre $\Phi(77)=\Phi(7\cdot 11)=6\cdot 10=60$, quindi $(7,\Phi(77))=(7,60)=1$ pertanto esiste $s$ tale che $7s\cong 1\quad{\rm mod} \Phi (77)$. Per il piccolo teorema di Fermat, $\left[8^x\right]_{77}$ è allora la soluzione della congruenza.

Usando l'algoritmo di Euclide, si ottiene $1=2\cdot 60-17\cdot 7$, e quindi la soluzione è data da $\left[8^43\right]_{77}=\left[50\right]_{77}$.     

Soluzione dell'esercizio 3 

    

Soluzione dell'esercizio 4 

    

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 1: 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 2: 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.