En matemáticas , una cadena de Kempe es un dispositivo que se utiliza principalmente en el estudio del teorema de los cuatro colores . Intuitivamente, es una cadena de puntos conectados en un gráfico con colores alternos.
Historia
Las cadenas de Kempe fueron utilizadas por primera vez por Alfred Kempe en su intento de demostración del teorema de los cuatro colores. [1] Aunque su demostración resultó ser incompleta, el método de las cadenas de Kempe es crucial para las demostraciones modernas exitosas (Appel & Haken, Robertson et al., Etc.). Además, el método se utiliza en la demostración del teorema de los cinco colores de Percy John Heawood , una forma más débil del teorema de los cuatro colores. [1]
Definicion formal
El término "cadena de Kempe" se utiliza de dos formas diferentes pero relacionadas.
Suponga que G es una gráfica con un conjunto de vértices V , y se nos da una función para colorear
donde S es un conjunto finito de colores, que contiene al menos dos colores distintos a y b . Si v es un vértice con el color de una , entonces el ( un , b ) cadena -Kempe de G que contiene v es la máxima subconjunto de conectado V que contiene V y cuyos vértices son todos de color, ya sea una o b .
La definición anterior es con la que trabajó Kempe. Normalmente, el conjunto S tiene cuatro elementos (los cuatro colores del teorema de los cuatro colores), y c es un color adecuado , es decir, a cada par de vértices adyacentes en V se le asignan colores distintos.
Una definición más general, que se utiliza en las demostraciones modernas basadas en computadora del teorema de los cuatro colores, es la siguiente. Supongamos de nuevo que G es un gráfico, con un conjunto de aristas E , y esta vez tenemos una función de coloración
Si e es un color borde asignado una , entonces el ( un , b ) cadena -Kempe de G que contiene e es la máxima conectado subconjunto de E que contiene correos y cuyos bordes son todos de color, ya sea una o b .
Esta segunda definición se aplica típicamente donde S tiene tres elementos, por ejemplo un , b y c , y donde V es un gráfico cúbico , es decir, cada vértice tiene tres bordes de incidentes. Si dicho gráfico está correctamente coloreado, entonces cada vértice debe tener bordes de tres colores distintos, y las cadenas de Kempe terminan siendo caminos , lo cual es más simple que en el caso de la primera definición.
En términos de mapas
Aplicación al teorema de los cuatro colores
En el teorema de los cuatro colores, Kempe pudo demostrar que todas las gráficas tienen necesariamente un vértice de cinco o menos, o contienen un vértice que toca otros cinco vértices, llamados sus vecinos . Como tal, para probar el teorema de los cuatro colores, es suficiente probar que los vértices de cinco o menos eran todos de cuatro colores. Kempe pudo probar el caso del grado cuatro y dar una prueba parcial del grado cinco utilizando cadenas de Kempe. [2]
En este caso, las cadenas de Kempe se utilizan para demostrar la idea de que ningún vértice tiene que tocar cuatro colores diferentes de él mismo, es decir, tener un grado 4. Primero, se puede crear un gráfico con un vértice v y cuatro vértices como vecinos. Si quitamos el vértice v , podemos cuatricromar los vértices restantes. Podemos establecer los colores como (en el sentido de las agujas del reloj) rojo, amarillo, azul y verde. En esta situación, puede haber una cadena de Kempe que une a los vecinos rojo y azul o una cadena de Kempe que une a los vecinos verde y amarillo, pero no ambos, ya que estos dos caminos necesariamente se cruzarían y el vértice donde se cruzan no se puede colorear. Suponiendo que la cadena Kempe está conectando a los vecinos verde y amarillo, el rojo y el azul no deben tener necesariamente una cadena Kempe entre ellos. Entonces, al volver a colocar el vértice v original en el gráfico, podemos simplemente invertir los colores del vértice rojo y sus vecinos (incluido el vértice rojo, haciéndolo azul) y colorear el vértice v como rojo. Esto da como resultado un gráfico de cuatro colores. [3]
Otras aplicaciones
Las cadenas de Kempe se han utilizado para resolver problemas en la extensión del color . [4] [5]
Referencias
- ^ a b "Matemáticas coloridas: Parte I" . Sociedad Matemática Estadounidense . Consultado el 10 de julio de 2020 .
- ^ Appel, Kenneth; Haken, Wolfgang (1989), Every Planar Map is Four-Colorable, Contemporary Mathematics, 98, Con la colaboración de J. Koch., Providence, RI: American Mathematical Society, doi: 10.1090 / conm / 098, ISBN 0-8218-5103-9 , SEÑOR 1025335
- ^ Kempe, AB (1879), "Sobre el problema geográfico de los cuatro colores", American Journal of Mathematics, The Johns Hopkins University Press, 2 (3): 193-220
- ^ Albertson, MO (1998). "No se puede pintar a sí mismo en una esquina". Revista de Teoría Combinatoria, Serie B . 73 (2): 189-194. doi : 10.1006 / jctb.1998.1827 .
- ^ Albertson, MO; Moore, EH (1999). "Ampliación de la coloración de los gráficos". Revista de Teoría Combinatoria, Serie B . 77 : 83–95. doi : 10.1006 / jctb.1999.1913 .