Relaciones y funciones discretas - 44. Aplicaciones en teoría de grafos

44.1 Introducción

Un grafo es un par G = (V, E) donde V es un conjunto de vértices y E es una relación binaria sobre V. Los elementos de E son aristas que conectan pares de vértices.

La teoría de grafos formaliza preguntas intuitivas:

¿Existe un camino entre dos ciudades? → Conectividad
¿Cuál es la ruta más corta? → Camino mínimo
¿Cómo conectar todos los nodos con mínimo costo? → Árbol generador mínimo
¿Se puede colorear con k colores sin que vértices adyacentes compartan color? → Coloración
¿Cuánto flujo máximo pasa de fuente a sumidero? → Flujo máximo

Cada pregunta corresponde a una propiedad de la relación binaria E. Este tema explora cómo resolver estos problemas algorítmicamente.

44.2 Grafos como Relaciones Binarias

Un grafo no dirigido modela una relación simétrica: si hay arista (u,v), también hay (v,u).

Un grafo dirigido modela una relación asimétrica: (u,v) ≠ (v,u).

Ejemplo formal: Una red social donde "sigue a" es un grafo dirigido. Si Ana sigue a Luis, no significa que Luis siga a Ana. La relación sigue = {(Ana, Luis), (Luis, Marta), (Marta, Ana)} forma un ciclo dirigido.

// Grafo como lista de adyacencia con pesos (ponderado)
class GrafoPonderado {
  constructor(vertices) {
    this.vertices = vertices;
    this.adyacencia = new Map();
    vertices.forEach(v => this.adyacencia.set(v, []));
  }

  agregarArista(u, v, peso = 1) {
    this.adyacencia.get(u).push({ destino: v, peso });
  }

  // Obtener vecinos de un vértice
  vecinos(v) {
    return this.adyacencia.get(v);
  }

  // Grado de un vértice (número de aristas)
  grado(v) {
    return this.adyacencia.get(v).length;
  }

  // Obtener todas las aristas
  aristas() {
    const aristas = [];
    for (const [u, adyacentes] of this.adyacencia) {
      for (const { destino: v, peso } of adyacentes) {
        aristas.push({ u, v, peso });
      }
    }
    return aristas;
  }
}

// Uso
const grafo = new GrafoPonderado(["A", "B", "C", "D"]);
grafo.agregarArista("A", "B", 4);
grafo.agregarArista("A", "C", 2);
grafo.agregarArista("B", "C", 1);
grafo.agregarArista("B", "D", 5);
grafo.agregarArista("C", "D", 8);

console.log("Grado de A:", grafo.grado("A"));       // 2
console.log("Aristas:", grafo.aristas());

44.3 Conectividad y Componentes Conexas

Un grafo es conexo si existe camino entre todo par de vértices. Las componentes conexas son subgrafos máximos conexos.

// Encontrar componentes conexas con DFS
class GrafoConexo {
  constructor(vertices) {
    this.vertices = vertices;
    this.adyacencia = new Map();
    vertices.forEach(v => this.adyacencia.set(v, []));
  }

  agregarArista(u, v) {
    this.adyacencia.get(u).push(v);
    this.adyacencia.get(v).push(u);
  }

  // DFS para marcar vértices visitados
  dfs(v, visitados) {
    visitados.add(v);
    for (const vecino of this.adyacencia.get(v)) {
      if (!visitados.has(vecino)) {
        this.dfs(vecino, visitados);
      }
    }
  }

  // Encontrar componentes conexas
  componentesConexas() {
    const visitados = new Set();
    const componentes = [];

    for (const v of this.vertices) {
      if (!visitados.has(v)) {
        const componente = new Set();
        this.dfs_marcar(v, visitados, componente);
        componentes.push(Array.from(componente));
      }
    }
    return componentes;
  }

  dfs_marcar(v, visitados, componente) {
    visitados.add(v);
    componente.add(v);
    for (const vecino of this.adyacencia.get(v)) {
      if (!visitados.has(vecino)) {
        this.dfs_marcar(vecino, visitados, componente);
      }
    }
  }
}

