Coloração de gráfico de 3 cores com o uso da função fornecida

Question

Eu tenho a função three_colorability(n,E) que fornece saída verdadeira (quando o gráfico com essas arestas e vértices pode ser colorido com 3 cores) ou falso (se não).(! Não há parâmetro para saber o que já foi colorido), assumimos que essa função funciona na complexidade do tempo linear.

Eu tenho que fazer um algoritmo de 3 cores do gráfico não direcionado G fornecido com o uso da função fornecida que funcionará em tempo polinomial.

Não consigo chegar à solução para isso.

Answer 1

Adicione 3 novos nós, nomeados C1, C2 e C3 pela cor que eles representam.Adicione arestas entre novos nós (C1,C2), (C2,C3) e (C1,C3).Se three_colorability(V,E) é verdade do que three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)}) também é verdade.

Para cada vértice (original) v, three_colorability() retorna verdadeiro para pelo menos um dos gráficos com duas arestas adicionadas {(v,C1), (v,C2), (v,C3)}.Por exemplo.se three_colorability() retorna verdadeiro para gráfico com arestas adicionadas {(v,C2), (v,C3)}, significa que v pode ser colorido com a cor 1.

Para encontrar a cor de todos os vértices, encontre gradualmente a cor do vértice e adicione essas 2 arestas em um gráfico.