Soluzioni proposte

Soluzione dell'esercizio 1  $(35,25)=5\mathrel{\big\vert}25 = 22-(-3)$ quindi il sistema è risolubile. Usando l'algoritmo di Euclide, si ottiene $5 = 3 \cdot 25 + (-2) \cdot 35$ quindi

$$22-(-3)= 25 = 5 \cdot 5= 5(3 \cdot 25 + (-2) \cdot 35 )=15\cdot 25 - 10 \cdot 35$$

pertanto $x_0= 22 - 15 \cdot 25 = -3 -10 \cdot 35 = -353$ è una soluzione del sistema. L'insieme delle soluzioni è allora dato da $\{ -353 + k [25,35] \mid k\in\mathbb{Z}\}=\{ -353 + k 175 \mid k\in\mathbb{Z}\} = \{ 172 + k 175 \mid k\in\mathbb{Z}\}$.

    

Soluzione dell'esercizio 2 (1). Indichiamo con rispettivamente con $S$, $T$, $P$, $C$ gli insiemi dei sassoffonisti, trombettisti, percussionisti e chitarristi che si presentano alla selezione. Si ha $\left\vert S\right\vert=8$, $\left\vert T\right\vert=7$, $\left\vert P\right\vert=5$, $\left\vert(\right\vert C)=3$. Da ciascuno di questi insiemi devono essere scelti rispettivamente, 5, 3, 2, 2 elementi, quindi l'insieme $\mathcal{B}$ delle possibili band è in bigezione con l'insieme

$${S \choose 5} \times {T \choose 3} \times {P \choose 2} \times {C \choose 2}$$

e quindi il numero di band è dato da

$$\begin{array}{rcl} \left\vert\mathcal{B}\right\vert &=& \displays... ...hoose 2} \cdot {3 \choose 2} = 56 \cdot 35 \cdot 10 \cdot 3 = 58800 \end{array}$$

(2). Il numero di possibili scelte della cantante è evidentemente $4$, e quindi il numero delle [possibili band viene moltiplicato per 4, e diventa 235200.

(3). Detti ora $S$, $C$, $P$ gli insiemi dei sassofonisti, dei chitarristi e dei percussionisti della band, l'insieme $\mathcal{T}$ dei possibili trii è allora in bigezione con l'insieme $S\times C\times P$ e quindi ha cardinalità pari a

$$\left\vert\mathcal{T}\right\vert = \left\vert S\times C\times P\r... ...t\left\vert C\right\vert\cdot\left\vert P\right\vert = 5 \cdot 2 \cdot 2 = 20.$$

    

Soluzione dell'esercizio 3 Un grafo $G$ tale che $\mathop{\rm score}\nolimits (G)=d_1$ dovrebbe avere $8$ vertici, di cui due di grado $7$, ossia adiacenti a tutti gli altri. Ma allora ogni vertice dovrebbe avere grado almeno $2$. Questo cotraddice il fatto che dovrebbero esserci anche due vertici di grado $1$.

Per $d_2$ usiamo il teorema dello score:

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

Dato che $d_2'''$ è realizzabile come score di un grafo, anche $d_2$ 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$, e dai lati $\{2,3\},\{7,8\}$ che realizzano lo score $d_2'''$ a cui sono successivamente aggiunti i vertici $9$, $10$ e $11$ ottenendo dei grafi, che realizzano, nell'ordine, gli score $d_2''$, $d_2'$ e $d_2$.

(1). La risposta è no. Se $G=(V,E)$ è un grafo tale che $\mathop{\rm score}\nolimits (G)=d_2$ allora $\left\vert V\right\vert=11$ e $\left\vert E\right\vert=\frac{1}{2}\sum\limits_{v\in V} \deg{v}=\frac{1}{2}(1+ 1+ 2+ 3+ 3+ 3+ 3+ 4+ 6+ 7+ 9)=21$. Ma allora $\left\vert E\right\vert=21\ne 10 =\left\vert V\right\vert-1$, quindi $G$ non può essere un albero.

(2). La risposta è sì. Basta prendere il grafo che si è costruito in precedenza. In realtà si può mostrare che ogni tale grafo è necessariamente connesso, dato che ha $11$ vertici, un vertice di grado $9$ e quindi adiacente ad ogni altro vertice tranne uno, e quest'ultimo vertice avendo grado positivo, sarà necessariamente adiacente ad uno dei precedenti.

(3). La risposta è no. Se $G=(V,E)$ è un grafo tale che $\mathop{\rm score}\nolimits (G)=d_2$ allora ha un vertice di grado $1$, quindi non può essere $2$-connesso.     

Soluzione dell'esercizio 4 Tutti i grafi hanno un unico vertice di grado massimo (in tutti e tre i casi è il vertice $J$), $9$ e quindi sono isomorfi se e solo se lo sono privati di questo vertice. Questo perchè se $V$ ha grado massimo in $G$ allora $G$ è ottenuto da $G-v$ aggiungendo un vertice collegato con tutti gli altri ;lati.

Ma ora $G_1-J$ è costituito dall'unione disgiunta di tre copie di $C_3$ (ha quindi 3 componenti connesse), mentre $G_2-J$ e $G_3-J$ sono entrambi costituiti dall'unione disgiunta di un $C_4$ e un $C_5$ (in particolare hanno due componenti connesse). Quindi $G_2 \oldcong G_3$, mentre $G_1\not\oldcong G_2$ e $G_1\not\oldcong G_3$. Un isomorfismo $G_2\to G_3$ è dato ad esempio da: $A\to I$, $B\to C$, $C\to B$, $D\to D$, $E\to E$, $F\to F$, $G\to G$, $H\to H$ $I\to A$ e $J\to J$.