// Uso
const grf = new GrafoConexo(["A", "B", "C", "D", "E"]);
grf.agregarArista("A", "B");
grf.agregarArista("B", "C");
grf.agregarArista("D", "E");

console.log("Componentes:", grf.componentesConexas());
// [["A", "B", "C"], ["D", "E"]]

44.4 Camino Más Corto: Algoritmo de Dijkstra

Dijkstra encuentra el camino mínimo desde un nodo fuente a todos los demás. Usa una propiedad de optimalidad: el subcamino de un camino óptimo es también óptimo.

Aplicación: GPS busca la ruta más rápida usando Dijkstra en un grafo ponderado de carreteras donde los pesos son tiempos o distancias.

// Algoritmo de Dijkstra (O(V² + E) con array, O((V + E) log V) con heap)
class GrafoDijkstra {
  constructor(vertices) {
    this.vertices = vertices;
    this.adyacencia = new Map();
    vertices.forEach(v => this.adyacencia.set(v, []));
  }

  agregarArista(u, v, peso) {
    this.adyacencia.get(u).push({ destino: v, peso });
  }

  dijkstra(fuente) {
    const distancias = new Map();
    const visitados = new Set();
    const anterior = new Map();

    // Inicializar distancias
    for (const v of this.vertices) {
      distancias.set(v, v === fuente ? 0 : Infinity);
      anterior.set(v, null);
    }

    for (let i = 0; i < this.vertices.length; i++) {
      // Seleccionar vértice no visitado con mínima distancia
      let u = null;
      let minDist = Infinity;

      for (const v of this.vertices) {
        if (!visitados.has(v) && distancias.get(v) < minDist) {
          u = v;
          minDist = distancias.get(v);
        }
      }

      if (u === null || minDist === Infinity) break;

      visitados.add(u);

      // Relajación de aristas
      for (const { destino: v, peso } of this.adyacencia.get(u)) {
        const nuevaDist = distancias.get(u) + peso;
        if (nuevaDist < distancias.get(v)) {
          distancias.set(v, nuevaDist);
          anterior.set(v, u);
        }
      }
    }

    return { distancias, anterior };
  }

  // Reconstruir camino desde fuente a destino
  reconstruirCamino(anterior, destino) {
    const camino = [];
    let actual = destino;
    while (actual !== null) {
      camino.unshift(actual);
      actual = anterior.get(actual);
    }
    return camino;
  }
}

// Uso
const gd = new GrafoDijkstra(["A", "B", "C", "D"]);
gd.agregarArista("A", "B", 4);
gd.agregarArista("A", "C", 2);
gd.agregarArista("B", "C", 1);
gd.agregarArista("B", "D", 5);
gd.agregarArista("C", "D", 8);

const { distancias, anterior } = gd.dijkstra("A");
console.log("Distancias desde A:", distancias);
// Map { A → 0, C → 2, B → 3, D → 8 }

console.log("Camino A→D:", gd.reconstruirCamino(anterior, "D"));
// ["A", "C", "B", "D"]

44.5 Árbol Generador Mínimo (MST)

Un árbol generador es un subgrafo conexo acíclico que conecta todos los vértices. El MST es el árbol generador con peso mínimo.

Aplicación: Diseñar una red de telecomunicaciones con mínimo costo de cables, o una red de distribución con mínima longitud de tuberías.

// Algoritmo de Kruskal para MST (usando Union-Find)
class UnionFind {
  constructor(elementos) {
    this.padre = new Map();
    this.rango = new Map();
    elementos.forEach(e => {
      this.padre.set(e, e);
      this.rango.set(e, 0);
    });
  }

  encontrar(x) {
    if (this.padre.get(x) !== x) {
      this.padre.set(x, this.encontrar(this.padre.get(x))); // Compresión de ruta
    }
    return this.padre.get(x);
  }

