Una componente conexa es un grupo maximal de vértices que pueden alcanzarse entre sí. Las componentes dividen un grafo desconectado en regiones independientes.
Cuando un grafo no es conexo, sus vértices quedan separados en grupos. Dentro de cada grupo existen caminos entre todos sus integrantes, pero no hay caminos hacia los vértices de otros grupos.
Estos grupos reciben el nombre de componentes conexas. Identificarlas permite dividir un problema grande en subproblemas independientes.
Una componente conexa es un subgrafo conexo maximal. La palabra maximal significa que no podemos agregarle otro vértice del grafo sin perder la conectividad.
Cada vértice pertenece exactamente a una componente conexa.
Podemos relacionar dos vértices cuando existe un camino entre ellos. Esta relación es reflexiva, simétrica y transitiva, por lo que divide el conjunto de vértices en clases de equivalencia.
| Propiedad | Interpretación |
|---|---|
| Reflexiva | Todo vértice se alcanza a sí mismo |
| Simétrica | Si u alcanza a v, v alcanza a u |
| Transitiva | Si u alcanza a v y v a w, u alcanza a w |
Un grafo conexo tiene una única componente. Un grafo sin aristas posee tantas componentes como vértices, porque cada nodo aislado forma una componente de tamaño uno.
Agregar una arista entre componentes diferentes las fusiona. Eliminar un puente puede separar una componente en dos o más.
Cada color representa una componente. Selecciona dos vértices para agregar o quitar una arista y observa cómo se fusionan o separan los grupos.
Componentes detectadas
Conecta un vértice de un color con otro de un color diferente: ambas componentes se convierten inmediatamente en una sola.
Una búsqueda DFS o BFS iniciada en un vértice visita exactamente todos los nodos de su componente.
No se alcanzarán otras componentes porque no existe ninguna arista que cruce entre ellas.
Para descubrirlas todas, recorremos los vértices. Cada vez que encontramos uno no visitado, iniciamos una nueva búsqueda y obtenemos otra componente.
Un vértice aislado forma por sí solo una componente conexa. Se denomina componente trivial porque contiene un único vértice y ninguna arista.
En la simulación, H comienza aislado y aparece como una componente independiente.
En dígrafos distinguimos componentes débilmente conexas y componentes fuertemente conexas. Las primeras ignoran la orientación; las segundas exigen caminos dirigidos en ambos sentidos.
| Tipo | Condición |
|---|---|
| Débilmente conexa | Conexa al ignorar las direcciones |
| Fuertemente conexa | Cada par se alcanza en ambos sentidos |
function componentesConexas(grafo) {
const visitados = new Set();
const componentes = [];
function dfs(vertice, componente) {
visitados.add(vertice);
componente.push(vertice);
for (const vecino of grafo[vertice]) {
if (!visitados.has(vecino)) dfs(vecino, componente);
}
}
for (const vertice of Object.keys(grafo)) {
if (!visitados.has(vertice)) {
const componente = [];
dfs(vertice, componente);
componentes.push(componente);
}
}
return componentes;
}Con listas de adyacencia, encontrar todas las componentes cuesta O(|V| + |E|): cada vértice y cada arista se procesa una cantidad constante de veces.
| Aplicación | Interpretación de las componentes |
|---|---|
| Red social | Comunidades sin vínculos externos |
| Red informática | Equipos que pueden comunicarse |
| Procesamiento de imágenes | Regiones de píxeles conectados |
| Mapas | Grupos de lugares con rutas internas |
Las componentes conexas dividen un grafo en sus regiones independientes. Esta partición facilita analizar redes desconectadas y procesar cada grupo por separado.
En el próximo tema estudiaremos árboles y bosques, estructuras acíclicas estrechamente relacionadas con la conectividad.