1
그래프를 사용하여 문제가 NP- 완전 함을 증명할 수있는 3 가지 색상이 필요하지만 주어진 그래프가 3 색으로 표시 될 때 확실하지 않습니다. 그래프에 삼각형의 모든 3 정점에 연결된 노드가 없다면 생각합니다.하지만 확실하지 않습니다. 맞습니까?주어진 그래프를 3 색으로 표시 할 수 있습니까?
A
답변
0
아니요 노드가 삼각형의 세 노드에 모두 연결되어 있으면 (이는 "크기가 4 인 클록이 더 복잡합니다") 충분하지만 일 수도 있지만 그래프가 아닌 경우는 일 수 있습니다. 3 색 가능. 그래프는 예를 들어 크기 4.
의 파벌을 가진 다른 이유로 3 겉치레하지있을 수 있습니다 :
는
이 3 겉치레 아니다. 증명 : 바깥 쪽의 5 사이클은 2 색 가능하지 않으며 중간 꼭지점을 위해 여분의 색이 필요합니다.