Grafique la coloración de 3 colores con el uso de la función dada
-
20-12-2019 - |
Pregunta
Tengo la función three_colorability(n,E) que da como resultado verdadero (cuando el gráfico con esos bordes y vértices se puede colorear con 3 colores) o falso (si no).(!
Tengo que crear un algoritmo de 3 colores para el gráfico no dirigido G dado con el uso de la función dada que funcionará en tiempo polinomial.
No puedo llegar a la solución a esto.
Solución
Agregue 3 nuevos nodos, llamados C1
, C2
y C3
por el color que representan.Agregar bordes entre nuevos nodos (C1,C2)
, (C2,C3)
y (C1,C3)
.Si three_colorability(V,E)
es verdad que three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)})
también es cierto.
Para cada vértice (original) v
, three_colorability()
devuelve verdadero para al menos uno de los gráficos con dos bordes agregados {(v,C1), (v,C2), (v,C3)}
.P.ej.si three_colorability()
devuelve verdadero para un gráfico con aristas agregadas {(v,C2), (v,C3)}
, esto significa que v
Se puede colorear con el color 1.
Para encontrar el color de todos los vértices, busque incrementalmente el color de los vértices y agregue estos 2 bordes en un gráfico.