가난한 지도 제작자

이번 활동에서 탐색한 지도 채색 문제는 본질적으로 특정한 지도를 채색하는데 필요한 최소색 숫자—2, 3, 4—를 찾는 것이다. 단지 4가지 색을 사용해서 어떤 지도도 채색될 수 있다는 추측은 1852년에 정립되었다. 하지만, 1976년이 되어서야 증명이 되었다. 컴퓨터 과학은 미해결된 문제로 가득차 있다. 네가지 색깔 정리가 연구자로부터 120년 이상 관심을 받을 후에야 증명되었다는 > 것을 알게되는 것은 수십년동안 해결책이 발견되지 않은 다른 문제에 학생들이 달려드는데 좋은 동기부여가 된다.

지도 책색은 그래프 채색(graph coloring)으로 알려진 일반적인 문제 분야에 속한다. 컴퓨터 과학에서 여기 보여지듯이 그래프는 관계의 추상적인 표현이다.

진흙도시 활동 9 에서 언급되었듯이, 그래프라는 단어는 숫자 데이터를 표현하기 위한 막대그래프 같은 차트를 의미하는 수학에서 다른 의미로 사용된다. 컴퓨터 과학자가 사용하는 그래프는 이것과 > 연관되어 있지 않다. 컴퓨터 과학에서 그래프는 기술적으로 객체를 표현하는 노드(node)라고 불리는 원 혹은 큰 점을 사용해서 표현한다. 객체와 객체 사이에는 선을 그어서 객체간에 일종의 관계가 있다는 것을 표기한다. 상기 그래프는 활동 처음에 나온 지도를 그래프로 표현한 것이다. 노드는 나라를 두 노드 사이의 선은 두 나라가 국경음 맞대고 있음을 표기한다. 그래프에서 채색 규칙은 어떠한 연결된 노드도 동일한 색으로 채색될 수 없다는 것이다. 지도와 달리, 일반적인 그래프가 필요로 하는 색 수에는 한계가 없다. 왜냐하면, 많은 다른 제약이 연결된 선에 가해질 수 있는 > 반면에 지도의 이차원적인 특성이 가능한 방식을 제약한다. 그래프 채색 문제(graph coloing problem)는 특정 그래프에 채색에 필요한 최소 색깔 숫자를 찾는 것이다.

다음 그래프에서 노드는 학교 수업 과목에 대응된다. 두 수업 과목 사이의 선은 적어도 한 학생이 두 과목을 수강한다는 것을 나타낸다. 그래서 동일 시간 시간표에 두 과목이 동시에 올라가면 안된다. 이러한 표기법을 사용하여 최소 시간이 필요한 가능한 시간표 만들기 문제는 채색 문제와 동일하다. 다른 색깔은 다른 시간대에 상응한다. 그래프 채색 알고리즘은 컴퓨터 과학에서 매우 흥미로운 주제이며, 많은 실제 생활에서 사용된다. 가난한 지도 제작자는 단지 픽션(fiction)으로 절대로 지도를 채색하는데 그래프 채색 알고리즘을 사용하지는 않을 것이다.

그래프에 기반한 문자 그대로 수천가지 다른 문제가 있다. 활동 9번째에서 언급된 최소생성나무와 활동 14번째에서 언급되는 지배 집합처럼 일부가 이 책에서 기술되었다. 그래프는 데이터를 표현하는 매우 일반적인 방식이고 다양한 상황을 표현하는데 사용될 수 있다. 예를 들어, 도로와 교차로로 구성된 지도, 분자에서 원자간 연결, 컴퓨터 네트워크를 통해 메시지가 전달되는 경로, 전자 기판(PCB)> 위 소자들간 연결, 대형 프로젝트를 수행하는 작업들간의 관계를 예로 들 수 있다. 이러한 연유로 인해서 그래프 표현을 포함하는 문제는 오랜동안 컴퓨터 과학자를 매료시켰다.

