En la teoría de grafos , la coloración 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 sujetos a ciertas restricciones. En su forma más simple, es una forma de colorear los vértices de un gráfico de manera que no haya dos vértices adyacentes del mismo color; Esto se llama coloración de vértice . Del mismo modo, un color de borde asigna un color a cada borde para que no haya dos bordes adyacentes del mismo color, y un color de cara 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 generalmente 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, un color de borde de un gráfico es solo un color de vértice de su gráfico de línea , y un color de cara de un gráfico plano es solo un color de vértice de su dual . Sin embargo, los problemas de coloración que no son vértices a menudo se expresan y estudian tal como están . Esto es en parte pedagógico y en parte porque algunos problemas se estudian mejor en su forma no vértice, como en el caso de la coloración de bordes.
La convención de usar colores se origina al 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 se volvió coloreando los vértices, y de esta forma se generaliza a todos los gráficos. En las representaciones matemáticas e informáticas, es típico usar los primeros enteros positivos o no negativos como "colores". En general, se puede usar 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 gráfica disfruta de muchas aplicaciones prácticas, así como 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 de números Sudoku . La coloración de gráficos sigue siendo un campo de investigación muy activo.
Historia [ editar ]
Los primeros resultados sobre la coloración de gráficos tratan casi exclusivamente con gráficas planas en forma de coloración de mapas . Mientras intentaba colorear un mapa de los condados de Inglaterra, Francis Guthrie postuló la conjetura de cuatro colores , señalando que cuatro colores eran suficientes para colorear el mapa de modo que ninguna región que compartiera un borde 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 lo mencionó en una carta a William Hamilton en 1852. Arthur Cayley planteó el problema en una reunión de la London Mathematical Societyen 1879. El mismo año, Alfred Kempe publicó un artículo que afirmaba 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 documento demostró el teorema de los cinco colores , diciendo que cada mapa plano puede ser coloreado con no más de cinco colores, utilizando ideas de Kempe. En el siglo siguiente, se desarrolló una gran cantidad de trabajo y teorías para reducir el número de colores a cuatro, hasta que Kenneth Appel y Wolfgang Haken probaron finalmente el teorema de los cuatro colores en 1976 . La prueba se remonta a las ideas de Heawood y Kempe y en gran medida ignora los desarrollos que intervienen. [2] La prueba del teorema de los cuatro colores también es notable por ser la primera prueba importante asistida por computadora.
En 1912, George David Birkhoff introdujo el polinomio cromático para estudiar los problemas de coloración, que Tutte generalizó al polinomio de Tutte , estructuras importantes en la teoría de grafos algebraicos . Kempe ya había llamado la atención sobre el caso general, no plano en 1879, [3] y muchos resultados sobre generalizaciones de coloración de gráfico plano en superficies de orden superior seguido a principios del siglo XX.
En 1960, Claude Berge formuló otra conjetura sobre la coloración gráfica, la conjetura gráfica fuerte y perfecta , originalmente motivada por un concepto teórico de la información llamado capacidad de error cero de un gráfico introducido por Shannon . La conjetura quedó sin resolver durante 40 años, hasta que se estableció como el célebre teorema fuerte perfecta gráfico por Chudnovsky , Robertson , Seymour , y Thomas en 2002.
La coloración de gráficos se ha estudiado como un problema algorítmico desde principios de la década de 1970: el problema del número cromático es uno de los 21 problemas completos de NP de Karp de 1972, y aproximadamente al mismo tiempo se desarrollaron varios algoritmos de tiempo exponencial basados en el retroceso y la eliminación -recurrencia de la contracción de Zykov (1949) . Una de las principales aplicaciones de la coloración de gráficos, la asignación de registros en compiladores, se introdujo en 1981.
Definición y terminología [ editar ]
Coloración de vértices [ editar ]
Cuando se usa sin ninguna calificación, una coloración de un gráfico es casi siempre una coloración de vértice adecuada , es decir, un etiquetado de los vértices del gráfico con colores de modo que no haya dos vértices que compartan el mismo borde con el mismo color. Dado que un vértice con un bucle (es decir, una conexión directamente de vuelta a sí mismo) nunca podría tener el color adecuado, se entiende que los gráficos en este contexto no tienen bucles.
La terminología del uso de colores para las etiquetas de vértices se remonta al color del mapa. Las etiquetas como rojo y azul solo se usan cuando el número de colores es pequeño, y normalmente se entiende que las etiquetas se extraen de los enteros {1, 2, 3, ...}.
Una coloración utilizando en la mayoría de k colores se llama un (adecuado) k -Coloreado . El número más pequeño de colores necesarios para colorear un gráfico G se llama su número cromático , y a menudo se denota χ ( G ). A veces se usa γ ( G ), ya que χ ( G ) también se usa para denotar la característica de Euler de un gráfico. Un gráfico al que se le puede asignar un color k (apropiado) es k -colorable , y es k -cromático si su número cromático es exactamente k . Un subconjunto de vértices asignado al mismo color se denomina clase de color. , cada clase forma un conjunto independiente . Por lo tanto, un k- coloring es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k-partite y k-colorable tienen el mismo significado.
Polinomio cromático [ editar ]
El polinomio cromático cuenta el número de formas en que se puede colorear un gráfico utilizando no más de un número dado de colores. Por ejemplo, usando tres colores, el gráfico en la imagen adyacente se puede colorear de 12 maneras. Con solo dos colores, no se puede colorear en absoluto. Con cuatro colores, se puede colorear de 24 + 4⋅12 = 72 formas: ¡usando los cuatro colores, hay 4! = 24 colores válidos ( cada asignación de cuatro colores a cualquier gráfico de 4 vértices es un color apropiado); y para cada elección de tres de los cuatro colores, hay 12 colores válidos de 3 colores. Entonces, para el gráfico en el ejemplo, una tabla del número de colores válidos comenzaría así:
| Colores disponibles | 1 | 2 | 3 | 4 4 | ... |
| Numero de colorantes | 0 0 | 0 0 | 12 | 72 | ... |
El polinomio cromático es una función P ( G , T ) que cuenta el número de t -colorings de G . Como su nombre indica, para una G dada, la función es de hecho un polinomio en t . Para el gráfico de ejemplo, P ( G , t ) = t ( t - 1) 2 ( t - 2), y de hecho P ( G , 4) = 72.
El polinomio cromático incluye al menos tanta información sobre la colorabilidad de G como el número cromático. De hecho, χ es el entero positivo más pequeño que no es una raíz del polinomio cromático
| Triángulo K 3 | |
| Gráfico completo K n | |
| Árbol con n vértices | |
| Ciclo C n | |
| Gráfico de Petersen |
Coloración de bordes [ editar ]
Un color de borde de un gráfico es un color apropiado de los bordes , lo que significa una asignación de colores a los bordes para que ningún vértice incida en dos bordes del mismo color. Una coloración de borde con k colores se llama k -edge-coloring y es equivalente al problema de dividir el conjunto de bordes en k coincidencias . El número más pequeño de colores necesarios para una coloración de borde de un gráfico G es el índice cromático , o número cromático de borde , χ ′ ( G ). Una coloración Tait es una coloración de 3 bordes de un gráfico cúbico . losEl teorema de cuatro colores es equivalente a la afirmación de que cada gráfico cúbico plano sin puente admite una coloración Tait.
Coloración total [ editar ]
La coloración total es un tipo de coloración en los vértices y bordes de un gráfico. Cuando se usa sin ninguna calificación, siempre se supone que una coloración total es adecuada en el sentido de que no se asignan vértices adyacentes, ni bordes adyacentes, y ningún borde y sus vértices finales del mismo color. El número cromático total χ ″ (G) de un gráfico G es el menor número de colores necesarios en cualquier coloración total de G.
Coloración sin etiqueta [ editar ]
Un color sin etiquetar de un gráfico es una órbita de un color bajo la acción del grupo de automorfismo del gráfico. Si interpretamos una coloración de un gráfico en vértices como un vector en , la acción de un automorfismo es una permutación de los coeficientes de la coloración. Hay análogos de los polinomios cromáticos que cuentan el número de colorantes no etiquetados de un gráfico de un conjunto de colores finitos dado.
No hay comentarios:
Publicar un comentario