Problema del cartero chino para niños
El problema del cartero chino es un desafío interesante en el campo de las matemáticas que busca encontrar el camino más corto en un mapa. Imagina que eres un cartero y necesitas entregar cartas en todas las calles de un barrio. El objetivo es recorrer cada calle al menos una vez y regresar al punto de partida, ¡haciéndolo en el menor tiempo posible!
Este problema también se conoce como el "problema del circuito del cartero" o "problema de la inspección y selección de rutas". Si el mapa tiene un camino especial llamado "circuito euleriano" (un recorrido que visita cada calle exactamente una vez), esa es la solución más eficiente.
Alan J. Goldman, del Instituto Nacional de Estándares y Tecnología de EE. UU., le dio el nombre de "problema del cartero chino". Lo hizo en honor al matemático chino Mei-Ko Kuan, quien estudió este problema por primera vez en 1962. Curiosamente, Mei-Ko Kuan era cartero.
Contenido
¿Qué es un Grafo?
Para entender el problema, primero necesitamos saber qué es un grafo. En matemáticas, un grafo es como un mapa simplificado.
- Está formado por vértices (o nodos), que son como los puntos o cruces en un mapa.
- Y está formado por aristas (o enlaces), que son como las calles o caminos que conectan esos puntos.
Un grafo se dice que está "conectado" si puedes ir de cualquier vértice a cualquier otro vértice siguiendo las aristas.
Caminos y Circuitos Especiales: Euler
Dentro de los grafos, existen caminos muy particulares que nos ayudan a resolver el problema del cartero.
¿Qué es un Circuito Euleriano?
Un circuito euleriano es un recorrido cerrado en un grafo que pasa por cada arista (calle) exactamente una vez. Es como si el cartero pudiera recorrer todas las calles sin repetir ninguna y terminara justo donde empezó.
Para que un grafo tenga un circuito euleriano, debe cumplir algunas condiciones:
- Debe estar conectado, es decir, no debe haber calles aisladas.
- Todos los vértices (cruces) del grafo deben tener un grado par. El grado de un vértice es el número de aristas (calles) que llegan a él. Si un cruce tiene un número par de calles que salen de él, es más fácil que el cartero pase por allí sin tener que repetir una calle para salir.
¿Qué es un Camino Euleriano?
Un camino euleriano es similar a un circuito euleriano, pero no es cerrado. Esto significa que el cartero recorre todas las calles una sola vez, pero termina en un punto diferente al de partida. Un camino euleriano existe si el grafo está conectado y tiene exactamente dos vértices con un grado impar.
¿Cómo se Resuelve el Problema del Cartero Chino?
El objetivo es encontrar el camino más corto que visite cada arista al menos una vez y regrese al inicio.
Cuando el Grafo es "Perfecto"
Si el grafo tiene un circuito euleriano, ¡la solución es sencilla! Cualquier circuito euleriano es la respuesta, porque ya visita cada arista una sola vez y es el camino más corto posible.
Cuando el Grafo no es "Perfecto"
A veces, un grafo no tiene un circuito euleriano. Esto ocurre cuando hay vértices con un grado impar. Siempre habrá un número par de estos vértices con grado impar.
Para resolver el problema en estos casos, necesitamos "arreglar" el grafo:
- La idea es encontrar los caminos más cortos entre los vértices que tienen un grado impar.
- Luego, "duplicamos" las aristas de esos caminos más cortos. Esto significa que imaginamos que esas calles se pueden recorrer dos veces.
- Al duplicar estas aristas, logramos que todos los vértices tengan un grado par.
- Una vez que todos los vértices tienen grado par, el grafo se convierte en un grafo euleriano.
- Finalmente, encontramos un circuito euleriano en este nuevo grafo "arreglado". Este circuito será la solución al problema original, ya que nos dirá el camino más corto para recorrer todas las calles, repitiendo solo las necesarias.
Véase también
En inglés: Chinese postman problem Facts for Kids
- Problema del viajante
- Ciclo euleriano
- Algoritmo de Dijkstra
