Next: Lezione 20 (23 maggio
Up: Matematica Discreta
Previous: Lezione 18 (16 maggio
Subsections
Definizione 19.1
Sia
![$G=(V,E)$](img1121.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)$](img1385.gif)
, anche
![$G\%e$](img1386.gif)
è connesso.
Soluzione
Esercizio 19.2
Si provi che per ogni vertice
![$v$](img1132.gif)
si ha che
![$C_n-v\oldcong P_{n-1}$](img1387.gif)
.
Soluzione
Definizione 19.2
Sia
![$G$](img3.gif)
un grafo, diremo che
![$G$](img3.gif)
è
![$2$](img799.gif)
-connseeo se
![$\left\vert V(G)\right\vert\ge3$](img1388.gif)
e per
ogni
![$v\in V(G)$](img1284.gif)
si ha che
![$G-v$](img1389.gif)
è connesso.
Esercizio 19.3
Si provi che ogni grafo hamiltoniano è
![$2$](img799.gif)
-connesso.
Soluzione
Esercizio 19.4
Si provi che se
![$f:G\to G'$](img1201.gif)
è un isomorfismo, allora per ogni
![$v\in V(G)$](img1284.gif)
ed
![$e\in E(G)$](img1385.gif)
si ha che
![$G-v\oldcong G'-f(v)$](img1390.gif)
,
![$G-e\oldcong G'-f(e)$](img1391.gif)
,
![$G\%e\oldcong
G'\%f(e)$](img1392.gif)
.
Soluzione
Esercizio 19.5
Si provi che se
![$e\in E(C_n)$](img1393.gif)
allora
![$C_n\%e \oldcong C_{n+}1$](img1394.gif)
.
Soluzione
Esercizio 19.6
Si provi che se
![$e\in E(P_n)$](img1395.gif)
allora
![$P_n\%e \oldcong P_{n+1}$](img1396.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$](img799.gif)
-connesso
è connesso.
Teorema 19.5 (prima caratterizzazione dei grafi
![$2$](img799.gif)
-connessi)
Un grafo
![$G$](img3.gif)
è
![$2$](img799.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)$](img1305.gif)
esiste un ciclo
![$(v_0,v_1,\dots,v_n=v_0)$](img1410.gif)
in
![$G$](img3.gif)
che
passa per i vertci
![$v$](img1132.gif)
e
![$w$](img1160.gif)
.
Lemma 19.6
Sia
![$G$](img3.gif)
un grafo
![$2$](img799.gif)
-connesso allora per ogni
![$e\in E$](img1193.gif)
anche
![$G\%e$](img1386.gif)
è
![$2$](img799.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$](img799.gif)
-connesso allora per ogni
![$e\in {V \choose 2}\setminus E$](img1378.gif)
anche
![$G+e$](img1428.gif)
è
![$2$](img799.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$](img799.gif)
-connesso se e solo se è isomorfo ad un grafo
ottenuto a partire da
![$C_3$](img1431.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
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
![\begin{displaymath}
\left\vert E(H_0)\right\vert \ge \left\vert E(H)\right\vert\quad \forall H\in {\cal G}.
\end{displaymath}](img1435.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 6), ossia
,
e
per ogni
. Consideriamo il grafo
definito da:
Figura 6:
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}](img1453.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 7).
Figura 7:
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}](img1460.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)$](img1121.gif)
e
![$G'=(V'.e')$](img1466.gif)
due grafi. Si denoti con
![$G\cup G'$](img1467.gif)
il grafo
tale che
![$V(G\cup G') = V\cup V'$](img1468.gif)
e
![$E(G\cup G')=E\cup E'$](img1469.gif)
. Si provi che se
![$G$](img3.gif)
e
![$G'$](img1135.gif)
sono connessi e
![$V\cap V'\ne\varnothing $](img1470.gif)
allora
![$G\cup G'$](img1467.gif)
è connesso.
Soluzione
Esercizio 19.8
Si provi che se
![$G$](img3.gif)
e
![$G'$](img1135.gif)
sono 2-connessi e
![$\left\vert V\cap V'\right\vert\ge2$](img1471.gif)
allora
![$G\cup G'$](img1467.gif)
è 2-connesso.
Soluzione
Esercizio 19.9
Sia
![$k\ge
1$](img1472.gif)
, si dice che un grafo
![$G=(V,E)$](img1121.gif)
è
-connesso se per ogni
![$v_1,\dots,v_{k-1}\in V$](img1473.gif)
si ha che
![$G-v_1-v_2-\dots-v_{k-1}$](img1474.gif)
è connesso. Si
osservi che
![$1$](img493.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}$](img157.gif)
sia
![$G_n=(V_n,E_n)$](img1477.gif)
un grafo connesso e si supponga che
![$V_n\subseteq V_{n+1}$](img1478.gif)
per ogni
![$n$](img2.gif)
. Si provi che allora
![$G=\bigcup_{n\in\mathbb{N}} G_n$](img1479.gif)
è connesso.
Soluzione
Esercizio 19.12
Per ogni
![$n\in\mathbb{N}$](img157.gif)
sia
![$G_n=(V_n,E_n)$](img1477.gif)
un grafo connesso e si supponga che
![$V_n\cap V_{n+1}\ne\varnothing $](img1480.gif)
per ogni
![$n$](img2.gif)
. Si provi che allora
![$G=\bigcup_{n\in\mathbb{N}} G_n$](img1479.gif)
è connesso.
Soluzione
Esercizio 19.13
Per ogni
![$n\in\mathbb{N}$](img157.gif)
sia
![$G_n=(V_n,E_n)$](img1477.gif)
un grafo
![$k$](img1.gif)
-connesso e si supponga che
![$\left\vert V_n\cap V_{n+1}\right\vert\ge k$](img1481.gif)
per ogni
![$n$](img2.gif)
. Si provi che allora
![$G=\bigcup_{n\in\mathbb{N}} G_n$](img1479.gif)
è
![$k$](img1.gif)
-connesso.
Soluzione
Next: Lezione 20 (23 maggio
Up: Matematica Discreta
Previous: Lezione 18 (16 maggio
Luminati Domenico
2002-06-07