Un componente conectado es un subgrafo conectado máximo de un grafo no dirigido. Cada vértice pertenece exactamente a un componente conexo, al igual que cada arista. Un grafo es conexo si y sólo si tiene exactamente una componente conexa.
Las componentes fuertes son los subgrafos fuertemente conectados máximos de un grafo dirigido.
Un corte de vértices o conjunto separador de un grafo conectado G es un conjunto de vértices cuya eliminación hace que G quede desconectado. La conectividad de vértices κ(G) (donde G no es un grafo completo) es el tamaño de un corte de vértices mínimo. Un grafo se llama k-conectado o k-conectado si su conectividad de vértices es k o mayor.
Más precisamente, se dice que cualquier grafo G (completo o no) está k-conectado si contiene al menos k+1 vértices, pero no contiene un conjunto de k – 1 vértices cuya eliminación desconecta el grafo; y κ(G) se define como el mayor k tal que G está k-conectado. En particular, un gráfico completo con n vértices, denotado Kn, no tiene ningún corte de vértices, pero κ(Kn) = n – 1.
Un corte de vértice para dos vértices u y v es un conjunto de vértices cuya eliminación del grafo desconecta a u y v. La conectividad local κ(u, v) es el tamaño de un corte de vértice más pequeño que separa a u y v. La conectividad local es simétrica para grafos no dirigidos; es decir, κ(u, v) = κ(v, u). Además, excepto para los grafos completos, κ(G) es igual al mínimo de κ(u, v) sobre todos los pares no adyacentes de vértices u, v.
La conectividad 2 también se llama biconexión y la conectividad 3 también se llama triconexión. Un gráfico G que es conectado pero no 2-conectado se llama a veces separable.
Conceptos análogos se pueden definir para las aristas. En el caso simple en el que cortar una sola arista específica desconectaría el grafo, esa arista se llama puente. De forma más general, una arista cortada de G es un conjunto de aristas cuya eliminación hace que el gráfico se desconecte. La conectividad de aristas λ(G) es el tamaño de un corte de aristas más pequeño, y la conectividad local de aristas λ(u, v) de dos vértices u, v es el tamaño de un corte de aristas más pequeño que desconecte u de v. De nuevo, la conectividad local de aristas es simétrica. Un grafo se llama k-conectado si su conectividad de aristas es k o mayor.
Se dice que un grafo está maximamente conectado si su conectividad es igual a su grado mínimo. Se dice que un grafo está maximalmente conectado por aristas si su conectividad por aristas es igual a su grado mínimo.
Superconectividad e hiperconectividadEditar
Se dice que un grafo está superconectado o super-κ si cada corte de vértice mínimo aísla un vértice. Se dice que un grafo es hiperconectado o hiper-κ si la eliminación de cada corte de vértice mínimo crea exactamente dos componentes, uno de los cuales es un vértice aislado. Un grafo es semi-hiper-conectado o semi-κ si cualquier corte de vértice mínimo separa el grafo en exactamente dos componentes.
Más precisamente: se dice que un grafo conectado G es super-conectado o super-κ si todos los cortes de vértice mínimos consisten en los vértices adyacentes con un vértice (de grado mínimo).Se dice que un grafo conectado G está superconectado o super-λ si todos los cortes de arista mínimos consisten en las aristas incidentes en algún vértice (de grado mínimo).
Un conjunto de cortes X de G se llama conjunto de cortes no triviales si X no contiene la vecindad N(u) de ningún vértice u ∉ X. Entonces la superconectividad κ1 de G es:
κ1(G) = min{|X| : X es un conjunto de cortes no triviales}.
Un corte no trivial de aristas y la superconectividad de aristas λ1(G) se definen de forma análoga.
