Upload
roberta-vejar
View
220
Download
0
Embed Size (px)
Citation preview
Coloración de Grafos Planos
Huberto Ayanegui SantiagoHuberto Ayanegui Santiago
José María Vega RamosJosé María Vega Ramos
Enrique Ayala FrancoEnrique Ayala Franco
Avance del proyecto de medio término
15 de marzo de 2001
Coloración de grafosColoración de grafos
Consiste en asignar colores a los vértices de un grafo no dirigido con la condición que para todo par de vértices adyacentes estos no sean coloreados del mismo color.
AplicacionesAplicaciones
Grafos PlanosGrafos PlanosDefinición:
Un grafo finito no dirigido se denomina plano, si puede ser dibujado sobre una superficie plana de forma que sus aristas se intersecten únicamente en los vértices.
Grafos PlanosGrafos Planos
Ejemplos:
Teorema de los 4 coloresTeorema de los 4 coloresCualquier grafo plano puede ser coloreado con no más de cuatro colores, de modo que ningún par de vértices adyacentes tengan el mismo color.
Francis Guthrie (1850)
El teorema fue comprobado por Appel y Haken (1976)
Teorema de los 4 coloresTeorema de los 4 colores
Solución propuestaSolución propuesta
Grafo plano
Matriz de adyacencias
Reducción a FNC´s
Davis &Putnam
Solución
Interpretación
4
1
5
32
MATRIZ DE ADYACENCIASMATRIZ DE ADYACENCIAS
X1X1 X2X2 X3X3 X4X4 X5X5
X1X1 11 11 11 11
X2X2 11 11
X3X3 11 11
X4X4 11 11 11
X5X5 11 11 11
Reducción del Grafo a CláusulasReducción del Grafo a Cláusulas
Para el Grafo mostrado tenemos 5 vértices y 4 colores posibles para colorearlo
Definiremos una proposición de la forma:
Xi,j
donde:
i = # de vertice j = # de color
El primer paso es garantizar que cada vértice tenga al menos un color.
Entonces proponemos cláusulas de esta forma:Entonces proponemos cláusulas de esta forma:
XX1111 v X v X1212 v X v X1313 v X v X1414
XX2121 v X v X2222 v X v X2323 v X v X2424
XX3131 v X v X3232 v X v X3333 v X v X3434
XX4141 v X v X4242 v X v X4343 v X v X4444
XX5151 v X v X5252 v X v X5353 v X v X5454
El segundo paso es garantizar que cada vértice tenga un solo color.Y las cláusulas tienen esta forma:Y las cláusulas tienen esta forma:
~X~X1111 v ~X v ~X1212 v ~X v ~X1313 v ~X v ~X1414
~X~X2121 v ~X v ~X2222 v ~X v ~X2323 v ~X v ~X2424
~X~X3131 v ~X v ~X3232 v ~X v ~X3333 v ~X v ~X3434
~X~X4141 v ~X v ~X4242 v ~X v ~X4343 v ~X v ~X4444
~X~X5151 v ~X v ~X5252 v ~X v ~X5353 v ~X v ~X5454
El Tercer Paso es garantizar que para cada dos vértices adyacentes no tengan el mismo color.
~X~X1111 v ~X v ~X2121
~X~X1212 v ~X v ~X2222
~X~X1313 v ~X v ~X2323
~X~X1414 v ~X v ~X2424
En la primera cláusula se indica que el vértice 1 adyacente al 2, no pueden tener el mismo color 1, y así susesivamente para cada par de vértices adyacentes
Al convertir a la Matriz FNC
• 0 = ~X0 = ~X• 1 = X1 = X• -1 = no hay asignación de verdad-1 = no hay asignación de verdad• -2 = proposición que fue eliminada -2 = proposición que fue eliminada
Consideraremos:
FNC en MatrizXX1111 XX1212 XX1313 XX1414 ............ XX3131 .......... XX5353 XX5454
CC11 11 11 11 11 -1-1 -1-1 -1-1
CC22 11 11 11 11 -1-1 -1-1 -1-1
CC33 11 11 11 11 -1-1 -1-1 -1-1
CC44 11 11 11 11 -1-1 -1-1 -1-1
CC55 11 11 11 11 -1-1 -1-1 -1-1
CC66 00 00 00 00 -1-1 -1-1 -1-1
........
CC2929 -1-1 -1-1 -1-1 -1-1 -1-1 00 -1-1
CC3030 -1-1 -1-1 -1-1 -1-1 -1-1 -1-1 00
Solución SATSolución SATfunction davis-putnam(in FORMULA : lista de cláusulas) reduce(FORMULA, VREDUCE) if FORMULA esta vacia then return VREDUCE; else if FORMULA contiene una clausula vacía then return "FAIL“ else begin escoge una variable V de FORMULA; VALUACION := davis-putnam(substituye(TRUE, V, FORMULA)) if VALUACION != FAIL then return agrega(V->TRUE, VREDUCE, VALUACION); VALUACION := davis-putnam(substituye(FALSE, V, FORMULA)) if VALUACION != FAIL then return agrega(V->FALSE, VREDUCE, VALUACION); return FAIL end endif end davis-putnam
Solución SATSolución SAT
function substituye(TF, V, FORMULA) For cada clausula C en FORMULA do if [C contiene a V y TF = TRUE] o [C contiene a ~V y TF = FALSE] then borrar C de FORMULA else if [C contiene a V y TF = FALSE] o [C contiene a ~V y TF = TRUE] then borrar V de C endif endFor return FORMULAend_substituye
Solución SATSolución SAT
Procedure Reduce(in out FORMULA, VREDUCE) VREDUCE := vacío;While exista una clausula C en FORMULA con solo una literal L IF L es una variable positiva V then FORMULA := sustitucion(VERDADERO, V, FORMULA) VREDUCE := cons(V-> TRUE, VREDUCE); Else IF L es la negacion de la variable V then FORMULA := sustitucion(FALSE,V,FORMULA) VREDUCE := cons(V-> FALSE, VREDUCE); EndIF EndWhile return(FORMULA)end_Reduce
4
1
5
32