Grafique la coloración de 3 colores con el uso de la función dada

Question

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.

Answer 1

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.