Ayúdame a pensar en...

En el siglo XVIII había en Europa una hermosa ciudad: Königsberg, donde había siete puentes. Como se muestra en la Figura 1, hay dos puentes que conectan la pequeña isla A en el río con la orilla izquierda B y la orilla derecha C del río, y un puente que conecta la tierra D entre los dos afluentes del río con A, B y C respectivamente. En aquel momento surgió entre los habitantes de Königsberg la pregunta: ¿Cómo es posible que una persona cruce siete puentes a la vez, pase por cada puente una sola vez y finalmente regrese al punto de partida? Todos intentan encontrar la respuesta al problema, pero nadie puede resolverlo.

El problema de los siete puentes atrajo la atención del famoso matemático Euler (1707-1783). Clasificó el diseño específico de los siete puentes en un gráfico simple como se muestra en la Figura 2, por lo que el problema de los siete puentes se convirtió en un problema de un solo trazo: ¿Cómo podemos comenzar desde un cierto punto de A, B, C y D? ?Tan pronto como el bolígrafo dibuje esta figura simple (es decir, el bolígrafo no sale del papel, las líneas A, B, C, D, E, F y G solo se pueden dibujar una vez), ¿finalmente volverá a? el punto de partida? Después de la investigación de Euler, llegó a la conclusión de que la Figura 2 es una figura que no se puede dibujar de un solo trazo. En otras palabras, no hay solución al Problema de los Siete Puentes. ¿Cómo se llegó a esta conclusión? Vea el análisis a continuación.

Si partimos de un determinado punto, dibujamos una determinada figura de un solo trazo, y terminamos en un determinado punto, entonces cada vez que el pincel pasa por un punto distinto al inicial y al final, habrá Siempre habrá una línea dibujada en el punto, y se dibujará una línea en el punto. Si se dibuja una línea en este punto, entonces hay dos líneas conectadas a este punto. Si el pincel pasa n veces, hay 2n líneas conectadas al punto. Por lo tanto, todos los puntos de este gráfico, excepto los puntos inicial y final, están conectados por líneas pares. Si el punto inicial y el punto final coinciden, entonces este punto también está conectado por una línea par; si el punto inicial y el punto final son dos puntos diferentes, entonces los dos puntos son puntos conectados por una línea impar; En resumen, en la figura dibujada con un trazo, todos los puntos están conectados por líneas pares, o solo dos puntos están conectados por líneas impares.

En la Figura 2, el punto A está conectado por cinco líneas, el punto B, el punto C y el punto D están conectados por tres líneas respectivamente. Hay cuatro puntos en la figura conectados por líneas impares, por lo que no importa. el punto inicial y el punto final deben coincidir con No, no se puede dibujar la forma de un solo trazo.

En 1736, Euler presentó un informe académico en la Academia de Ciencias de San Petersburgo. En el informe demostró la conclusión anterior. Más tarde dio un criterio para juzgar si cualquier figura se puede dibujar de un solo trazo, a saber, el teorema de Euler. Para presentar este teorema, primero echemos un vistazo a los siguientes preliminares:

Un gráfico compuesto de líneas finitas se llama red, donde cada línea requiere dos puntos finales diferentes. Estas líneas se denominan arcos de la red y los puntos finales de los arcos se denominan vértices de la red. Por ejemplo, la Figura 2 es una red. A, B, C, D, E, F, G son sus siete arcos, y A, B, C, D son sus cuatro vértices.

Una serie de arcos interconectados en una red se denomina carretera. Si dos vértices cualesquiera de una red pueden conectarse mediante una ruta, entonces la red se denomina conectada; de lo contrario, se denomina no conectada. Por ejemplo, la Figura 2 es una red conectada; la Figura 3 es una red desconectada donde algunos vértices (como A y D) no están conectados mediante enrutamiento.

El número de arcos con un vértice como punto final en la red se llama número de intersección del vértice. Los vértices con un número impar de bifurcaciones se llaman vértices impares y los vértices con un número par de bifurcaciones se llaman vértices pares.

A continuación se presenta el teorema de Euler.

Teorema de Euler Si una red está conectada y el número de vértices impares es igual a 0 o 2, entonces se puede dibujar con un trazo; de lo contrario, no se puede dibujar con un trazo;

El teorema de Euler facilita determinar si un gráfico simple se puede dibujar de un solo trazo.