La conectividad estudia si los vértices pueden alcanzarse mediante caminos. Una sola arista puede unir regiones enteras o provocar que una red se divida al desaparecer.
En una red no basta con conocer las conexiones directas. También interesa saber si podemos llegar de un vértice a otro utilizando una secuencia de aristas.
La conectividad describe esta posibilidad. Es fundamental para analizar redes de comunicación, rutas, dependencias y cualquier sistema que deba continuar funcionando aunque algunas conexiones fallen.
Dos vértices u y v están conectados si existe al menos un camino entre ellos.
No es necesario que compartan una arista directa. Pueden estar unidos mediante numerosos vértices intermedios.
Un grafo no dirigido es conexo cuando cada par de vértices está conectado por algún camino.
Si existe al menos un par sin camino, el grafo es desconectado.
Un grafo desconectado queda dividido en grupos de vértices que no pueden alcanzarse entre sí.
| Situación | Estado | Ejemplo |
|---|---|---|
| Todos los nodos se alcanzan | Conexo | Red operativa |
| Existen grupos separados | Desconectado | Red partida por una falla |
| Un nodo tiene grado 0 | Desconectado, salvo grafo de un nodo | Equipo aislado |
En modo Explorar, pulsa un nodo para resaltar todo lo alcanzable desde él. En modo Editar, selecciona dos vértices para agregar o quitar una arista.
Pulsa Cortar puente D—E: la red se divide en dos grupos. Luego entra en modo Editar y vuelve a conectar cualquier nodo de la izquierda con uno de la derecha.
El conjunto de vértices alcanzables desde un origen puede obtenerse mediante DFS o BFS. Si la búsqueda visita todos los vértices, el grafo no dirigido es conexo.
Una sola búsqueda es suficiente porque la relación de alcanzabilidad es simétrica en grafos no dirigidos.
Un puente es una arista cuya eliminación aumenta la cantidad de grupos desconectados del grafo.
En la simulación, D—E es el único enlace entre dos zonas. Su falla separa la red, por lo que constituye un puente.
Un vértice de articulación es un nodo cuya eliminación, junto con sus aristas, desconecta más el grafo.
| Elemento crítico | Se elimina | Efecto |
|---|---|---|
| Puente | Una arista | Aumenta los grupos separados |
| Vértice de articulación | Un vértice y sus aristas | Aumenta los grupos separados |
En dígrafos la dirección introduce varias nociones. Un grafo es fuertemente conexo si cada vértice alcanza a todos los demás respetando los arcos. Es débilmente conexo si se vuelve conexo al ignorar las direcciones.
function alcanzables(grafo, origen) {
const visitados = new Set([origen]);
const cola = [origen];
while (cola.length) {
const actual = cola.shift();
for (const vecino of grafo[actual]) {
if (!visitados.has(vecino)) {
visitados.add(vecino);
cola.push(vecino);
}
}
}
return visitados;
}
const grafo = { A: ["B"], B: ["A", "C"], C: ["B"] };
console.log(alcanzables(grafo, "A").size === Object.keys(grafo).length);Además de marcar vértices, podemos guardar el predecesor con el que descubrimos cada nodo para reconstruir un camino.
function existeCamino(grafo, origen, destino) {
const pendientes = [origen];
const visitados = new Set([origen]);
while (pendientes.length) {
const actual = pendientes.shift();
if (actual === destino) return true;
for (const vecino of grafo[actual]) {
if (!visitados.has(vecino)) {
visitados.add(vecino);
pendientes.push(vecino);
}
}
}
return false;
}La conectividad permite determinar si una red funciona como un único sistema o está dividida en regiones aisladas. También ayuda a encontrar conexiones y nodos cuya falla puede fragmentarla.
En el próximo tema formalizaremos estos grupos mediante el concepto de componentes conexas.