Aplicación del teorema de los cuatro colores.

Estaba leyendo el teorema de los cuatro colores y me pregunto si hay alguna aplicación práctica. (No creo que separar el mapa en cuatro colores diferentes pueda considerarse una aplicación).

Intenté buscar en Google las aplicaciones, pero no pude encontrar ninguna.

Una de las aplicaciones más notables de 4 Color Theorem se encuentra en los mástiles de teléfonos móviles. Todos estos mástiles cubren ciertas áreas con cierta superposición, lo que significa que no todos pueden transmitir en la misma frecuencia. Un método simple para garantizar que no haya dos mástiles que se superpongan tienen la misma frecuencia es darles a todos una frecuencia diferente. Pero, como el gobierno posee todas las frecuencias y cobra por cada una, uno quiere usar el mínimo número posible de frecuencias. Las áreas cubiertas se pueden dibujar como un mapa y las diferentes frecuencias se pueden representar como colores.

Los problemas de coloración de gráficos son ampliamente aplicables al problema de la programación.

Considere una universidad, donde está tratando de programar horarios para todos los exámenes finales. Algunos estudiantes toman más de una clase, por lo que debe asegurarse de que no tengan dos exámenes programados al mismo tiempo. Sin embargo, desea que el período de redacción de su examen sea lo más breve posible, para ejecutar tantos exámenes simultáneamente como sea posible.

Puede representar esto como un problema de coloración gráfica: usted hace $G=(V,E)$donde cada clase es un vértice y un borde entre vértices cada vez que dos clases contienen el mismo alumno. Sus colores representarán diferentes intervalos de tiempo de examen. El número mínimo con el que puede colorear ese gráfico es el menor número de intervalos de tiempo que necesita para escribir todos sus exámenes.

El problema en general es NP difícil, pero si tenía algún conocimiento sobre su horario, por ejemplo, que era plano, entonces podría aplicar el teorema de 4 colores para escribir todos los exámenes juntos.

No estoy 100% seguro de que alguna vez obtenga un gráfico plano en un problema de programación de la vida real, pero aquí hay una lección más amplia: los gráficos son ampliamente aplicables a cosas que no son obvias de inmediato. El teorema de 4 colores no se trata solo de gráficos y mapas, sino que puede usarse para modelar problemas de la vida real en los que está expresando un conjunto de objetos y algunas relaciones binarias entre esos objetos.

sí gráfico plano $n$-color para bajo / fijo $n$tiene aplicaciones mínimas, principalmente coloración de mapa plano. sin embargo$n$-color para arbitrario $n$es NP completo , fue uno de los ^primeros problemas comprobados NP completo, por lo tanto, vincularse al edificio masivo de la teoría. pero en realidad incluso$n$-color puede reducirse a 3 colores a través de una transformación básica. [1] entonces$n$ colorear para $n \geq 3$está NP completo (pero no restringido a gráficos planos) . Probablemente hay otras reducciones a 4 colores y mapas planos estudiados en la literatura. es decir, para tener una mejor idea de su importancia, habría que estudiar las posibles reducciones, que es un tema complejo / avanzado / amplio.

pero otro ángulo es que la cuestión de la coloración en 4 de un mapa / gráfico plano fue un problema abierto difícil en matemáticas / ciencias de la computación durante muchas décadas (en realidad más de 1½ siglo de antigüedad , y uno de los primeros problemas gráficos muy avanzados). Las matemáticas avanzan a través de la resolución de problemas no resueltos. encaja en un patrón central común de "problemas que son fáciles de enunciar pero las soluciones / pruebas estuvieron inaccesibles durante mucho tiempo y son muy complejas". Esta es una asimetría fundamental generalizada en matemáticas que muestra los límites del apalancamiento matemático / teórico .

Las técnicas que tienen éxito pueden aplicarse a otros problemas no resueltos y, a veces, abren nuevas perspectivas / abstracciones teóricas / conceptuales. a veces las pruebas notables son valiosas por derecho propio y el teorema de 4 colores se ajusta a esta categoría. Es una de las pruebas de teorema automatizadas tempranas más sofisticadas. Se han realizado más trabajos para mejorar las simplificaciones legibles por humanos desde que se descubrió y causó un choque relativo a través de la comunidad teórica en su anuncio, y provocó mucho más análisis y comentarios. Sirve como un punto de referencia clave / hito / caso de prueba para mejoras en la demostración automatizada de teoremas .

[1] 3 colores son NP completos