주어진 함수를 활용한 3색 채색 그래프

Question

출력을 true(해당 가장자리와 정점이 있는 그래프가 3가지 색상으로 표시될 수 있는 경우) 또는 false(그렇지 않은 경우)로 제공하는 three_colorability(n,E) 함수가 있습니다.(! 이미 채색 된 것을 알기위한 매개 변수는 없습니다) 우리는이 기능이 선형 시간 복잡성에서 작동한다고 가정합니다.

다항식 시간에 작동하는 주어진 함수를 사용하여 주어진 무향 그래프 G의 3색 알고리즘을 만들어야 합니다.

나는 이것에 대한 해결책을 찾을 수 없습니다.

Answer 1

이름이 지정된 3개의 새 노드를 추가합니다. C1, C2 그리고 C3 색상으로 표현됩니다.새 노드 사이에 가장자리 추가 (C1,C2), (C2,C3) 그리고 (C1,C3).만약에 three_colorability(V,E) 보다 사실이다 three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)}) 또한 사실이다.

각 (원본) 정점에 대해 v, three_colorability() 두 개의 간선이 추가된 그래프 중 적어도 하나에 대해 true를 반환합니다. {(v,C1), (v,C2), (v,C3)}.예:만약에 three_colorability() 간선이 추가된 그래프에 대해 true를 반환합니다. {(v,C2), (v,C3)}, 그것은 다음을 의미합니다 v 1번 색상으로 색칠할 수 있습니다.

모든 정점의 색상을 찾으려면 정점 색상을 점진적으로 찾아 그래프에 이 2개의 가장자리를 추가하세요.