4. Grafos dirigidos y no dirigidos

4.1 Introducción

Al modelar un sistema debemos preguntar si cada relación es simétrica. Una carretera de doble mano permite viajar en ambos sentidos, mientras que una calle de sentido único solo permite avanzar en una dirección.

Los grafos no dirigidos representan relaciones sin sentido definido. Los grafos dirigidos, también llamados dígrafos, representan relaciones que parten de un vértice y llegan a otro.

4.2 Grafos no dirigidos

En un grafo no dirigido, una arista conecta dos vértices de manera simétrica. Si A está conectado con B, entonces B también está conectado con A.

Las aristas suelen escribirse como conjuntos sin orden y se dibujan mediante líneas. Amistades recíprocas, enlaces físicos y rutas de doble sentido son ejemplos habituales.

4.3 Grafos dirigidos

En un grafo dirigido, cada arista tiene un origen y un destino. Se denomina arco y se representa visualmente con una flecha.

El arco (A, B) permite avanzar desde A hacia B, pero no afirma que exista una conexión desde B hacia A. Para representar ambos sentidos necesitamos dos arcos.

4.4 Comparación fundamental

4.5 Simulación interactiva: cambia la dirección

Alterna el tipo de grafo y observa las aristas. Luego selecciona dos vértices: en modo dirigido, el orden de selección define el origen y el destino.

En el modo no dirigido, A—B representa una relación recíproca. En el modo dirigido, A→B y B→A son arcos diferentes. Selecciona un nodo para comparar su grado total con sus grados de entrada y salida.

4.6 Origen y destino

En un arco dirigido (A, B), A es el origen y B es el destino. Esta distinción permite representar flujo, causalidad, dependencia o permiso de movimiento.

• En una red social, A puede seguir a B sin que B siga a A.
• En un sitio web, una página puede enlazar a otra que no contiene un enlace de regreso.
• En un proyecto, la tarea B puede depender de A.
• En una calle, se puede permitir el recorrido desde A hacia B solamente.

4.7 Grado en grafos no dirigidos

En un grafo no dirigido, el grado de un vértice es la cantidad de aristas que inciden en él. Cada arista contribuye al grado de sus dos extremos.

En la simulación, utiliza el modo sin dirección y selecciona un nodo. El panel muestra su grado y sus vecinos.

4.8 Grados de entrada y salida

En un grafo dirigido se distinguen dos valores. El grado de entrada cuenta los arcos que llegan al vértice y el grado de salida cuenta los que parten de él.

Por ejemplo, en una red social estos números pueden indicar cuántas personas siguen a un usuario y a cuántas personas sigue ese usuario.

4.9 Representación en JavaScript

La estructura puede parecer idéntica, pero la interpretación de cada par cambia. En un grafo dirigido debemos conservar el orden.

const arcos = [
  ["Ana", "Bruno"],
  ["Bruno", "Carla"],
  ["Carla", "Ana"]
];

function salidasDe(vertice) {
  return arcos
    .filter(([origen]) => origen === vertice)
    .map(([, destino]) => destino);
}

function entradasDe(vertice) {
  return arcos
    .filter(([, destino]) => destino === vertice)
    .map(([origen]) => origen);
}

console.log("Ana sigue a:", salidasDe("Ana"));
console.log("Siguen a Ana:", entradasDe("Ana"));

4.10 Comprobar una relación

La consulta también depende del tipo de grafo. En un dígrafo solo buscamos el par en el orden solicitado.

const conexiones = [["A", "B"], ["B", "C"]];

function existeArco(origen, destino) {
  return conexiones.some(([a, b]) =>
    a === origen && b === destino
  );
}

console.log(existeArco("A", "B"));
console.log(existeArco("B", "A"));

El primer resultado es true y el segundo es false. Si el grafo fuera no dirigido, ambos representarían la misma conexión.

4.11 Cómo elegir el tipo de grafo

4.12 Errores comunes

• Suponer que A→B implica automáticamente B→A.
• Usar un grafo dirigido para una relación que siempre es recíproca y duplicar todas las aristas.
• Perder el orden de origen y destino al guardar un arco.
• Calcular un único grado cuando el grafo es dirigido.
• Confundir la orientación visual del dibujo con la dirección indicada por la flecha.
• Elegir el tipo de grafo sin considerar la pregunta que resolverá el programa.

4.13 Qué debes recordar de este tema

• Las aristas de un grafo no dirigido no tienen orientación.
• Los arcos de un grafo dirigido poseen origen y destino.
• En un grafo no dirigido, {A, B} y {B, A} son la misma arista.
• En un grafo dirigido, (A, B) y (B, A) son arcos diferentes.
• Los dígrafos distinguen grado de entrada y grado de salida.
• La naturaleza de la relación determina qué tipo de grafo debemos utilizar.

4.14 Conclusión

Elegir entre un grafo dirigido y uno no dirigido determina cómo se interpretan todas sus conexiones. Una flecha puede expresar movimiento permitido, seguimiento, dependencia o flujo, mientras que una línea representa una relación simétrica.

En el próximo tema diferenciaremos grafos simples y multigrafos según la cantidad y el tipo de aristas permitidas entre sus vértices.