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

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

$\displaystyle 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}\}$.

    back.gif


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

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

e quindi il numero di band è dato da

$\displaystyle \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

$\displaystyle \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.
$

    back.gif


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:

$\displaystyle \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$.
\begin{figure}\begin{center}
\psfig{file=fig_a1_2_e3s_2003.eps,width=.6\hsize} \end{center}\end{figure}

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


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



next up previous
Next: About this document ... Up: Matematica Discreta (II modulo) Previous: Matematica Discreta (II modulo)
Domenico Luminati 2004-04-20