next up previous
Next: About this document ... Up: Testo degli esercizi Previous: Testo degli esercizi

Soluzioni proposte

Soluzione dell'esercizio 1 

    back.gif


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}$.     back.gif


Soluzione dell'esercizio 3 

    back.gif


Soluzione dell'esercizio 4 

    back.gif


Soluzione dell'esercizio 5 Usiamo il teorema dello score:

\begin{displaymath}
\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}\end{displaymath}

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$
\begin{figure}\begin{center}
\psfig{file=fige5.2.ps,width=6cm} \end{center}\end{figure}

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
\begin{figure}\begin{center}
\psfig{file=fige5.2.2.ps,width=.95\hsize} \end{center}\end{figure}

    back.gif


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{displaymath}
\begin{array}{rclcrcl}
\alpha &\mapsto &A &\hbox{\kern1cm}...
... &D && \psi &\mapsto &G\\
\delta &\mapsto &C \\
\end{array}\end{displaymath}

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.     back.gif



next up previous
Next: About this document ... Up: Testo degli esercizi Previous: Testo degli esercizi
Luminati Domenico 2002-05-16