9 Conexión

Vocabulario:

componentes conexas

conjunto de subgrafos conexos y maximales

Notaciones:

$d(v,w)$	distancia entre dos vértices siendo la longitud del camino más corto entre $v$ y $w$
$d_G(v,w)$	distancia entre $v$ y $w$ en $G$

La distancia define una métrica, es decir,

1. $d(v,w)\geq 0$
2. $d(v,w)=0 \Longleftrightarrow v=w$
3. $d(v,w)=d(w,v)$
4. $d(u,w)\leq d(u,v)+d(v,w)$

Vocabulario:

conexo	$v$ y $w$ son conexos, si $d(v,w)<\infty$;
	$G$ es conexo, si todas las parejas $v,w\in V$ son conexas
disconexo	$G$ es disconexo si no es conexo
puente	arista $e\in G$ es una puente, $G$ conexo, tal que $G\setminus e$ es disconexo
vértice de corte	vértice $v\in G$, $G$ conexo, tal que $G\setminus v$ es disconexo

Notaciones:

$c(G)$	número de componentes conexas de $G$
$\kappa(G)$	cardinalidad mínima de un subconjunto de vértices de $G$
	tal que $G\setminus V$ sea disconexo
$\lambda(G)$	cardinalidad mínima de un subconjunto de aristas de $G$
	tal que $G\setminus E$ sea disconexo

Vocabulario:

$k$-conexo	$G$ es $k$-conexo, si $\kappa(G)\geq k$
biconexo	2-conexo
$k$-aristoconexo	$G$ es $k$-aristoconexo, si $\lambda(G) \geq k$
bloque	subgrafo máximo biconexo