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

Soluzioni proposte

Soluzione dell'esercizio 1  $ (156,108)=12\mathrel{\big\vert}-12 = 8-20$ quindi il sistema è risolubile. Inoltre, usando l'algoritmo di Euclide, si ottiene $ 12 = (-2) \cdot 156 + (3)
\cdot 108$ quindi

$\displaystyle 8-20 = -12 = -((-2) \cdot 156 + (3)
\cdot 108) = 2\cdot 156 - 3 \cdot 108
$

e pertanto $ x_0= 332= 8+3\cdot 108 = 20 + 2\cdot 156$ è una soluzione del sistema.

L'insieme delle soluzioni è allora dato da $ \{ 332 + k [156,108] \mid
k\in\mathbb{Z}\}=\{ 332 + k 1404 \mid k\in\mathbb{Z}\}$     back.gif


Soluzione dell'esercizio 2 (1). Se $ \left\vert X\right\vert=k$ e $ \left\vert Y\right\vert=n$ allora l'insieme delle funzioni iniettive da $ X$ in $ Y$ ha cardinalità $ {n \choose k}k!=\frac{n!}{(n-k)!}$. Nel nostro caso $ n=8$, $ k=6$, quindi

$\displaystyle \left\vert\{f\in Y^X\mid f \text{ \\lq e
iniettiva}\}\right\vert=\frac{8!}{(8-6)!}=8\cdot7\cdot6\cdot5\cdot4\cdot3=20160.
$

(2). Se consideriamo $ X'=X\setminus\{1\}$ e $ Y'=Y\setminus\{4\}$ alora l'insieme $ \{f\in Y^X\mid f$    è iniettiva e $ f(1)=4\}$ può essere messo in bigezione con l'insieme $ \{f\in {Y'}^{X'}\mid f$    è iniettiva$ \}$ mediante la restrizione. Ma allora, applicando la stessaa formula del punto precedente, si ottiene che la cardinalità cercate è pari a

$\displaystyle \left\vert\{f\in Y^X\mid f \text{ \\lq e iniettiva e }f(1)=4\}\right...
...\\lq e iniettiva}\}\right\vert=
\frac{7!}{(7-5)!}=7\cdot6\cdot5\cdot4\cdot3=2520.
$

(3). Dato che $ f$ è iniettiva, $ \left\vert f^{-1}(\{0,1\})\right\vert\le\left\vert\{0,1\}\right\vert=2$. D'altra parte, dato che $ \left\vert Y\setminus\{0,1\}\right\vert = 6 \ge \left\vert X\right\vert \ge 2 =\left\vert\{0,1\}\right\vert$, possono essere assunti tutti i tre valori $ 0,1,2,3$. Costruiamo degli esempi:

$\displaystyle f_i$ $\displaystyle :$ $\displaystyle X \longrightarrow Y \qquad\qquad i=0,1,2$  
$\displaystyle f_0$ $\displaystyle :$ $\displaystyle x \longrightarrow x+1$  
$\displaystyle f_1$ $\displaystyle :$ $\displaystyle x \longrightarrow x$  
$\displaystyle f_2$ $\displaystyle :$ $\displaystyle x \longrightarrow x-1$  

Si verifica immediatamente che per ogni $ i=0,1,2$ si ha che $ \left\vert f_i^{-1}(\{0,1\})\right\vert=i$.     back.gif


Soluzione dell'esercizio 3 Un grafo $ G$ tale che $ \mathop{\rm score}\nolimits (G)=d_2$ dovrebbe avere $ 9$ vertici, due vertici, chiamiamoli $ u$ e $ v$, di grado $ 8$, ossia adiacenti a tutti gli altri. Ma allora ogni vertice diverso da $ u$ e $ v$ questi due deve essere adiacente almeno ad uno di loro e quindi avere grado almeno $ 2$. Ma se $ \mathop{\rm score}\nolimits (G)=d_2$ esiste almeno un vertce di grado $ 1$, che è in contraddizione con quanto appena provato. Quindi un tale $ G$ non può esistere.

