Componentes de $G$
Definição: Componentes
Seja $G = (V,A)$ um grafo. Um subgrafo maximal conexo de $G$ é um componente de $G$. Claramente, os componentes são subgrafos induzidos e seus conjuntos de vértices consistem em partições de $V$.
O grafo vazio não tem componentes, uma vez que os grafos conexos não são vazios.
Definição: Separação de Conjuntos e Vértices
Seja ainda $G=(V,A)$. Se $A,B \subseteq V$ e $X \subseteq V \cup A$ são tais que todo caminho $A-B$ em $G$ contém um vértice ou uma aresta de $X$, dizemos então que $X$ separa os conjuntos $A$ e $B$ em $G$. Observe que isso implica que $A \cap B \subseteq X$.
Dizemos que $X$ separa dois vértices $a,b$ se separar os conjuntos $\{a\},\{b\}$, sendo $a,b \notin X$, e que $X$ separa $G$ se $X$ separa dois vértices quaisquer em $G$.
Um conjunto que separa vértices é chamado de Conjunto separador.
Um vértice que separa dois outros vértices do mesmo componente é um “vértice separador”, e uma aresta que separa suas extremidades é uma ponte.Assim, as pontes em um grafo são precisamente aquelas arestas que não estão em nenhum ciclo.
Peguemos dois exemplos para exemplificar:
Podemos ver no grafo representado na imagem acima, que os vértices $v,x,y,w$ são os chamados “vértices deparadores” e que há uma ponte, representada pela letra $e$, constituída pelos vertices $x$ e $y$.
Definição: Separação
O par não ordenado $\{A,B\}$ é uma separação de $G$ se $A \cup B = V$ e $G$ não tem arestas entre $A \setminus B$ e $B \setminus A$. Claramente, o último é equivalente a dizer que $A \cap B$ separa $A$ de $B$.
Se ambos $A \setminus B$ e $B \setminus A$ são não vazios, dizemos que a separação é adequada. O número $|A \cap B|$ é a ordem da separação $\{A,B\}$, e os conjuntos A, B são seus lados.
$k$-conexidade
Definição
Um grafo $G=(V,A)$ é dito $k$-conexo (para $k \in \mathbb{N}$) se $|V| > k$ e $G-X$ é conexo para qualquer conjunto $X \subseteq V$ com $|X| < k $. Em outras palavras, não há dois vértices de $G$ separados por menos de $k$ outros vértices.
Todo grafo não vazio é $0$-conexo, e os grafos $1$-conexos são precisamente os grafos conexos não triviais. O maior inteiro $k$ tal que $G$ é $k$-conexo é a conectividade $\kappa (G)$ de $G$. Portanto, $\kappa (G) = 0$ se, e somente se, $G$ é desconexo ou se $G = K^1$, e $\kappa (K^n) = n-1$ para todo $n \geq 1$, onde $K^n$ é um grafo completo.
$\ell$-aresta-conexidade
Definição
Um grafo $G = (V, A)$ é dito $\ell$-aresta-conexo ($\ell \in \mathbb{N}$) se $|V|>1$ e $G - F$ é conexo para todo conjunto $F\subset A$ com $|F|<\ell$.
O maior inteiro $\ell$ para o qual $G$ é $\ell$-aresta-conexo é a aresta-conectividade de $G$, denotada por $\lambda(G)$. Em particular, temos que $\lambda(G) = 0 $ se $G$ é desconexo.
Tomando como exemplo o octaedro $G$ e o grafo $H$ abaixo:
temos $k(G)=\lambda(G)=4$, e o grafo $H$, a figura à direita, com $k(H)=2$, mas $\lambda(H)=4$., respectivmente.
Se um grafo é $k$-conexo (resp. $\ell$-aresta-conexo), então remover $k$ vértices (resp. $\ell$ arestas) não o tornará desconexo.
Referências
- Reinhard Diestel. “Graph Theory” .5th Electronic Edition 2016, pp. 10–12. Acesso em 19/01/2023.