==== 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 [[.defsubinduc |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 [[.defCaminho|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 [[.separar|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 | 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:
{{ :grafos:screenshot_from_2023-01-20_12-29-07.png?500 |}}
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 [[.defKConexo|$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 [[.defCompleto|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:
{{ :grafos:l-aresta.png?450 |}}
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.
----
=== Leia também ===
* [[.cicloDeltaKConexidade|Uma relação de $k$-conexidade,$\ell$-aresta-conexidade e grau mínimo]].
=== Referências ===
* Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 10–12. Acesso em 19/01/2023.