Presentamos hoy uno de los típicos problemas o pasatiempos en los que hay que conseguir trazar una figura de un solo trazo, es decir, en una sola línea, sin levantar el lápiz del papel y sin pasar dos veces por un mismo camino ya dibujado:
¿Es usted capaz de dibujar, de un solo trazo, la siguiente figura triangulada?
La solución, unos cuantos triángulos más abajo.
 |
| Buscando triángulos hemos encontrado esta caja de porciones de queso. Anuncia que lleva dentro "16 cheese triangles", (16 triángulos de queso), aunque estrictamente hablando, las porciones no son triangulares, porque uno de sus lados es curvo. Pero claro, anunciar que dentro de la caja hay "16 cheese circular sectors", (16 sectores circulares de queso), sería no solo confuso, sino matemáticamente pedante. |
SOLUCIÓN:
En este grafo en particular podemos empezar a trazar por cualquiera de los puntos, y si hacemos el recorrido de forma inteligente lograremos nuestro objetivo.
Así, por ejemplo, podemos empezar por el vértice A, y luego hacer el siguiente recorrido:
A - C - D - B - G - I - J - H - E - C - F - I - H - F - D - G - F - E - A
Pasando en este orden por los diferentes vértices habremos resuelto el problema. Hay muchas otras soluciones que el lector puede ir probando.
AMPLIACIÓN:
Históricamente, el problema de dibujar grafos pasando por todas las aristas sin levantar el lápiz del papel tiene su origen en el Problema de los Puentes de Königsberg. Este problema fue resuelto por Leonhard Euler, y dio origen a una nueva rama de las matemáticas, la Topología, también llamada originalmente Analisis Situs.
La solución de Euler es muy sencilla de entender y se basa en clasificar los vértices del grafo en vértices pares o impares, según el número de aristas que convergen en cada vértice:
-Si un grafo solo tiene vértices pares, entonces se puede dibujar de un solo trazo, empezando por cualquier vértice.
-Si un grafo tiene dos vértices impares y el resto son pares, también se puede dibujar, pero esta vez hay que empezar el trazo en uno de los vértices impares, mientras que el otro vértice impar será el punto en el que finaliza el trazo.
-Si un grafo tiene cuatro o más vértices impares, entonces no se puede dibujar de un solo trazo.
En el grafo que hemos puesto en el problema de hoy, podemos ver que todos los vértices son pares: en A, B y J convergen 2 aristas, en C, D, E, G, H e I convergen 4 aristas, y en F convergen 6. Por tanto, se puede dibujar de un solo trazo, empezando por cualquier punto.
Nota: este problema está inspirado en un capítulo del libro Mathematics and the Imagination, de Edward Kasner y James Newman.
No hay comentarios:
Publicar un comentario