  unir(x, y) {
    const px = this.encontrar(x);
    const py = this.encontrar(y);

    if (px === py) return false; // Ya están en el mismo conjunto

    // Unión por rango
    if (this.rango.get(px) < this.rango.get(py)) {
      this.padre.set(px, py);
    } else if (this.rango.get(px) > this.rango.get(py)) {
      this.padre.set(py, px);
    } else {
      this.padre.set(py, px);
      this.rango.set(px, this.rango.get(px) + 1);
    }
    return true;
  }
}

class GrafoMST {
  constructor(vertices) {
    this.vertices = vertices;
    this.aristas = [];
  }

  agregarArista(u, v, peso) {
    this.aristas.push({ u, v, peso });
  }

  kruskal() {
    // Ordenar aristas por peso
    this.aristas.sort((a, b) => a.peso - b.peso);

    const uf = new UnionFind(this.vertices);
    const mst = [];
    let pesoTotal = 0;

    for (const { u, v, peso } of this.aristas) {
      if (uf.unir(u, v)) {
        mst.push({ u, v, peso });
        pesoTotal += peso;
      }
    }

    return { mst, pesoTotal };
  }
}

// Uso
const gm = new GrafoMST(["A", "B", "C", "D"]);
gm.agregarArista("A", "B", 4);
gm.agregarArista("A", "C", 2);
gm.agregarArista("B", "C", 1);
gm.agregarArista("B", "D", 5);
gm.agregarArista("C", "D", 8);

const { mst, pesoTotal } = gm.kruskal();
console.log("MST:", mst);
// [{ u: "B", v: "C", peso: 1 }, { u: "A", v: "C", peso: 2 }, { u: "A", v: "B", peso: 4 }]

console.log("Peso total:", pesoTotal); // 7

44.6 Ciclos, Bipartición y Coloración

Un grafo acíclico (DAG) no contiene ciclos. Un grafo es bipartido si sus vértices se pueden dividir en dos conjuntos sin aristas dentro de cada conjunto.

// Detectar si un grafo es bipartido (2-coloreable)
class GrafoBipartido {
  constructor(vertices) {
    this.vertices = vertices;
    this.adyacencia = new Map();
    vertices.forEach(v => this.adyacencia.set(v, []));
  }

  agregarArista(u, v) {
    this.adyacencia.get(u).push(v);
    this.adyacencia.get(v).push(u);
  }

  esBipartido() {
    const color = new Map();

    for (const v of this.vertices) {
      if (color.get(v) === undefined) {
        // BFS para colorear
        const cola = [v];
        color.set(v, 0);

        while (cola.length > 0) {
          const u = cola.shift();
          for (const vecino of this.adyacencia.get(u)) {
            if (color.get(vecino) === undefined) {
              color.set(vecino, 1 - color.get(u));
              cola.push(vecino);
            } else if (color.get(vecino) === color.get(u)) {
              return false; // Vecino tiene el mismo color
            }
          }
        }
      }
    }
    return true;
  }

  // Coloración greedy (no óptima en general)
  coloracionGreedy() {
    const color = new Map();
    const coloresDisponibles = new Set();

    for (const v of this.vertices) {
      const coloresUsados = new Set();

      for (const vecino of this.adyacencia.get(v)) {
        if (color.get(vecino) !== undefined) {
          coloresUsados.add(color.get(vecino));
        }
      }

      let c = 0;
      while (coloresUsados.has(c)) c++;
      color.set(v, c);
    }

    return color;
  }
}

// Uso
const gb = new GrafoBipartido(["A", "B", "C", "D"]);
gb.agregarArista("A", "B");
gb.agregarArista("A", "C");
gb.agregarArista("B", "D");
gb.agregarArista("C", "D");

console.log("¿Es bipartido?", gb.esBipartido()); // true
console.log("Coloración:", gb.coloracionGreedy());

44.7 Flujo Máximo y Corte Mínimo

En un grafo con capacidades en aristas, el flujo máximo es la máxima cantidad que puede fluir de una fuente a un sumidero. El teorema min-corte max-flujo relaciona esto con el corte de mínima capacidad.

