Coloració de grafos

En Teoria de grafos, la coloració de grafos és un cas especial d'etiquetage de grafos; és una assignació d'etiquetes anomenades colors a elements del grafo. De manera simple, una coloració dels vèrtiços d'un grafo tal que cap vèrtiç adjacent compartixca el mateix color és cridat vèrtiç coloració. Similarmente, una aresta coloració assigna colors a cada aresta tal que arestes adjacents no compartixquen el mateix color, i una coloració de cares d'un grafo pla a l'assignació d'un color a cada cara o regió tal que cares que compartixquen una frontera comuna tinguen colors diferents. El vèrtiç coloració és el punt d'inici de la coloració, i els atres problemes de coloreo poden ser transformats a una versió en vèrtiços. Per eixemple, una aresta coloració d'un grafo és justament una vèrtiç coloració del grafo llínea respectiu, i una coloració de cares d'un grafo pla és una vèrtiç coloració del grafo dual.

La convenció d'usar colors s'origina de la coloració de països d'un mapa, a on a cada cara se li assigna un color. Açò va ser generalisat a la coloració de cares de grafos immersos en el pla. En representacions matemàtiques i computacionals s'utilisen típicament sancers no negatius com a colors. En general es pot usar un conjunt finito com a conjunt de colors. La naturalea del problema de coloració solament depén del número de colors, sense importar cuales siguen o la seua orde.

Història

Els primers resultats sobre coloració de grafos tractaven exclusivament sobre grafos planars en forma de coloració de mapes. Fins que un dia de 1852 Francis Guthrie mentres intentava colorear un mapa d'Anglaterra, va postular la conjectura dels 4 colors, senyalant que 4 colors eren suficients per a colorear el mapa de manera tal que les regions que compartiren una vora comuna no reben el mateix color. Guthrie va mostrar el problema al seu germà Frederick qui a la seua volta ensenya el problema al seu professor de matemàtiques Augustus de Morgan en l'University College de Londres, qui al vore's desesperat per no poder resoldre-ho, menciona en una carta a William Hamilton eixe mateix dia. Arthur Cayley envia el problema a la London Mathematical Society i en 1879 Alfred Kempe publica un paper que assegurava resoldre el problema i per una década el problema dels 4 colors es va considerar resolt. Per la seua contribució Kempe va ser elegit Fellow de la Royal Society i posteriorment president de la London Mathematical Society.

En 1890, Heawood va descobrir que l'argument de Kempe contenia un error, en eixe artícul va provar la teorema dels 5 colors, dient que cada mapa pla pot ser coloreado en, a lo més 5 colors, no obstant, seguia usant idees de Kempe. En el següent sigle, noves teories varen ser desenrollades per a reduir el número de colors a quatre, fins que la teorema dels 4 colors va ser finalment provat (en ajuda de la computació) en 1976 per Kenneth Appel i Wolfgang Haken.

La coloració de grafos ha segut estudiada com un problema algorítmic des de 1970: el problema del número cromàtic és el problema 21 de Karp NP-complet de 1972, i aproximadament al mateix temps varis algoritmes de temps exponencial varen ser desenrollats basats en backtraking i en l'eliminació i MALA ntracción de Zykov (1949). Una de les principals aplicacions de la coloració de grafos és l'assignació de registres en compiladors, introduïda en 1981.

Definicions i terminologia

Vèrtiç coloració

La vèrtiç coloració (o simplement coloració) és l'assignació dels vèrtiços d'un grafo en colors tal que dos vèrtiços que compartixen la mateixa aresta tinguen colors diferents. Un grafo en bucles no pot ser coloreado; solament es consideren grafos simples.

La terminologia d'usar colors per a etiquetar vèrtiços prové del problema de colorear mapes. Les etiquetes com a roig o blau són solament utilisades quan el número de colors és menut, i normalment els colors estan representats pels sancers {1, 2, 3, …}.

Una coloració que usa com a molt k colores es diu k-coloració (pròpia). El menor número de colors necessari per a colorear un grafo G es diu número cromàtic i es denota com χ(G). Un grafo al que pot ser assignada una k-coloració (pròpia) és k-coloreable, i és k-cromàtic si el seu número cromàtic és exactament k. Un subconjunt de vèrtiços assignats en el mateix color es diu una classe de color. Cada classe forma un conjunt independent. Açò és, una k-coloració és lo mateix que una partició del conjunt de vèrtiços en k conjunts independents. Els térmens k-partito i k-coloreable tenen el mateix significat.

Polinomi cromàtic

El polinomi cromàtic conta el número de maneres en les quals pot ser coloreado un grafo usant no més que un número de colors donat. Per eixemple, usant 3 colors, el grafo en l'image de la dreta pot ser coloreado de 12 formes distintes. En sol 2 colors, no pot ser coloreado. En 4 colors, pot ser coloreado de 24+4*12 maneres distintes: usant els quatre colors junts, hi ha 4!= 24 coloració vàlides (tota assignació de quatre colors a algun grafo de quatre vèrtiços és una coloració pròpia); i per a cada elecció de tres dels quatre colors, hi ha 12 3-coloració vàlides. Aixina que, per al grafo de l'eixemple, una taula de números de coloració vàlides pot començar com esta:

Colors disponibles	1	2	3	4	…
Número de coloració	0	0	12	72	…

El polinomi cromàtic és una funció p(G, t) que conta el número de t-coloració de G. com el nom ho indica per a un grafo G la funció és un polinomi en t. per al grafo de l'eixemple, P(G, t)= t(t-1)^2 (t-2) i P(G,4)=72

Polinomis cromàtics d'alguns grafos.
Triàngul K₃	$t (t - 1) (t - 2)$
Grafo complet K_n	$t (t - 1) (t - 2) \dots (t - (n - 1))$
Arbre en n vèrtiços	$t (t - 1)^{n - 1}$
Cicle C_n	$(t - 1)^{n} + (- 1)^{n} (t - 1)$
Grafo de Petersen	$t (t - 1) (t - 2) (t^{7} - 12 t^{6} + 67 t^{5} - 230 t^{4} + 529 t^{3} - 814 t^{2} + 775 t - 352)$

Aresta coloració

Una aresta coloració d'un grafo, és una coloració de les arestes, denotada com l'assignació de colors a arestes tal que arestes incidents tinguen un color distint. Una aresta coloració en k colores és cridada k-aresta-coloració i és equivalent al problema de particionar el conjunt d'arestes en k emparejamientos. El menor número de colors necessaris per a un aresta coloració d'un grafo G és l'índex cromàtic o número cromàtic d'arestes. Una coloració Tait és una 3-aresta-coloració d'un grafo cúbic. La teorema dels quatre colors és equivalent a que cada grafo cúbic sense ponts admet una coloració Tait.

Vore també

Este artícul conté una traducció derivada de «Coloración de grafos» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.