다항식 시간에 3 가지 색상의 그래프를 채울 수 있습니까? 나는 그 색을 2
색을 가진 그래프를 색칠하지만 3 가지 다른 색 (두 개의 꼭지점은
동색)이 아닌 그래프를 색칠하는 것은 np-hard입니다. 그러나 말하는 마법 상자가 있는지 궁금합니다. '예'에 대한 '
그래프는 다항식 시간에 3-colourable입니까?'라고 말하면 '예'라고 대답하면 어떻게 되겠습니까?
다항식 시간? 어떤 아이디어?그래프의 3 색 (다항식 시간)?
빨간색/녹색/파란색이라는 3 개의 새로운 정점을 그래프에 추가합니다. 각 그래프에는 다른 2 개는 연결되지만 다른 것은 표시되지 않습니다.
이 과정이 끝나면 각 vert 전의.
이것은 O (N * magic)입니다. 여기서 magic은 마법 상자의 복잡성입니다.
두 인접 꼭지점이 동일한 색상을 가져야합니다. – user3787061
왜이 알고리즘이 효과가 있는지 설명해 주시겠습니까? 꼭지점의 색상을 결정하기 전에 원래의 그래프에서 가장자리를 보지 않았기 때문에 혼란 스럽습니다. 따라서 원본 그래프의 두 인접 꼭지점이 색상을 공유하지 않는다는 것을 어떻게 확신 할 수 있습니까? – twinlakes
@twinlakes "결과 그래프"는 지금까지 작성한 그래프와 원본 그래프의 모든 가장자리로 구성됩니다. 이것은 알고리즘이 각 단계에서 원래 그래프의 가장자리를 검사한다는 것을 의미합니다. –
정확하게 이해할 수 있습니까? 다항식 시간에 특정 그래프를 3 색으로 만들 수있는 그래프의 속성과 그 알고리즘을 알고 싶습니까? – delnan
@delnan이 마법 상자를 사용하여 무 방향성 그래프 G의 3 색을 다항식 시간에서 찾으려고합니다. (즉, 그래프의 각 꼭지점에 빨강, 초록 또는 파랑을 할당하여 두 개의 인접한 꼭지점이 같은 색이 아니어야합니다.) – user3787061
그리고 마법 상자가 P = NP를 암시하는지 여부를 분별하려고합니다. 그래서 당신의 질문은 "P에서 방향없는 그래프를 3 색으로 채 웁니까?"입니다. – delnan