Um componente conectado é um subgráfico máximo conectado de um gráfico não direcionado. Cada vértice pertence exatamente a um componente conectado, assim como cada borda. Um gráfico é conectado se e somente se ele tiver exatamente um componente conectado.
Os componentes fortes são os subgrafos máximos fortemente conectados de um gráfico dirigido.
Um conjunto de vértices cortados ou separados de um gráfico conectado G é um conjunto de vértices cuja remoção torna G desconectado. A conectividade do vértice κ(G) (onde G não é um gráfico completo) é o tamanho de um corte mínimo do vértice. Um gráfico é chamado de k-vertex-conectado ou k-conectado se sua conectividade de vértices for k ou maior.
Mais precisamente, qualquer gráfico G (completo ou não) é dito como k-vertex-conectado se ele contiver pelo menos k+1 vértices, mas não contém um conjunto de k – 1 vértices cuja remoção desconecta o gráfico; e κ(G) é definido como o maior k de tal forma que G é k-conectado. Em particular, um gráfico completo com n vértices, denotado Kn, não tem nenhum corte de vértice, mas κ(Kn) = n – 1.
Um corte de vértice para dois vértices u e v é um conjunto de vértices cuja remoção do gráfico desconecta u e v. A conectividade local κ(u, v) é o tamanho de um corte de vértice menor separando u e v. A conectividade local é simétrica para gráficos não direcionados; ou seja, κ(u, v) = κ(v, u). Além disso, com exceção dos gráficos completos, κ(G) é igual ao mínimo de κ(u, v) sobre todos os pares de vértices não-adjacentes u, v.
2-conectividade também é chamada de biconectividade e 3-conectividade também é chamada de triconectividade. Um gráfico G que é conectado mas não 2-conectividade é às vezes chamado de separável.
Conceitos análogos podem ser definidos para bordas. No caso simples em que cortar uma única e específica aresta desconectaria o gráfico, essa aresta é chamada de ponte. Mais geralmente, um corte de aresta de G é um conjunto de arestas cuja remoção faz com que o gráfico seja desconectado. A conectividade de aresta λ(G) é o tamanho de um corte de aresta menor, e a conectividade de aresta local λ(u, v) de dois vértices u, v é o tamanho de um corte de aresta menor desconectando u de v. Novamente, a conectividade de aresta local é simétrica. Um gráfico é chamado de k-edge-connect se sua conectividade de borda for k ou maior.
Um gráfico é chamado de k-edge-connect se sua conectividade for igual ao seu grau mínimo. Diz-se que um gráfico é ligado ao máximo se a sua conectividade de borda for igual ao seu grau mínimo.
Super- e hiper-conectividadeEditar
Diz-se que um gráfico é super-conectado ou super-κ se cada corte de vértice mínimo isolar um vértice. Diz-se que um gráfico é hiper-conectado ou hiper-κ se a eliminação de cada corte mínimo de vértice cria exactamente dois componentes, um dos quais é um vértice isolado. Um gráfico é semiperligado ou semiper-κ se qualquer corte de vértice mínimo separar o gráfico em exatamente dois componentes.
Mais precisamente: um gráfico G conectado é dito ser super-conectado ou super-κ se todos os cortes de vértices mínimos consistem nos vértices adjacentes com um vértice (grau mínimo).Um gráfico de G conectado é dito ser super-conectado ou super-λ se todos os cortes mínimos de arestas consistem nos vértices adjacentes a algum vértice (grau mínimo).
Um cutset X de G é chamado de cutset não trivial se X não contiver a vizinhança N(u) de nenhum vértice u ∉ X. Então a superconectividade κ1 de G é:
κ1(G) = min{|X| : X é um cutset não trivial}.
Um corte de borda não trivial e a superconectividade de borda λ1(G) são definidos de forma análoga.