Per $ d_1$ usiamo il teorema dello score:

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

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

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$, e dai lati $ \{7,8\},\{8,9\},\{9,10\}$ che realizzano lo score $ d_1''$ a cui sono successivamente aggiunti i vertici $ 11,12$ ottenendo dei grafi, che realizzano, nell'ordine, gli score $ d_1'$ e $ d_1$.
\begin{figure}\begin{center}
\psfig{file=fig_a1_1_e31_2001.eps,width=6cm} \end{center}\end{figure}

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

(2). La risposta è no. Se $ G=(V,E)$ è un grafo tale che $ \mathop{\rm score}\nolimits (G)=d_1$ allora esiste $ v\in V$ tale che $ \deg(V)=11$, ossia ogni altro vertice è adiacente e quindi congiungibile con $ v$. Ne consegue che $ G$ è connesso.

(3). Che il grafo di figura [*] sia $ 2$-connesso lo si può vedere mostrando che è ottenuto da un ciclo con successive aggiunzioni e suddivisioni di lati (cfr. figura).

Figura: Il grafo di figura [*] è ottenuto da un ciclo mediante aggiunzione e suddivisione di lati, quindi è $ 2$-connesso
\begin{figure}\begin{center}
\psfig{file=fig_a1_1_e32_2001.eps,width=.95\hsize} \end{center}\end{figure}

Un altro modo di provare la $ 2$-connessione di questo grafo è il seguente. Sia $ G$ il grafo e sia$ w$ il vertice di grado $ 11$. Chiaramente, per ogni $ v\ne w$ si ha che $ G-v$ ha un vertice di grado $ 10$ (e $ 11$ vertici) e quindi è connesso. D'altra parte $ G$ ha anche un vertice $ u$ di grado $ 10$ e quindi $ u$ ha grado $ 9$ in $ G-w$ (è adiacente a tutti i suoi vertici tranne uno) e dato che ogni vertice di $ G$ ha grado almeno $ 2$, ogni vertice di $ G-w$ ha grado almeno $ 1$. Ma allora l'unico vertice $ v$ di $ G-w$ non adiacente a $ u$ sarà adiacente almeno ad un altro vertice $ t$ e quindi $ P=(u,t,v)$ è un cammino tra $ u$ e $ v$ in $ G-w$. Ne consegue che tutti i vertici di $ g-w$ sono congiungibili a $ u$ e quindi anche $ G-w$ è connesso. Questo ragionamento prova in realtà che ogni grafo tale che $ \mathop{\rm score}\nolimits (G)=d_1$ è $ 2$-connesso.     back.gif


Soluzione dell'esercizio 4 Il primo grafo non è $ 2$-connesso, infatti se a questo grafo si toglie il vertice $ G$ si ottengono i due cicli disgiunti $ (A,B,F,A)$ e $ (C,D,E,C)$, mentre il secondo grafo è hamiltoniano (e quindi quindi è $ 2$-connesso) in quanto c'è il ciclo $ (a,b,e,f,g,c,d,a)$.

Di conseguenza il primo ed il secondo grafo non sono isomorfi.

Il secondo e il terzo grafo sono isomorfi (conseguentemente il primo e il terzo non lo sono). Un isomorfismo è dato ad esempio dalla funzione $ f$ definita da:

$\displaystyle \begin{array}{rclcrcl}
a &\mapsto &\chi &\hbox{\kern1cm}& e &\map...
...apsto &\epsilon && g &\mapsto &\varphi \\
d &\mapsto &\delta \\
\end{array}$

Che tale funzione sia un isomorfismo segue da una semplice verifica. L'insieme dei lati del secondo grafo è dato da

$\displaystyle \big\{
\{b,a\}, \{a,d\}, \{d,c\}, \{c,b\}, \{g,c\}, \{a,e\}, \{b,g\},
\{g,f\}, \{f,e\}, \{e,b\}
\big\}
$

i cui trasformati tramite $ f$ sono

$\displaystyle \big\{
\{\gamma,\chi\}, \{\chi,\delta\}, \{\delta,\epsilon\}, \{\...
...mma,\varphi \},
\{\varphi ,\alpha\}, \{\alpha,\beta\}, \{\beta,\gamma\}
\big\}
$

che sono proprio tutti e soli i lati del terzo grafo.     back.gif



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