7 votos

¿Intuición detrás de la "grande pero el espacio de búsqueda finita" de la prueba del teorema de cuatro colores?

Sé que el Teorema de color cuatro fue solucionado por una computadora de control de un gran número de casos. Lo que no entiendo es por qué hay sólo un número grande pero finito de casos. Parece que debe haber infinitamente muchos gráficos planares... ¿Qué es la intuición detrás de este hasta un número finito de configuraciones de corte?

18voto

Chris Benard Puntos 1430

No estoy seguro de entender o no entender cómo la prueba de la $4$ mapa de color teorema trabajado. Voy a croquis, y luego hacer algunos comentarios filosóficos.

Vamos a empezar por probar la $6$ mapa de color teorema. Sin pérdida de generalidad, podemos asumir que todas las caras de nuestro gráfico son triangulares, ya que la adición de bordes simplemente hace una gráfica más difícil a color. (Estamos colorear los vértices.) Vamos $V$, $E$ y $F$ el número de vértices, aristas y caras. Cada borde es de dos caras y cada cara tiene tres bordes, por lo $F=(2/3)E$. Tenemos $V-E+F=2$ por Euler de la relación, por lo $V=E/3 +2$. Ya que la suma de todos los vértices de grado superior es de $2E$, el promedio de grado de un vértice es $2E/V = (2E)/(E/3 + 2) < 6$. Por lo que el grado medio es menos de $6$ y no debe ser un vértice $v$ grado $\leq 5$. Eliminar $v$, $6$-color el resto de la gráfica (por inducción), y agregar$v$. Desde el vértice tiene grado $\leq 5$, hay algunos colores que no fronteriza $v$, color $v$ ese color.

Para demostrar la $5$ mapa de color teorema requiere de una nueva idea. Encontrar el vértice $v$ como antes, el color del resto de la gráfica y agregarlo de nuevo. Pero tenemos un problema si el $v$ tiene el grado $5$, y sus vecinos, todos tienen diferentes colores. La idea de conseguir alrededor de esto es considerar los subdiagramas $G_{ij}$ consta de los vértices de colores $i$$j$, para los diferentes pares de $(i,j)$. Debido a $G_{ij}$ $G_{k \ell}$ no puede cruzar, para $i$, $j$, $k$ y $\ell$ distintos, algunos de estos gráficos deben ser desconectados. Teniendo en cuenta la finitely posible que muchos de los arreglos de estos gráficos, se ve que, en cada caso, se puede tomar algún componente de $G_{ij}$ y cambiar los colores $i$ $j$ en el componente con el fin de hacer $v$ tiene sólo $4$ colores diferentes de vecino. Véase, por ejemplo, la Wikipedia para más detalles.

El $4$ mapa de color teorema requiere el cambio de idea en el párrafo anterior, además de uno más idea. En lugar de mostrar que siempre hay un vértice de grado $3$, $4$ o $5$, una muestra que uno de un número finito de lista de configuraciones más grandes es inevitable. Esta lista tiende a tener 600-2000 miembros, dependiendo exactamente lo que copia de la prueba de leer. La idea de mostrar que esta lista es inevitable es un promedio argumento como el que he utilizado; el término técnico para la búsqueda se "descarga". Para cada uno de estos cientos de configuraciones, una quita de la gráfica, los colores, el resto, y analiza las posibles posiciones de los gráficos de $G_{ij}$. En cada caso se puede cambiar el color de algunos de los componentes de la $G_{ij}$ de tal manera que, cuando la configuración se vuelve a poner en el gráfico entero será engañosa.

Como yo lo entiendo, los ordenadores se utilizan de dos maneras. La menos interesante es que hay una rutina que comprueba que la descarga argumento es correcto, encuentra las posiciones posibles de la $G_{ij}$, y comprueba que se puede volver a colorear.

La más interesante es que, cuando la rutina en el párrafo anterior falla, el equipo perturba el desempeño de argumento, encuentra una nueva lista resultante de las configuraciones y lo intenta de nuevo. Se trata básicamente de un proceso genético, donde el equipo de ajustes de la descarga algoritmo hasta que encuentra una lista de las configuraciones que funciona.

El salto de fe que Appel y Haken fue para creer que hubo algunos lo suficientemente complejo para el desempeño del algoritmo, y algunos de la lista de configuraciones para que este procedimiento funcione, y que sólo había que buscar el tiempo suficiente. Desde entonces, esta búsqueda se ha implementado muchas veces, con los detalles del algoritmo de búsqueda diferentes en cada caso, y las diferentes soluciones se han encontrado.

A mi mente, todo esto me recuerda a una evolución paralela. Hay un montón de maneras de hacer un ala, y si deja a un organismo el tiempo suficiente en un entorno en el que las recompensas de vuelo, a continuación, se va a desarrollar. Pero todas esas formas son tan complejos que un humano intellegence no podía ingeniero de ellos. Del mismo modo, hay un montón de desempeño de los algoritmos que probar el $4$ mapa de color teorema, pero todos ellos son demasiado extraño para un humano matemático para encontrar directamente.

2voto

Collin K Puntos 6535

Tal vez este relato expositivo de una prueba "mejorada" del teorema 4 colores le ayudará a:

http://People.Math.gatech.edu/~Thomas/FC/fourcolor.html

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X