Lezione 18 (15 maggio 2000 h. 9-11)

Alcune costruzioni con i grafi

Definizione di grafo 2-connessi

Prima caratterizzazione dei grafi 2-connessi

Seconda caratterizzazione dei grafi 2-connessi

Esercizio 18.1    Siano G=(V,E) e G'=(V'.e') due grafi. Si denoti con $G\cup G'$ il grafo tale che $V(G\cup G') = V\cup V'$ e $E(G\cup G')=E\cup E'$. Si provi che se G e G' sono connessi e $V\cap V'\ne\varnothing$ allora $G\cup G'$ è connesso.
Soluzione

Esercizio 18.2    Si provi che se G e G' sono 2-connessi e $\left\vert V\cap V'\right\vert\ge2$ allora $G\cup G'$ è 2-connesso.
Soluzione

Esercizio 18.3    Sia $k\ge1$, si dice che un grafo G=(V,E) è k-connesso se per ogni $v_1,\dots,v_{k-1}\in V$ si ha che $G-v_1-v_2-\dots-v_{k-1}$ è connesso. Si osservi che 1-connesso è sinonimo di connesso.

Si provi che G è k-connesso se e solo se per ogni $v\in V$ G-v è k-1-connesso.
Soluzione

Esercizio 18.4    Si determinino condizioni sufficienti affinché l'unione di due grafi k-connessi sia ancora k-connesso.
Soluzione

Esercizio 18.5    Per ogni $n\in\mathbb N$ sia G_n=(V_n,E_n) un grafo connesso e si supponga che $V_n\subseteq V_{n+1}$ per ogni n. Si provi che allora $G=\bigcup_{n\in\mathbb N} G_n$ è connesso.
Soluzione

Esercizio 18.6    Per ogni $n\in\mathbb N$ sia G_n=(V_n,E_n) un grafo connesso e si supponga che $V_n\cap V_{n+1}\ne\varnothing$ per ogni n. Si provi che allora $G=\bigcup_{n\in\mathbb N} G_n$ è connesso.
Soluzione

Esercizio 18.7    Per ogni $n\in\mathbb N$ sia G_n=(V_n,E_n) un grafo k-connesso e si supponga che $\left\vert V_n\cap V_{n+1}\right\vert\ge k$ per ogni n. Si provi che allora $G=\bigcup_{n\in\mathbb N} G_n$ è k-connesso.
Soluzione