Los puentes de Königsberg
El nacimiento del concepto GRAFOS se puede situar, por el año 1730, cuando Euler se convirtió en el padre de la Teoría de Grafos al modelar un famoso problema no resuelto, llamado el "problema de los puentes de Königsberg". Un río con dos islas atraviesa la ciudad. Las islas están unidas, entre si y con las orillas, a través de siete puentes. El problema consistía en establecer un recorrido que pasara una y solo una vez por cada uno de los siete puentes, partiendo de cualquier punto y regresando al mismo lugar. Para probar que no era posible, Euler sustituyó cada zona de partida por un punto y cada puente por un arco, creando así un grafo, el primer grafo, diseñado para resolver un problema.
Mostrar que el problema no tiene solución equivale a mostrar que el grafo no puede ser recorrido según criterios determinados. Problema genérico: dado un grafo (con múltiples líneas entre pares de puntos) encontrar un camino que recorra el grafo pasando por cada arista exactamente una vez.
Texto original extraído de http://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/teorico/grafos.pdf
Un camino euleriano en un grafo G es un camino que pasa por cada arista de G una y sólo una vez.
Teorema: Un grafo conexo tiene un camino euleriano si y sólo si tiene exactamente dos nodos de grado impar.
No hay comentarios:
Publicar un comentario