2. Historia de la teoría de grafos

2.1 Introducción

La historia de la teoría de grafos muestra cómo un problema cotidiano puede originar una nueva forma de pensar. Su punto de partida tradicional se encuentra en el siglo XVIII, cuando se intentaba resolver un paseo aparentemente sencillo por la ciudad prusiana de Königsberg.

La gran innovación no fue encontrar una ruta, sino representar el problema de manera abstracta. Al eliminar distancias, formas y detalles geográficos, quedaron únicamente lugares y conexiones. Esa idea sigue siendo esencial cuando un programador diseña un modelo de datos.

2.2 La ciudad de Königsberg

Königsberg estaba atravesada por el río Pregel. Dos islas y las zonas continentales quedaban comunicadas por siete puentes. Los habitantes se preguntaban si era posible realizar un paseo que cruzara cada puente exactamente una vez.

Intentar resolverlo sobre un mapa llevaba a probar rutas una tras otra. Sin embargo, la longitud de los puentes, la forma de las islas y la distancia recorrida no afectaban la respuesta.

2.3 La abstracción de Euler

En 1736, el matemático Leonhard Euler presentó un análisis del problema. Reemplazó cada región de tierra por un punto y cada puente por una conexión entre dos puntos.

Con esta transformación, el mapa dejó de ser un problema geográfico y se convirtió en una estructura de relaciones.

2.4 La solución de los siete puentes

Euler observó cuántos puentes llegaban a cada región. Para recorrer todas las aristas una sola vez, los vértices intermedios deben permitir entrar y salir por pares de aristas. Por eso, un recorrido abierto de este tipo solo puede tener cero o dos vértices de grado impar.

En el grafo de Königsberg, los cuatro vértices tenían grado impar. Por lo tanto, el paseo solicitado era imposible.

Este razonamiento anticipó lo que hoy conocemos como recorridos eulerianos, que estudiaremos en profundidad más adelante.

2.5 Una idea revolucionaria

La respuesta fue importante, pero el método lo fue aún más. Euler demostró que ciertas propiedades dependen de cómo están conectados los elementos y no de su tamaño, forma o ubicación exacta.

• Redujo un problema real a sus componentes esenciales.
• Representó objetos mediante puntos y relaciones mediante conexiones.
• Reemplazó la búsqueda por prueba y error con una propiedad matemática.
• Demostró la imposibilidad de una solución sin enumerar todos los recorridos.

Esta forma de abstraer un problema es muy cercana al trabajo de programar: elegir una estructura adecuada puede hacer que una solución compleja se vuelva clara.

2.6 Comprobar los grados con JavaScript

Podemos representar los siete puentes mediante pares de vértices y contar cuántas aristas inciden en cada uno.

const puentes = [
  ["A", "B"], ["A", "B"],
  ["A", "C"], ["A", "C"],
  ["A", "D"], ["B", "D"],
  ["C", "D"]
];

const grados = {};

for (const [origen, destino] of puentes) {
  grados[origen] = (grados[origen] || 0) + 1;
  grados[destino] = (grados[destino] || 0) + 1;
}

console.log(grados);
console.log("Grados impares:",
  Object.values(grados).filter(grado => grado % 2 !== 0).length
);

El programa obtiene cuatro grados impares. La computadora confirma la propiedad usada por Euler, aunque la explicación matemática es la que evita probar cada paseo posible.

2.7 El crecimiento durante el siglo XIX

Durante el siglo XIX, las ideas relacionadas con grafos aparecieron en diferentes áreas. Gustav Kirchhoff utilizó estructuras semejantes para estudiar circuitos eléctricos. Arthur Cayley investigó árboles mientras analizaba formas de compuestos químicos y estructuras algebraicas.

También surgieron problemas sobre recorridos que visitan todos los vértices, asociados al nombre de William Rowan Hamilton. Estos trabajos ampliaron el estudio desde el uso de todas las aristas hacia el recorrido de todos los vértices.

2.8 Del dibujo a una teoría formal

Con el paso del tiempo se desarrolló un lenguaje preciso para hablar de vértices, aristas, caminos, ciclos, conectividad, árboles y otros conceptos. Esto permitió demostrar resultados generales y comparar problemas que, a primera vista, no tenían relación.

La teoría también comenzó a estudiar distintas clases de grafos: dirigidos, ponderados, bipartitos, planares y muchos otros. Cada variante permite representar relaciones con propiedades específicas.

2.9 El siglo XX y los algoritmos

La aparición de las computadoras convirtió a los grafos en estructuras que podían almacenarse y procesarse. Ya no solo interesaba demostrar que una solución existía: también era necesario encontrarla mediante un procedimiento eficiente.

2.10 Los grafos en la era de Internet

Internet multiplicó el tamaño y la visibilidad de las redes. Las páginas web conectadas por enlaces forman un grafo; los routers y enlaces físicos forman otro; los usuarios y sus interacciones forman muchos grafos más.

Los motores de búsqueda analizan enlaces, las plataformas sociales estudian comunidades y los sistemas de recomendación relacionan usuarios con contenidos. En todos estos casos, la teoría desarrollada durante siglos se combina con estructuras de datos, algoritmos y computación distribuida.

2.11 De Königsberg al trabajo del programador

El problema de los puentes enseña un procedimiento que sigue siendo útil al desarrollar software:

1. Identificar qué pregunta debe responderse.
2. Eliminar los detalles que no afectan la respuesta.
3. Representar los objetos y sus relaciones.
4. Buscar una propiedad o algoritmo aplicable.
5. Comprobar la solución y analizar su costo.

function puedeTenerRecorridoEuleriano(grados) {
  const impares = grados.filter(grado => grado % 2 !== 0);
  return impares.length === 0 || impares.length === 2;
}

console.log(puedeTenerRecorridoEuleriano([3, 3, 3, 5]));
console.log(puedeTenerRecorridoEuleriano([2, 3, 3, 4]));

La primera lista representa cuatro grados impares y devuelve false. La segunda tiene exactamente dos y supera esta condición necesaria.

2.12 Qué debes recordar de este tema

• El origen tradicional de la teoría de grafos es el problema de los siete puentes de Königsberg.
• Euler estudió el problema en 1736 mediante una representación abstracta.
• Las regiones se convirtieron en vértices y los puentes en aristas.
• El recorrido era imposible porque los cuatro vértices tenían grado impar.
• Durante el siglo XIX, los grafos aparecieron en circuitos, árboles, química y problemas de recorridos.
• Las computadoras impulsaron el desarrollo de algoritmos eficientes para procesar grafos.
• Internet, las redes sociales y el software moderno convierten los grafos en una herramienta cotidiana.

2.13 Conclusión

La teoría de grafos comenzó con una pregunta sobre puentes, pero su verdadero aporte fue una nueva manera de representar relaciones. La abstracción introducida por Euler permitió analizar el problema sin depender del mapa ni de intentos exhaustivos.

En el próximo tema estudiaremos con mayor precisión los dos componentes fundamentales de cualquier grafo: los vértices y las aristas.