이러한 문제 중 상당수는 매우 어렵다—개념적으로 어렵다기 보다는 해결방안을 도출하는데 매우 오랜 시간이 걸려서 어렵다. 선생님이 30명, 학생이 800명 있는 학교에 최선의 강의 시간표를 작성하는 것을 예로 들어 보자. 이러한 문제는 중간 정도 크기를 가지는 그래프 채색 문제로 가장 효율적인 해결책을 도출하는 것도 알려진 최선의 알고리즘을 사용해서 몇년, 심지어 수백년이 걸린다.>
해결책을 찾아낸 시간이 되면, 문제는 이미 아무 상관업이 무관하게 된다—그리고, 컴퓨터가 작업을 마치기 전에 고장이 나거나 소모되지 않는다고 가정한다. 이러한 문제는 실제에서만 풀려질 > 수 있는데, 왜냐하면 기꺼이 최적이 아닌 하지만 매우 좋은 해결적을 받아들여 사용하려고 하기 때문이다. 만약 발견한 해결책이 가장 최선이라는 것을 보증하려고 한다면, 문제는 완전히 다루기 힘든 난해성을 가진다.

채색 문제를 해결하는데 소요되는 컴퓨터 시간은 그래프 크기가 증가함에 따라 기하급수적으로 증가한다. 지도채색 문제를 고려해보자. 이 문제는 지도를 채색하는 모든 가능한 방법을 시도해보고 해결할 수 있다. 최대로 채색에 색이 네개가 필요하다는 것을 이미 알고 있기 때문에, 네가지 색을 나라마다 적용해서 모든 가능한 조합을 평가할 필요가 있다. 만약 n개의 나라가 있다면 총 n^4>개의 조합이 있다. 숫자는 매우 빠르게 증가한다: 나라가 하나씩 증가할 때마다 4승의 곱만큼 증가해서 시간이 4배로 증가한다. 설사 이 문제를 해결하기 고안된 컴퓨터조차도, 50개 나라를 색칠하는데 한 시간이 소요되고, 나라를 하나 더 추가하면 4시간이 소요되고, 10개 나라를 더 추가하게 되면 일년이상이 정답을 찾는데 소요된다. 점점더 빠른 컴퓨터를 발명한다고 해서 이런 종류의 문제는 사라지지 않는다.

그래프 채색은 해답을 찾는 시간이 기하급수적으로 늘어나는 것을 보여주는 좋은 문제 사례다. 이번 활동에 사용된 작은 지도 같은 매우 간단한 문제 예제로, 최적의 해결책을 찾기는 매우 쉽다. 하지만, 나라의 숫자가 10개국을 넘게 되면, 최적해를 손으로 찾기는 매우 어렵게 된다. 100개 이상의 나라에 대해서 최적해를 찾기 위해서 컴퓨터를 사용하여 지도 채색을 시도하는 것도 수년이 소요될 수 있다.

실생활의 많은 문제는 이와 같은 것이지만, 어쨌든 해결책을 찾아야만 한다. 컴퓨터 과학자는 완전하지는 않지만 훌륭한 답을 제시하는 방법을 사용한다. 휴리스틱(heuristic) 기법은 최적해에 무척 가깝고, 계산하기 빠르고, 실무적인 목적에 가깝게 부합하는 해결책을 제시한다. 학교에서 완벽한 강의 시간표 보다는 한 학급 더 배정하는 정도는 참아낼만 하고, 가난한 지도 제작자도 엄밀하게 보면 필요하지 않더라도, 여분의 색을 사용하는 것을 용인한다.

어느 누구도 전통적인 컴퓨터로 이런 종류의 문제를 해결하는 효율적인 방법이 있다는 것을 증명하지는 못했다. 하지만, 누구도 효율적인 방법이 존재한다는 것도 증명하지는 못했다. 그리고 컴퓨터 > 과학자는 효율적인 방법이 발견될 것이라는데 회의적이다. 다음 후속 두개의 활동을 통해서 이런 종류의 문제를 학습할 것이다.

워크쉬트 1 에 있는 지도에 대한 유일한 해답이다. (물론, 색깔을 선택하는 것은 학생에게 달려있지만, 두가지 다른 색만 필요하다.)

워크쉬트 2 의 상단에 있는 지도는 세가지 색으로 채색될 수 있는 반면에 하단에 있는 지도는 네가지 색이 필요하다. 여기 두가지 가능한 해답이 있다.

워크쉬트 3 에 있는 지도는 좀더 단순한 세가지 색깔지도가 되고 가능한 정답이 함께 있다.

단지 색깔 두개만 사용한 워크쉬트 4 정답은 다음과 같다.