next up previous
Next: About this document ... Up: Matematica Discreta (II modulo) Previous: Matematica Discreta (II modulo)

Soluzioni proposte

Soluzione dell'esercizio 1 $ (35,38)=1$ ossia $ 35$ è invertibile modulo $ 38$. Inoltre $ \Phi(38)=\Phi(2\cdot19)=1\cdot18=18$, e $ (11,18)=1$ quindi la congruenza ha soluzione unica $ \quad{\rm mod}\ 38$. Determiniamo un inverso positivo di $ 11$ modulo $ 18$.
$\displaystyle 18$ $\displaystyle =$ $\displaystyle 11 + 7$  
$\displaystyle 11$ $\displaystyle =$ $\displaystyle 7 + 4$  
$\displaystyle 7$ $\displaystyle =$ $\displaystyle 4 + 3$  
$\displaystyle 4$ $\displaystyle =$ $\displaystyle 3 + 1$  

da cui

$\displaystyle 1 = 4 - 3 = 4 - ( 7 - 4 ) = 2\cdot 4 -7 = 2(11-7) - 7 = 2\cdot 11 -3\cdot 7
= 2 \cdot 11 -3(18 - 11) = 5 \cdot 11 - 3 \cdot 18.
$

Quindi $ 5$ è un inverso positivo di $ 11$ modulo $ 18$, pertanto la congruenza è equivalente a $ x\cong 35^5\quad{\rm mod}\ 38$ e quindi le soluzioni intere sono date da $ \left[35^5\right]_{38}=\left[(-3)^5\right]_{38}=\left[(-3)^3\right]_{38}\left[...
...eft[11\right]_{38}\left[9\right]_{38}=\left[99\right]_{38}=\left[23\right]_{23}$. Dato che $ 0\le 23 < 38$, $ 23$ è la più piccola soluzione intera.     back.gif


Soluzione dell'esercizio 2 (1). L'insieme $ {\cal P}_1$ è in bigezione con $ 2^{X\setminus Y}$, una bigezione essendo data da $ \Phi_1:{\cal P}_1\to 2^{X\setminus Y}$ definita ponendo $ \Phi_1(A)=
A\setminus Y$. Ma allora

$\displaystyle \left\vert{\cal P}_1\right\vert=\left\vert 2^{X\setminus Y}\right...
...ght\vert}=2^{\left\vert X\right\vert-\left\vert Y\right\vert}= 2^{9-4}=2^5=32.
$

(2). $ {\cal P}_2$ è in bigezione con $ {Y \choose 2}\times (X\setminus Y)$, una bigezione è data da $ \Phi_2:{\cal P}_2\to{Y \choose 2}\times 2^{X\setminus Y}$ definita ponendo $ \Phi_2(A)=\big(A\cap Y, A\cap(X\setminus Y)\big)$. Ma allora

$\displaystyle \left\vert{\cal P}_2\right\vert=\left\vert{Y \choose 2}\times
2^{...
...left\vert Y\right\vert \choose 2}32 ={4 \choose 2} \cdot 32 =
6\cdot 32 = 192.
$

(3). $ {\cal P}_3=2^X\setminus 2^{X\setminus Y}$, infatti $ A\cap Y\ne\varnothing $ equivale a dire che $ A\not\subseteq X\setminus Y$. Ma allora

$\displaystyle \left\vert{\cal P}_3\right\vert= \left\vert 2^X\setminus 2^{X\set...
...2^{\left\vert X\setminus Y\right\vert}=
2^9-2^5 = 2^5(2^4-1)=32\cdot 15 = 480.
$

    back.gif


Soluzione dell'esercizio 3 Un grafo $ G$ tale che $ \mathop{\rm score}\nolimits (G)=d_1$ dovrebbe avere $ 5$ vertici di grado dispiri, ma sappiamo che in ogni grafo il numero di vertici di grado dispari è pari, quindi un tale $ G$ non può esistere.

Per $ d_2$ usiamo il teorema dello score:

$\displaystyle \begin{array}{lcl}
d_2 & = & (1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,...
...3) \\
d_2'' & = & (0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 2)
\end{array}$

Dato che $ d_2''$ è realizzabile come score di un grafo, anche $ d_1$ lo è. La costruzione standard produce il grafo in figura.

Figura: 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,11,12$, e dai lati $ \{6,7\},\{7,8\},\{9,10\},\{11,12\}$ che realizza $ d_2''$ a cui sono successivamente aggiunti i vertici $ 13,14$ ottenendo dei grafi, che realizzano, nell'ordine, $ d_2'$ e $ d_2$.
\begin{figure}\begin{center}
\psfig{file=fig_a2_1_e31_2001.eps,width=.4\hsize} \end{center}\end{figure}

(1). La risposta è si. Con un po' di attenzione si può costruire il grafo di figura, che è un albero.

Figura: Un albero che realizza lo score $ d_2$ dell'esercizio 3.
\begin{figure}\begin{center}
\psfig{file=fig_a2_1_e32_2001.eps,width=7cm} \end{center}\end{figure}

(2). La risposta è sì. Il grafo costruito in figura è evidentemente sconnesso.

(3). Un tale grafo non potrà certamente essere $ 2$-connesso dato che contiene necessariamente dei vertici di grado $ 1$, e sappiamo che ciò è impossibile nei grafi $ 2$-connessi.     back.gif


Soluzione dell'esercizio 4 $ G_3$ non è $ 2$-connesso, infatti se glio si toglie il vertice $ A$ si ottengono i due cicli disgiunti $ (B,C,D,E,B)$ e $ (F,G,H,F)$.

Il grafo $ G_2$ è hamiltoniano (e quindi quindi è $ 2$-connesso) in quanto c'è il ciclo $ (1,3,4,5,6,7,8,9,2,1)$ che contiene tutti i vertici.

Anche il grafo $ G_1$ è hamiltoniano (e quindi quindi è $ 2$-connesso) in quanto c'è il ciclo $ (\alpha,\delta,\epsilon,\varphi ,\gamma,\eta,\lambda,\beta,\chi,\alpha)$.

Di conseguenza il primo ed il secondo grafo non sono isomorfi $ G_1\not\oldcong G_3$ e $ G_2\not\oldcong G_3$.

Neanche $ G_1$ e $ G_2$ sono isomorfi, infatti in $ G_1$ c'è un vertice $ \beta$ che ha grado $ 2$ ed i vertici a lui adiacenti $ \chi$ e $ \lambda$ hanno entrambi grado $ 3$. Se ci fosse un isomorfismo $ f:G_1\to G_2$ dovrebbe esserci un vertice $ f(\beta)$ in $ G_2$ con le stesse proprietà, ma i quattro vertici di $ G_2$ che hanno grado $ 2$ sono adiacenti ciascuno ad al più un vertice di grado $ 3$, più esplicitamente:

    back.gif



next up previous
Next: About this document ... Up: Matematica Discreta (II modulo) Previous: Matematica Discreta (II modulo)
Luminati Domenico 2002-07-19