Coloração de gráfico de 3 cores com o uso da função fornecida
-
20-12-2019 - |
Pergunta
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.
Solução
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.