버텍스 컬러링 알고리즘을 읽고 있습니다. 문제가 O (| V | + | E |)에서 풀릴 수 있음을 암시하는 BFS를 사용하여 문제를 해결할 수있는 방법을 설명하는 문서를 볼 수 있습니다. 그러나이 또한 NP 어려운 문제라고 언급 한 것을 볼 수 있습니다.왜 정점 채색은 NP 어려운가요?
?이 두 가지가 함께 맞는 어떻게 당신은 어떤 빛을 던져 주시겠습니까 여기
는 나에게 일반적인 경우 다항식처럼 보였다 내가 건너 온 알고리즘입니다 : 이 번호로 식별 각 색상 되세요. 노드로 시작하여 색상이 가장 적은 번호를 할당합니다 .BFS를 사용하여 각 이웃을 방문하십시오. 노드를 방문하는 동안 각 이웃의 색상을 확인하고 이웃에 할당되지 않은 최소 수의 색상을 지정하십시오 .BFS 접근법은 2 가지 색상에만 적용됩니다. 위의 기술이 2 가지 색상 이상으로 작동하지 않는 이유를 알 수 있습니다.
BFS를 사용하여 꼭지점 색상 지정의 특별한 경우 또는 근사값을 얻을 수 있습니다. 일반적인 문제는 NP-Complete이며 BFS는 모든 경우를 해결하지 못합니다. 저는 카운터 - 예를 들어보고 싶지만 알고리즘에 대한 설명이 부족합니다 - 착색 전략이 명확하지 않습니다.
예를 들어, BFS 의해 achieveable 간단한 착색) (BFS 의해 검색된 d(source,v)으로는, 정점의 소스로부터의 거리, 컬러 인 c(v) 여기) c(v) = d(source,v)이다.
2 색으로 색칠 할 수있는 A--B--C--D에는 적합하지 않지만이 솔루션은 4 색을 사용합니다.
BFS를 사용하는 알고리즘은 색 수가 고정되어 있지 않은 편안한 색의 정점 색칠 문제를 해결하며 k 색을 사용하여 그래프를 색칠하거나 최소값을 찾는 일반적인 NP 완전 문제에서 근사 해법으로 작동 할 수 있습니다 그래프를 색칠하는 데 사용할 수있는 색상 집합입니다.
일반적으로 BFS (bread-first search)를 생각할 때 나무에 적용하는 것으로 생각하지만 꼭지점 색은 나무 문제가 아니라 그래프 문제입니다. . 나는 다른 노드로 이동하기 전에 현재 노드에 인접한 모든 노드에 레이블이 지정된다는 규칙을 적용하여 BFS를 그래프에 적용 할 수 있다고 가정합니다.
첫째, 작동하지 않는 방법을 간단 가장 낮은 번호 순서를 사용하여 라벨 (라고 순차적 순서)의 기본적인 예를 살펴 :
우리가 시계 방향으로 노드 레이블을 경우 (A ~ J) 우리는 실제로이 그래프가 2 색으로 표시 될 때 4 색으로 끝납니다. 이제는 인접한 노드를 레이블링하는 우선 순위를 정하는 규칙이 두 가지 색으로 표시되기 때문에 작동합니다. 이 예에서
우리는 "나무"의 루트로를 선택하고, 그 자식이 먼저 수행하지만,이 규칙이 작동하지 않습니다 3-색소, 예를 들면 있습니다 B 및 C를 선택합니다. C보다 알파벳 순서가 낮기 때문에 자식 B을 선택하고 B 님의 자녀 모두를 수행합니다. 실제로 그래프가 3 색이 될 수있는 경우 4 색으로 마무리됩니다.
BFS의 특수 케이스는 [Wikipedia] (http://en.wikipedia.org/wiki/Vertex_colouring#Polynomial_time)에 따라 2 색으로 표시됩니다 (그러나 일반적으로 일반적인 경우에 대한 근사치로도 사용됨). 여기 – Dukeling
@amit 나에게 일반적인 경우 다항식 시간의 솔루션처럼 나타나 내가 건너 온 알고리즘입니다 - 숫자로 identiied 각 색상 되세요. 노드로 시작하여 최소 숫자로 색상을 지정하십시오. BFS를 사용하여 각 이웃을 방문하십시오. 노드를 방문하는 동안 각 이웃 노드의 색을 확인하고 이웃 노드 중 하나에도 할당되지 않은 번호를 할당합니다. 나는 2 개 이상의 색상이 실 거예요 작업이 @Aadith – Aadith
는 대부분의 그래프에 필요한 것보다 더 많은 색상을 필요로한다는 점에서 욕심 알고리즘과 최적의 이유를 uable입니다 –