Capítulo 9
Puentes, Redes y Grafos
Descubre la teoría de grafos a través del famoso problema de los Puentes de Königsberg.
Un grafo es una forma de representar conexiones usando puntos (llamados vértices) unidos por líneas (llamadas aristas). Los mapas del metro, las redes de amistades y los enlaces entre páginas web se pueden dibujar como grafos.
El problema de los Puentes de Königsberg
Hace mucho tiempo, en la ciudad de Königsberg había un río con dos islas, conectadas entre sí y con las orillas por 7 puentes. Las personas se preguntaban: ¿es posible dar un paseo que cruce cada uno de los 7 puentes exactamente una vez y regrese al punto donde empezó?
La idea genial de los grafos
Hace casi 300 años, este problema se resolvió de una forma muy inteligente: se convirtió el mapa en un grafo. Cada zona de tierra se volvió un punto (vértice) y cada puente se volvió una línea (arista) que conecta dos puntos. Así se descubrió una regla general: un recorrido que cruce cada arista exactamente una vez y regrese al inicio (llamado circuito euleriano) solo es posible si CADA vértice tiene un número PAR de conexiones. En Königsberg, los 4 vértices tenían un número impar de puentes, así que... ¡el paseo perfecto era imposible!
🧪Recorre el grafo como Euler
Intenta recorrer cada línea una sola vez y volver al inicio. En 'El moño' se puede… ¿y en Königsberg?
1) Toca un punto para empezar. 2) Toca las líneas punteadas para recorrerlas, una sola vez cada una, y regresa al inicio.
¿Sabías que...?
La solución de este problema dio nacimiento a una nueva rama de las matemáticas llamada teoría de grafos, que hoy se usa para diseñar redes de internet, rutas de transporte y mucho más.
La fórmula mágica: V + R − E = 2
Existe otra fórmula sorprendente, llamada la fórmula de Euler, para cualquier grafo conectado dibujado sobre una hoja: si cuentas V (el número de vértices o puntos), R (el número de regiones en las que las líneas dividen la hoja, contando la región de afuera) y E (el número de aristas o líneas), siempre se cumple que V + R − E = 2. ¡Pruébalo con cualquier dibujo que hagas!
Actividad
Dibuja varios puntos en una hoja y conéctalos con líneas formando un grafo. Cuenta cuántos puntos (V), líneas (E) y regiones (R, incluyendo la de afuera) hay, y verifica que V + R − E = 2. Después, para cada punto cuenta cuántas líneas le llegan: ¿son todos números pares?