Soluzioni proposte

Soluzione dell'esercizio 1 $(2,51)=1$ quindi $2$ è invertibile $\quad{\rm mod}\ 51$. $\Phi(51)=32$ e $(32,23)=1$, quindi $23$ è invertibile $\quad{\rm mod}\ \Phi (51)$ e il suo inverso è dato da $7$. La soluzione della congruenza è data allora da $\left[2^{7}\right]_{51}=\left[26\right]_{51}$.

Il sistema è equivalente a

$$\begin{cases} x \equiv 26 \quad{\rm mod}\ 51 \\ x \equiv 4 \quad{\rm mod}\ 99 \end{cases}$$

che non è risolubile, dato che $(51,99)=3 \not\mathrel{\mathrel{\Big\vert}}22 = 26-4$.     

Soluzione dell'esercizio 2 Sia $T$. Un grafo $G$ ammette come albero di copertura $T$ se e solo se ha come insieme di vertici $V(T)$ (i.e. $V(G)=V(T)$) e se ha $T$ come sottografo ossia se e solo se $E(G)\supseteq E(T)$. Ma allora l'insieme dei grafi richiesto è in bigezione con l'insieme

$$\bigg\{ E \subseteq {V(T) \choose 2} \bigg\vert E\supseteq E(T) \bigg\} = 2 ^ {{V(T) \choose 2}-E(T)}$$

Dato che $\left\vert E(T)=n\right\vert$ allora $\left\vert V(T)\right\vert=n+1$ e quindi la cardinalità cercata è pari a

$$\left\vert 2 ^ {{V(T) \choose 2}-E(T)}\right\vert = 2^{\left\vert... ...ert} = 2^{({n+1 \choose 2}-n)} = 2^{\frac{n(n+1)}{2}-n} = 2^{\frac{n(n-1)}{2}}$$

    

Soluzione dell'esercizio 3 Se $G=(V,E)$ è un grafo tale che $\mathop{\rm score}\nolimits (G)=d_1$ allora $\left\vert V\right\vert=12$ e ci sono tre vertci di grado $11$. Ma allora ogni altro vertice deve essere adiacente a questi tre, e quindi ogni altro vertice dovrebbe avere grado almeno $3$, mentre in $d_1$ ci sono due $2$.

Per $d_2$ usiamo il teorema dello score:

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

$d_2'$ è realizzabile come una unione disgiunta di una copia di $C_3$ e di tre copie di $P_2$ e quindi anche $d_2$ è realizzabile.

(1). La risposta è sì. Si prenda ad esempio l'albero in figura 1.

Figura 1: Un albero che ha $d_2$ come score

(2). La risposta è sì. Basta prendere il grafo in figura 2 .

Figura 2: Un grafo che realizza $d_2$ ma che non è connesso

(3). La risposta è no. Un grafo $2$-connesso non può avere vertici di grado $1$, mentre ogni grafo che realizza $d_2$ ne ha $4$.     

Soluzione dell'esercizio 4  $(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\text... ..._{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ è l'insieme degli elementi invertibili di $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\texts... ...{{}_{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}}$ e quindi $(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\text... ...athbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*=\{1,2,4,7,8,11,13,14\}$. (1). Osserviamo che $7^2=49=4$, $7^3=4\cdot 7 = 28=13$, $4^4=13\cdot 7=91=1$, quindi i lati di $H$ sono dati da

$$E(K) = \big\{ \{1,7\},\{7,4\},\{4,13\},\{13,1\}, \{2,2\cdot7\}, \{2\cdot7,2\cdot4\}, \{2\cdot4,2\cdot13\}, \{2\cdot13,2\cdot1\} \big\}$$

$$= \big\{ \{1,7\},\{7,4\},\{4,13\},\{13,1\}, \{2,14\}, \{14,8\}, \{8,11\}, \{11,1\} \big\}$$

e quindi $K$ è isomorfo all'unione disgiunta di due copie di $C_4$.

Invece $4^2=16=1$ e quindi i lati sono dati da

$$E(K) = \big\{ \{1,4\},\{2,8\},\{7,13\},\{11,14\} \big\}$$

e quindi $H$ è isomorfo all'unione disgiunta di $4$ copie di $P_2$.

(2). Per quanto osservato sopra, basta trovare tutti gli $n$ tali che $n^2=1$ e $n=\ne1$. Si vede facilmente che questo insieme è $\{4,11,14\}$.

(3). Un tale $n$ esiste, basta prendere $n=1$. In questo caso infatti il grafo non ha lati e quindi non è isomorfo né a $H$ né a $K$.