En matemáticas , una cadena de Kempe es un mecanismo que se utiliza principalmente en el estudio del teorema de los cuatro colores . Intuitivamente, es una cadena conexa de vértices en un gráfico con colores alternados.
Las cadenas de Kempe fueron utilizadas por primera vez por Alfred Kempe en su intento de demostrar el teorema de los cuatro colores. [1] Aunque su prueba resultó incompleta, el método de las cadenas de Kempe es crucial para el éxito de las pruebas modernas válidas, como la primera exitosa de Kenneth Appel y Wolfgang Haken . [2] [3] Además, el método se utiliza en la prueba del teorema de los cinco colores de Percy John Heawood , una versión más débil pero más fácil de demostrar del teorema de los cuatro colores. [1]
El término "cadena de Kempe" se utiliza de dos maneras diferentes pero relacionadas.
Supongamos que G es un gráfico con un conjunto de vértices V , con una función de coloración dada
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 color a , entonces la cadena ( a , b )-Kempe de G que contiene a v es el subconjunto máximo conexo de V que contiene a v y cuyos vértices son todos de color a 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 una coloración propia , es decir, a cada par de vértices adyacentes en V se le asignan colores distintos. Con estas condiciones adicionales, a y b son dos de los cuatro colores disponibles, y cada elemento de la cadena ( a , b )-Kempe tiene vecinos en la cadena de solo el otro color.
Una definición más general, que se utiliza en las demostraciones informáticas modernas del teorema de los cuatro colores, es la siguiente. Supongamos de nuevo que G es un grafo, con un conjunto de aristas E , y esta vez tenemos una función de coloración
Si e es una arista a la que se le asigna el color a , entonces la cadena ( a , b )-Kempe de G que contiene a e es el subconjunto conexo máximo de E que contiene a e y cuyas aristas son todas de color a o b .
Esta segunda definición se aplica típicamente cuando S tiene tres elementos, digamos a , b y c , y donde V es un grafo cúbico , es decir, cada vértice tiene tres aristas incidentes. Si dicho grafo está coloreado correctamente, entonces cada vértice debe tener aristas 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 el teorema de los cuatro colores, Kempe pudo demostrar que todos los grafos tienen necesariamente un vértice de cinco o menos, o que contienen un vértice que toca otros cinco vértices, llamados sus vecinos . Por lo tanto, para demostrar el teorema de los cuatro colores, es suficiente demostrar que los vértices de cinco o menos eran todos de cuatro colores. Kempe pudo demostrar el caso de grado cuatro y dar una prueba parcial de grado cinco utilizando cadenas de Kempe. [4]
En este caso, se utilizan cadenas de Kempe para demostrar la idea de que ningún vértice de grado cuatro tiene que estar tocando cuatro colores distintos de sí mismo. Primero, se puede crear un grafo con un vértice v y cuatro vértices como vecinos. Si eliminamos el vértice v , podemos colorear con cuatro colores 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 una a los vecinos rojo y azul o una cadena de Kempe que una a los vecinos verde y amarillo, pero no ambas, ya que estos dos caminos se intersectarían necesariamente, y el vértice donde se intersecan no puede colorearse con rojo o azul y con verde o amarillo al mismo tiempo. Suponiendo que la cadena de Kempe está conectando a los vecinos verde y amarillo, el rojo y el azul necesariamente no deben tener una cadena de Kempe entre ellos. Por lo tanto, al colocar el vértice original v nuevamente en el gráfico, podemos simplemente invertir los colores del vértice rojo y sus vecinos (incluido el vértice rojo, que lo vuelve azul), lo que deja al vértice v con dos vecinos azules, uno verde y uno amarillo. Esto significa que v tiene solo tres colores distintos como vecinos y que ahora podemos colorear el vértice v como rojo. Esto da como resultado un gráfico de cuatro colores. [5]
Las cadenas de Kempe se han utilizado para resolver problemas de extensión de coloración . [6] [7] Las cadenas de Kempe se pueden utilizar para la asignación de registros . [ cita requerida ]
