Problemas de los puentes de Königsberg

El primer artículo referente a la teoría de gráficas fue de Leonard Euler en 1736. El artículo presentaba una teoría general que incluía una solución a lo que ahora se llama el proble de los puentes de Königsberg.

Dos islas en el río Pregel en Königsberg estaban conectados entre sí y con las orillas de ríos por puentes, como se aprecia en la siguiente figura. El problema es comenzar en cualquier lugar de A, B, C ó D; cruzar cada puente exactamente una vez; luego regresar al lugar de inició.

La configuración de los puentes se puede modelar como una gráfica, como se ve en la siguiente 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 figura que incluya todas las aristas y todos los vértices. En honor a Euler, un ciclo es una gráfica que incluye todas las aristas y vértices de g se llama ciclo de Euler.

A partir del análisis en la sección se ve que no hay un circuito de Euler en la gráfica de la figura porque hay un número impar de aristas, incidentes en cada vértice.