Next: Lezione 20
Up: Matematica Discreta (II modulo)
Previous: Lezione 18
Subsections
Definizione 19.1
Sia
![$ G=(V,E)$](img1205.gif)
un grafo, definiamo alcuni grafi costruiti a partire da
![$ G$](img3.gif)
:
- (cancellazione di un lato) se
denotiamo
- (aggiunta di un lato) se
denotiamo
- (cancellazione di un vertice) se
denotiamo
- (divisione di un lato) se
denotiamo
essendo
.
Esercizio 19.1
Si provi che se
![$ G$](img3.gif)
è connesso, allora per ogni
![$ e\in E(G)$](img1483.gif)
, anche
![$ G\%e$](img1484.gif)
è connesso.
Soluzione
Esercizio 19.2
Si provi che per ogni vertice
![$ v$](img1216.gif)
si ha che
![$ C_n-v\oldcong P_{n-1}$](img1485.gif)
.
Soluzione
Definizione 19.2
Sia
![$ G$](img3.gif)
un grafo, diremo che
![$ G$](img3.gif)
è
![$ 2$](img877.gif)
-connseeo se
![$ \left\vert V(G)\right\vert\ge3$](img1486.gif)
e per
ogni
![$ v\in V(G)$](img1383.gif)
si ha che
![$ G-v$](img1487.gif)
è connesso.
Esercizio 19.3
Si provi che ogni grafo hamiltoniano è
![$ 2$](img877.gif)
-connesso.
Soluzione
Esercizio 19.4
Si provi che se
![$ f:G\to G'$](img1299.gif)
è un isomorfismo, allora per ogni
![$ v\in V(G)$](img1383.gif)
ed
![$ e\in E(G)$](img1483.gif)
si ha che
![$ G-v\oldcong G'-f(v)$](img1488.gif)
,
![$ G-e\oldcong G'-f(e)$](img1489.gif)
,
![$ G\%e\oldcong
G'\%f(e)$](img1490.gif)
.
Soluzione
Esercizio 19.5
Si provi che se
![$ e\in E(C_n)$](img1491.gif)
allora
![$ C_n\%e \oldcong C_{n+}1$](img1492.gif)
.
Soluzione
Esercizio 19.6
Si provi che se
![$ e\in E(P_n)$](img1493.gif)
allora
![$ P_n\%e \oldcong P_{n+1}$](img1494.gif)
.
Soluzione
Dimostrazione.
Siano
. Dobbiamo provare che esiste una passeggiata tra
e
che
non contiene il lato
. Si hanno due casi
-
;
.
Nel primo caso, sia
un estremo di
diverso da
e
(i.e.
con
e
) allora
. Dato che
è
-connesso,
è connesso, e quindi esiste una passeggiata
in
che congiunge
e
. Dato che
,
quindi
questa passeggiata non contenere il lato
.
Nel secondo caso, sia
(esiste perché
). Dato che
è
-connesso esiste una passeggiata
tra
e
in
(chiaramente tale passeggiata non passa per
). Per lo
stesso motivo esiste una passeggiata tra
e
in
(anche questa
passeggiata non può contenere il lato
). Congiungendo queste due
passeggiate si ottiene una passeggiata che congiunge
e
e che non passa
per
.
Osservazione 19.4
Dalla proposizione precedente segue in particolare che ogni grafo
![$ 2$](img877.gif)
-connesso
è connesso.
Teorema 19.5 (prima caratterizzazione dei grafi
![$ 2$](img877.gif)
-connessi)
Un grafo
![$ G$](img3.gif)
è
![$ 2$](img877.gif)
-connesso se e solo se ogni coppia di vertici di
![$ G$](img3.gif)
è
contenuta in un ciclo. Ossia
per ogni
![$ v,w\in V(G)$](img1403.gif)
esiste un ciclo
![$ (v_0,v_1,\dots,v_n=v_0)$](img1508.gif)
in
![$ G$](img3.gif)
che
passa per i vertci
![$ v$](img1216.gif)
e
![$ w$](img1244.gif)
.
Lemma 19.6
Sia
![$ G$](img3.gif)
un grafo
![$ 2$](img877.gif)
-connesso allora per ogni
![$ e\in E$](img1291.gif)
anche
![$ G\%e$](img1484.gif)
è
![$ 2$](img877.gif)
-connesso.
Dimostrazione.
Sia
e
. Si hanno tre casi:
;
o
;
,
e
Nel primo caso,
, infatti dalle definizioni si ha
Pertanto
è connesso per la proposizione 19.3
Nel secondo caso, supponiamo che
(l'altro caso si ottiene per simmetria,
scambiando
e
). Osserviamo che
è un sottografo di
. Infatti
Ma allora dato che ogni
è
-connesso,
è connesso e quindi ogni
vertice di
è congiungibile in
, e quindi in
al vertice
. D'altra parte, l'unico altro vertice di
è
che è
congiungibile a
in
, dato che
. Tutti i
vertici sono quindi congiungibili tra loro.
Nel terzo caso
è connesso in quanto ottenuto dal grafo
connesso
suddividendo un suo lato (
è connesso).
Lemma 19.7
Sia
![$ G$](img3.gif)
un grafo
![$ 2$](img877.gif)
-connesso allora per ogni
![$ e\in {V \choose 2}\setminus E$](img1476.gif)
anche
![$ G+e$](img1540.gif)
è
![$ 2$](img877.gif)
-connesso.
Dimostrazione.
Segue dal fatto che per ogni vertice
il grafo
ha gli stessi vertici di
e contiene tutti i lati di
. Dato
che quest'ultimo è connesso, lo ànche
.
Teorema 19.8
Un grafo finito
![$ G$](img3.gif)
è
![$ 2$](img877.gif)
-connesso se e solo se è isomorfo ad un grafo
ottenuto a partire da
![$ C_3$](img1543.gif)
con una successione finita di suddivisioni di ed
aggiunzioni di lati.
Dimostrazione.
Dato che
è
-connesso, i due lemmi precedenti provano che ogni grafo ottenuto da
aggiungendo e suddividendo lati è
-connesso.
Proviamo l'implicazione opposta. Per semplicità diciamo che un grafo è
costruibile se è ottenuto da
con un numero finito di aggiunzioni
e suddivisioni di nodi. Consideriamo l'insieme
![$\displaystyle {\cal G}= \{H\mid H$](img1544.gif)
è sottografo costruibile di
usando l'esercizio 19.5, si prova che ogni ciclo è
costruibile, d'altra parte dal primo teorema di
caratterizzazione segue, in particolare, che
contiene dei cicli. Ma allora
. Sia allora
un grafo che massimizza il numero dei
lati (
è finito!), ossia tale che
![$\displaystyle \left\vert E(H_0)\right\vert \ge \left\vert E(H)\right\vert\quad \forall H\in {\cal G}.$](img1548.gif) |
(11) |
Proviamo che
da cui segue evidentemente la tesi.
. Supponiamo per assurdo che esista
.
è connesso, esiste quindi un cammino
che congiunge
ad un vertice di
. Sia
il primo vertice di questo cammino tale che
. Chiamiamo
e
(
dato che
), allora
,
e
.
Il grafo
è connesso e, dato che
ha almeno tre vertici,
esistono vertici di
diversi da
. Sia allora
un
cammino in
che congiunge
ad un vertice di
ed i cui altri
vertici sono tutti fuori di
(vedi figura 7), ossia
,
e
per ogni
. Consideriamo il grafo
definito da:
Figura 7:
Come costruire un cammino che ha solo due punti in comune con
![\begin{figure}\begin{center}
\psfig{file=2conn.eps,width=.3\hsize} \end{center}\end{figure}](img1566.gif) |
Chiaramente
è un sottografo di
e
. Se
proviamo che
è ottenuto da
con un numero finito di suddivisioni e
di aggiunzioni di lati si ha che
e quindi un assurdo. Ma ora si
hanno due casi:
-
-
Nel primo caso
è ottenuto suddividendo
volte il lato
e
quindi aggiungendo di nuovo il lato
, nel secondo caso
è
ottenuto aggiungendo il lato
e quindi dividendolo
volte (vedi
figura 8).
Figura 8:
Il grafo
è ottenuto da
o aggiungendo un lato e quindi
suddividendolo oppure suddividendo un lato già esistente e quindi
riaggiungendolo.
![\begin{figure}\begin{center}
\psfig{file=2conn2.eps,width=.98\hsize} \end{center}\end{figure}](img1576.gif) |
. Supponiamo per assurdo che
, allora,
visto che per il punto precedente
, necessariamente
, si può allora costruire il grafo
che
è un sottografo di
. D'altra parte
è ottenuto da
aggiungendo
un lato, quindi è costruibile, ovvero
. Ma
, che contraddice la (11).
Esercizio 19.7
Siano
![$ G=(V,E)$](img1205.gif)
e
![$ G'=(V'.e')$](img1582.gif)
due grafi. Si denoti con
![$ G\cup G'$](img1583.gif)
il grafo
tale che
![$ V(G\cup G') = V\cup V'$](img1584.gif)
e
![$ E(G\cup G')=E\cup E'$](img1585.gif)
. Si provi che se
![$ G$](img3.gif)
e
![$ G'$](img1219.gif)
sono connessi e
![$ V\cap V'\ne\varnothing $](img1586.gif)
allora
![$ G\cup G'$](img1583.gif)
è connesso.
Soluzione
Esercizio 19.8
Si provi che se
![$ G$](img3.gif)
e
![$ G'$](img1219.gif)
sono 2-connessi e
![$ \left\vert V\cap V'\right\vert\ge2$](img1587.gif)
allora
![$ G\cup G'$](img1583.gif)
è 2-connesso.
Soluzione
Esercizio 19.9
Sia
![$ k\ge1$](img1588.gif)
, si dice che un grafo
![$ G=(V,E)$](img1205.gif)
è
-connesso se per ogni
![$ v_1,\dots,v_{k-1}\in V$](img1589.gif)
si ha che
![$ G-v_1-v_2-\dots-v_{k-1}$](img1590.gif)
è connesso. Si
osservi che
![$ 1$](img567.gif)
-connesso è sinonimo di connesso.
Si provi che
è
se e solo se per ogni
è
-connesso.
Soluzione
Esercizio 19.10
Si determinino condizioni sufficienti affinché l'unione di due grafi
![$ k$](img1.gif)
-connessi sia ancora
![$ k$](img1.gif)
-connesso.
Soluzione
Esercizio 19.11
Per ogni
![$ n\in \mathbb{N}$](img214.gif)
sia
![$ G_n=(V_n,E_n)$](img1593.gif)
un grafo connesso e si supponga che
![$ V_n\subseteq V_{n+1}$](img1594.gif)
per ogni
![$ n$](img2.gif)
. Si provi che allora
![$ G=\bigcup_{n\in\mathbb{N}}
G_n$](img1595.gif)
è connesso.
Soluzione
Esercizio 19.12
Per ogni
![$ n\in \mathbb{N}$](img214.gif)
sia
![$ G_n=(V_n,E_n)$](img1593.gif)
un grafo connesso e si supponga che
![$ V_n\cap V_{n+1}\ne\varnothing $](img1596.gif)
per ogni
![$ n$](img2.gif)
. Si provi che allora
![$ G=\bigcup_{n\in\mathbb{N}}
G_n$](img1595.gif)
è connesso.
Soluzione
Esercizio 19.13
Per ogni
![$ n\in \mathbb{N}$](img214.gif)
sia
![$ G_n=(V_n,E_n)$](img1593.gif)
un grafo
![$ k$](img1.gif)
-connesso e si supponga che
![$ \left\vert V_n\cap V_{n+1}\right\vert\ge k$](img1597.gif)
per ogni
![$ n$](img2.gif)
. Si provi che allora
![$ G=\bigcup_{n\in\mathbb{N}}
G_n$](img1595.gif)
è
![$ k$](img1.gif)
-connesso.
Soluzione
Next: Lezione 20
Up: Matematica Discreta (II modulo)
Previous: Lezione 18
Domenico Luminati
2004-03-18