Aplicación: Redes de distribución de agua, flujo de tráfico, capacidad de redes de telecomunicaciones.

// Algoritmo de Ford-Fulkerson (simplificado con BFS = Edmonds-Karp)
class GrafoFlujo {
  constructor(vertices) {
    this.vertices = vertices;
    this.grafo = new Map();
    vertices.forEach(v => this.grafo.set(v, new Map()));
  }

  agregarArista(u, v, capacidad) {
    if (!this.grafo.get(u).has(v)) {
      this.grafo.get(u).set(v, 0);
    }
    if (!this.grafo.get(v).has(u)) {
      this.grafo.get(v).set(u, 0);
    }
    this.grafo.get(u).set(v, capacidad);
  }

  bfsEncontrarCamino(fuente, sumidero) {
    const visitados = new Set([fuente]);
    const cola = [[fuente, [fuente]]];

    while (cola.length > 0) {
      const [u, camino] = cola.shift();

      if (u === sumidero) return camino;

      for (const v of this.grafo.get(u).keys()) {
        if (!visitados.has(v) && this.grafo.get(u).get(v) > 0) {
          visitados.add(v);
          cola.push([v, [...camino, v]]);
        }
      }
    }
    return null;
  }

  flujoMaximo(fuente, sumidero) {
    let flujoTotal = 0;

    while (true) {
      const camino = this.bfsEncontrarCamino(fuente, sumidero);
      if (!camino) break;

      // Encontrar la capacidad mínima del camino
      let flujoMinimo = Infinity;
      for (let i = 0; i < camino.length - 1; i++) {
        const u = camino[i];
        const v = camino[i + 1];
        flujoMinimo = Math.min(flujoMinimo, this.grafo.get(u).get(v));
      }

      // Actualizar capacidades
      for (let i = 0; i < camino.length - 1; i++) {
        const u = camino[i];
        const v = camino[i + 1];
        this.grafo.get(u).set(v, this.grafo.get(u).get(v) - flujoMinimo);
        this.grafo.get(v).set(u, this.grafo.get(v).get(u) + flujoMinimo);
      }

      flujoTotal += flujoMinimo;
    }

    return flujoTotal;
  }
}

// Uso
const gf = new GrafoFlujo(["A", "B", "C", "D"]);
gf.agregarArista("A", "B", 10);
gf.agregarArista("A", "C", 10);
gf.agregarArista("B", "D", 4);
gf.agregarArista("C", "B", 2);
gf.agregarArista("C", "D", 8);

console.log("Flujo máximo A→D:", gf.flujoMaximo("A", "D")); // 12

44.8 Aplicaciones Prácticas

Los algoritmos de grafos resuelven problemas reales en:

Navegación: GPS usa Dijkstra para rutas más cortas
Redes sociales: Buscar amigos a distancia k, comunidades (componentes)
Logística: Problemas de ruteo, TSP (viajante)
Telecomunicaciones: Flujo máximo en redes, diseño de redes con MST
Verificación de programas: DAGs para detectar deadlocks
Compiladores: Grafos de dependencias, ordenamiento topológico
Juegos: Búsqueda A* en grafos de estados

// Aplicación: Red social - distancia geodésica
class RedSocial {
  constructor(usuarios) {
    this.usuarios = usuarios;
    this.adyacencia = new Map();
    usuarios.forEach(u => this.adyacencia.set(u, []));
  }

  agregarAmistad(u, v) {
    this.adyacencia.get(u).push(v);
    this.adyacencia.get(v).push(u);
  }

  // Encontrar distancia mínima entre dos usuarios (BFS)
  distancia(u, v) {
    if (u === v) return 0;

    const visitados = new Set([u]);
    const cola = [[u, 0]];

    while (cola.length > 0) {
      const [nodo, dist] = cola.shift();

      for (const vecino of this.adyacencia.get(nodo)) {
        if (vecino === v) return dist + 1;
        if (!visitados.has(vecino)) {
          visitados.add(vecino);
          cola.push([vecino, dist + 1]);
        }
      }
    }

    return Infinity; // No conexo
  }

