El 1er artículo referente a las teorías de graficas fue de Leonhard Euler en 1936; el artículo recitaba una teoría general que incluía una solución a lo que ahora se llama el problema de los puentes de Königsberg.
Dos islas en el rio Pregel en Königsberg (ahora Kaliningrado, Rusia) estaban conectadas entre sí y con las orillas de rio por puentes, como se aprecia en la sig. Figura. El problema es comenzar en cualquier lugar de A, B, C o D; cruzar cada puente exactamente una vez; luego regresar al lugar de inicio.
La configuración de los puentes se puede moderar como una gráfica, como se ve en la sig. Figura; los vértices representan los lugares y las aristas representan los puentes. El problema de los puentes de Königsberg ahora se reduce a encontrar un ciclo en la gráfica de la figura que incluya todas las aristas y todos los vértices. En honor a Euler, en un ciclo una gráfica que incluye todas las aristas G se llama ciclo Euler
No hay comentarios.:
Publicar un comentario