Colorear gráfico
En teoría de grafos, el coloreado de grafos es un caso especial de etiquetado de grafos ; es una asignación de etiquetas tradicionalmente llamadas "colores" a elementos de un gráfico sujeto a ciertas restricciones. En su forma más simple, es una forma de colorear los vértices de un gráfico de modo que no haya dos vértices adyacentes del mismo color; esto se llama coloración de vértices . De manera similar, un coloreado de bordes asigna un color a cada borde para que no haya dos bordes adyacentes del mismo color, y un coloreado de caras de un gráfico plano asigna un color a cada cara o región para que no haya dos caras que compartan un límite que tengan el mismo color. el mismo color.
La coloración de vértices se usa a menudo para introducir problemas de coloración de gráficos, ya que otros problemas de coloración se pueden transformar en una instancia de coloración de vértices. Por ejemplo, la coloración de los bordes de un gráfico es solo la coloración de los vértices de su gráfico de líneas , y la coloración de las caras de un gráfico plano es solo la coloración de los vértices de su doble . Sin embargo, los problemas de coloración que no son de vértices a menudo se plantean y estudian tal cual. Esto es en parte pedagógico y en parte porque algunos problemas se estudian mejor en su forma sin vértice, como en el caso del coloreado de bordes.
La convención de usar colores tiene su origen en colorear los países de un mapa , donde cada cara está literalmente coloreada. Esto se generalizó para colorear las caras de un gráfico incrustado en el plano. Por dualidad plana pasó a colorear los vértices, y de esta forma se generaliza a todos los grafos. En las representaciones matemáticas y por computadora, es típico usar los primeros números enteros positivos o no negativos como "colores". En general, se puede utilizar cualquier conjunto finito como "conjunto de colores". La naturaleza del problema de coloración depende de la cantidad de colores, pero no de lo que son.
La coloración de gráficos disfruta de muchas aplicaciones prácticas, así como de desafíos teóricos. Además de los tipos clásicos de problemas, también se pueden establecer diferentes limitaciones en el gráfico, o en la forma en que se asigna un color, o incluso en el color mismo. Incluso ha alcanzado popularidad entre el público en general en la forma del popular rompecabezas numérico Sudoku . La coloración de gráficos sigue siendo un campo de investigación muy activo.
Los primeros resultados sobre la coloración de grafos tratan casi exclusivamente de grafos planos en forma de coloración de mapas . Mientras intentaba colorear un mapa de los condados de Inglaterra, Francis Guthrie postuló la conjetura de los cuatro colores , y señaló que cuatro colores eran suficientes para colorear el mapa, de modo que ninguna región que compartía una frontera común recibiera el mismo color. El hermano de Guthrie le pasó la pregunta a su profesor de matemáticas Augustus de Morgan en el University College , quien la mencionó en una carta a William Hamilton en 1852. Arthur Cayley planteó el problema en una reunión de la Sociedad Matemática de Londres.en 1879. El mismo año, Alfred Kempe publicó un artículo que pretendía establecer el resultado, y durante una década se consideró resuelto el problema de los cuatro colores. Por su logro, Kempe fue elegido miembro de la Royal Society y más tarde presidente de la London Mathematical Society. [1]
En 1890, Heawood señaló que el argumento de Kempe estaba equivocado. Sin embargo, en ese artículo demostró el teorema de los cinco colores , diciendo que cada mapa plano puede ser coloreado con no más de cinco colores, usando ideas de Kempe. En el siglo siguiente, se desarrollaron una gran cantidad de trabajos y teorías para reducir el número de colores a cuatro, hasta que el teorema de los cuatro colores fue finalmente demostrado en 1976 por Kenneth Appel y Wolfgang Haken . La prueba volvió a las ideas de Heawood y Kempe y en gran medida descartó los desarrollos intermedios. [2] La prueba del teorema de los cuatro colores también es notable por ser la primera prueba importante asistida por computadora.