  // Grado de separación (six degrees)
  usuariosADistancia(usuario, k) {
    const visitados = new Map();
    const cola = [[usuario, 0]];
    visitados.set(usuario, 0);

    while (cola.length > 0) {
      const [u, dist] = cola.shift();

      for (const vecino of this.adyacencia.get(u)) {
        if (!visitados.has(vecino)) {
          visitados.set(vecino, dist + 1);
          if (dist + 1 <= k) {
            cola.push([vecino, dist + 1]);
          }
        }
      }
    }

    const resultado = [];
    for (const [usuario, distancia] of visitados) {
      if (distancia === k) resultado.push(usuario);
    }
    return resultado;
  }
}

// Uso
const red = new RedSocial(["Ana", "Luis", "Marta", "Carlos", "Diana"]);
red.agregarAmistad("Ana", "Luis");
red.agregarAmistad("Luis", "Marta");
red.agregarAmistad("Marta", "Carlos");
red.agregarAmistad("Carlos", "Diana");

console.log("Distancia Ana-Diana:", red.distancia("Ana", "Diana"));     // 4
console.log("Amigos a distancia 2 de Ana:", red.usuariosADistancia("Ana", 2));
// ["Marta"]

44.9 Resumen: Teoría de Grafos y Relaciones

Grafo: Relación binaria con propiedades estructurales
Conectividad: Existe camino entre vértices
Dijkstra: Camino más corto desde fuente a todos
MST: Árbol generador con peso mínimo (Kruskal, Prim)
Bipartición: 2-coloración de vértices
Flujo máximo: Máxima cantidad que fluye fuente→sumidero
Ordenamiento topológico: Orden lineal de DAG respetando precedencias
Aplicaciones: GPS, redes sociales, logística, telecomunicaciones

Qué debes recordar de este tema

Un grafo es una relación binaria; sus propiedades se heredan de la teoría de relaciones
La conectividad depende de la reflexividad y transitividad de la relación
El algoritmo de Dijkstra explota la propiedad de optimalidad: subestructura óptima
El MST resuelve minimización con relaciones de "menor costo"
Bipartición es 2-coloración, relacionada con relaciones simétricas vs. antisimétricas
Flujo máximo es optimización en una relación de capacidad
Los algoritmos de grafos son el corazón de muchas aplicaciones reales: desde GPS hasta redes sociales
La complejidad es crítica: Dijkstra es O(V²), Kruskal es O(E log E), Ford-Fulkerson es O(VE²)

Conclusión

La teoría de grafos es una de las aplicaciones más impactantes de las relaciones discretas. Los grafos permiten modelar sistemas complejos del mundo real: redes, dependencias, relaciones.

Cada algoritmo de grafos que hemos estudiado—desde DFS/BFS hasta Dijkstra, Kruskal y Ford-Fulkerson—explota una propiedad específica de la relación binaria subyacente:

DFS/BFS explotan la estructura de alcanzabilidad
Dijkstra explota la propiedad de optimalidad y orden de distancias
Kruskal/Prim explotan la propiedad de mínimo peso
Ford-Fulkerson explota la capacidad como cota superior en la relación de flujo

Lo más importante es que ninguno de estos algoritmos es "magia". Cada uno es una consecuencia lógica de las propiedades de las relaciones discretas.

Cuando entiendas que un grafo es simplemente una relación binaria con estructura, y que los algoritmos de grafos explotan esas estructuras, habrás adquirido una comprensión profunda de por qué funcionan. Eso te permitirá:

Resolver nuevos problemas reconociendo estructuras relacionales
Diseñar algoritmos propios basados en relaciones
Entender por qué los algoritmos fallan cuando las precondiciones (relaciones) no se cumplen
Optimizar soluciones aprovechando propiedades de la relación

La teoría de grafos y las relaciones discretas son el lenguaje universal de la computación moderna. Dominarlas es dominar la esencia de cómo resolvemos problemas complejos con elegancia algorítmica.

Volver al índice