Un mapa universal que evita que te pierdas

Buscamos un mapa universal que evite que te pierdas. ¿es posible? ¿Y si las calles del lugar estuvieran teñidas de un color específico?, de esa forma podrías caminar con un patrón fijo para llegar a su destino.

Lai Jiayi | Profesor de la Universidad Shu Tzu Chi

Creo que todos tienen esta experiencia: hice una cita con mi amigo en un lugar, pero se perdió en el vecindario, y finalmente tuvo que llamarte, decirte dónde estás y pedirte indicaciones. Pero si una persona está en un país extranjero, será más problemático, es posible que no entienda las señales de tráfico y los nombres de las tiendas.

En este momento, si las calles del lugar están teñidas de un color específico, puede caminar con un patrón fijo para llegar a su destino, ¿no sería conveniente? Puedes decirle por teléfono: «Después de caminar por la carretera azul hasta la intersección, cambia a la roja, y cuando vayas a la siguiente intersección, continúa hacia la roja. Una vez que la roja esté terminada, luego la azul , El azul va hasta la intersección para cambiar a rojo, y el rojo va a una intersección y continúa en rojo, para que puedas llegar allí ”. Para decirlo más claramente, él sigue caminando en el patrón» azul-rojo-rojo «. Incluso si no sabe dónde está ahora, finalmente puede llegar al lugar designado.

Tal vez sea difícil de imaginar en términos simples, por lo que es mejor mirar la imagen a continuación. Repita tres veces de acuerdo con el patrón «azul-rojo-rojo», no importa dónde se encuentre, puede llegar al punto amarillo, y de acuerdo con el patrón «azul-azul-rojo», repita tres veces, definitivamente llegará al punto verde.

teoria-de-grafos
créditos imagen:wikipedia

El problema de la coloración de las carreteras es uno de los problemas más famosos de la teoría de grafos. El gráfico formado por los nodos y los bordes que conectan los nodos se puede extender a un sistema que se encuentra en el mundo real. Por ejemplo, las intersecciones de calles se pueden considerar como nodos y las calles como bordes. En el mundo de Internet, los nodos son enrutadores y los bordes son conexiones entre enrutadores. En una red de aviación, el nodo es el aeropuerto y el borde es el viaje desde el aeropuerto hasta el aeropuerto.

Lo curioso es, ¿existe un «mapa universal» ideal como este para la figura formada por cada punto y borde? ¿Simplemente colorea los bordes y sigue las sencillas y repetidas instrucciones para llegar al destino? En 1970, Benjamin. Wise y Roy. Adler primero planteó esta pregunta, originalmente solo buscando un mapa, y por cierto, pensó en diseñar un programa de depuración automática para una computadora. No pude pensar en la pregunta que hice y me tomó varios años probarlo. Debido a que esta idea es bastante interesante, ha atraído la atención de algunos matemáticos y se han publicado varios artículos relacionados.

Aunque la narrativa del problema parece simple, ha permanecido incomprensible en matemáticas durante casi 40 años, hasta Afrahan. Apareció Taketman, y demostró que cualquier punto y la figura compuesta por una composición se puede colorear en forma de «mapa universal» siempre que se cumplan ciertas condiciones. Esta prueba no es solo un logro en matemáticas, sino que también tiene un significado especial en el campo de la informática. Significa que en algunos casos, datos erróneos e interferencias no afectan los resultados, al igual que un amigo perdido que no conoce su ubicación, mientras repita instrucciones, puede llegar a su destino.

Materiales de referencia:

  1. Vojtěch Vorel, & Adam Roman. Complejidad de la coloración de las carreteras con palabras de reinicio prescritas. Journal of Computer and System Sciences.
  2. A. Roman, & M. Drewienkowski. Una solución completa a la complejidad de Sincronizar la coloración de carreteras para alfabetos no binarios. Información y computación. 242, 383-393.


Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para fines de afiliación y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad
Ir al contenido