그래프 색칠 과 NP - Completeness 
 May 5 , 2019 15 : 00 
 현실 의 여러 대상 들 은 그래프 로 추상 화 할 수 있 다 . 그래프 를 색칠 하 는 것 은 , 서로 인접 한 두 정점 이 같 은 색 을 같 지 않 도록 색칠 하 는 것 이 다 . 이 그래프 를 색칠 하 는 문제 는 , 다양 한 스 케 쥴 링 문제 혹은 컴파일러 의 레지스터 배치 , 패턴 매칭 , 시험 / 수업 시간표 작성 등 다양 한 문제 를 해결 할 수 있 다 . 이런 문제 들 이 다항 시간 안 에 검증 이 가능 하 지만 , 다항 시간 안 에 풀리 는지 는 밝혀 지 지 않 는 NP - Complete 문제 라는 것 을 알아보 자 . 
 그래프 의 색칠 
 우리 는 이 그래프 의 정점 들 을 색칠 하 려고 한다 . 이 정점 들 을 색칠 하 는 것 은 여러 가지 방법 이 있 을 수 있 겠 지만 , 일반 적 으로 는 정점 와 정점 가 인접 하 면 , 같 은 색 으로 칠 하 지 않 는 것 을 그래프 의 색칠 이 라고 한다 . 이렇게 가능 한 모든 색칠 중 에서 색 을 가장 적 게 쓸 때 , 사용 한 색 의 수 를 채색 수 라고 한다 . 수식 으로 는 함수 에 대해서 , 와 가 인접 하 면 를 만족 하 는 함수 가 존재 하 면 , 그래 프 는 가지 색 으로 색칠 이 가능 하 고 , 이런 중 에 가장 작 은 를 채색 수라 하 고 라고 표시 한다 . 예 를 들 면 , 아래 그림 은 위 그래프 를 3 가지 색 으로 칠 한 사진 이 다 . 이 그래프 는 2 가지 이하 의 색 으로 는 칠 할 수 없 다 . ( 0 과 2 와 4 는 서로 인접 하 는데 , 이 들 이 서로 다른 색 을 가져야 하 기 때문 이 다 . ) 그래서 이 그래프 의 채색 수 는 3 이 다 . 
 이 그래프 의 채색 수 를 찾 는 것 은 NP - Complete 이 라는 게 증명 되 어 있 다 . 일단 , 인지 판단 하 는 것 은 선형 시간 안 에 풀리 는 문제 이 다 . 우리 는 어떤 한 정점 의 색 을 정하 면 , 다른 인접 한 모든 정점 의 색 은 유일 하 게 정해진다 . 이 를 통해서 DFS 등 의 탐색 을 사용 하 면 이 그래프 가 두 가지 색 으로 칠 해 질 수 있 는지 , 즉 이분 그래프 인지 빠른 시간 안 에 확인 할 수 있 다 . 하지만 , 인지 판단 하 는 문제 부터 굉장히 어려운 문제 가 되 고 , NP - Complete 문제 가 된다 . 
 NP - Completness 증명 
 일단 우리 는 3 - SAT 문제 로 부 터 시작 할 것 이 다 . 어떤 명제 가 참 이 라는 것 을 울리 는 초록색 , 거짓 이 라는 것 을 빨간색 , 그리고 임의 로 사용 되 는 색 을 노란색 으로 표현 할 것 이 다 . ( 이 임의 로 사용 하 는 색 은 말 그대로 임의 로 사용 되 는 색 이 다 . ) 
 우리 는 이것 을 증명 할 때 여러 가젯 ( Gadget , 기계 부품 ) 을 사용 한다 . 이 가젯 들 은 , 문제 를 푸 는데 여러 가지 도움 을 준다 . 우리 는 참 과 거짓 을 그래프 의 색 으로 잘 옮기 려고 한다 . 
 일단 우리 는 , 그래프 의 각 정점 들 을 , 참인 빨간색 , 거짓 인 초록색 , 그리고 중간 에서 사용 되 는 색깔 인 노란색 으로 칠한 것 이 다 . 이렇게 서로 다른 3 개 의 색 을 가지 게 만드 는 것 은 서로 이어주 는 완전 그래프 를 만들 면 되 고 , 다음 과 같이 서로 다른 세 가지 색 이 칠 해진다 . 
 어떤 색 을 강제 하 는 방법 은 , 그 색 이 아닌 나머지 색 들 에 그래프 를 연결 하 면 된다 . 
 변수 를 표현 할 때 는 는 참 과 거짓 , 는 와 반대 되 는 참 , 거짓 을 가져야 한다 . 와 를 하나 의 정점 으로 만든다고 할 때 , 와 는 임의 로 사용 되 는 색 이 되 면 안 되 고 , 와 는 다른 색 이 어야 한다 . 이 조건 을 만족 하 는 색칠 법 은 두 가지 뿐 이 고 , 우리 가 원 하 는 답 이 된다 . 
 우리 는 와 가 있 을 때 를 표현 하 는 방법 을 만들 어야 한다 . 이 OR 게이트 를 구현 을 직접 하 는 것 은 매우 힘든 일 이 기 때문 에 우리 는 다음 의 가젯 을 이용 한다 . 
 이 가젯 을 이용 하 면 , 와 가 같 은 색 일 때 는 가 그 색 임 을 알 수 있 다 . 
 와 가 다른 색 일 때 는 가능 한 모든 색 이 될 수 있 다 . 
 그렇 기 때문 에 , 우리 가 만드 려는 는 두 색 이 둘 다 빨간 색인 케이스 가 아니 면 언제 든지 초록색 으로 칠 할 수 있 고 , or 게이트 와 비슷 한 일 을 할 수 있 다 . 
 그래서 이 or 게이트 를 두 개 연속 해서 이을 경우 에 는 , 셋 다 빨간 색인 경우 에 는 빨간색 이 강제 되 고 , 나머지 는 초록색 을 만들 수 있 는 or 게이트 가 된다 . 
 이렇게 여러 가젯 들 을 한 데 묶 으면 다음 과 같 은 그림 이 나오 고 , 이 그래프 를 색칠 해서 와 에 어떤 색 들 이 있 는지 를 알려 주 는 것 이 SAT 문제 를 푸 는 것 과 동치 이 기 때문 에 , 3 가지 색 으로 칠 할 수 있 는지 를 판단 하 는 문제 는 NP - Complete 문제 이 다 . 
 우리 는 그래프 색칠 문제 가 NP - Complete 인 것 을 증명 했 다 . 이것 은 그래프 색칠 문제 가 매우 어려운 문제 중 하나 이 며 , 다항 시간 알고리즘 이 없 을 것 이 라고 생각 되 는 문제 임 을 말 한다 . 이런 문제 를 풀 때 는 그래프 의 특징 들 을 잘 활용 하 여 적절 한 근사해 나 그래프 의 특징 을 이용 한 다른 해법 들 을 이용 하 는 게 좋 을 것 이 다 . 
 특별 한 정렬 알고리즘 들 2