14 . 그래프 색칠하기
14.1 활동 14
개요
많은 최적화 문제는 특정 사건이 동일 시간에 발생할 수 없거나, 집합 객체에 소속된 구성원이 서로 인접할 수 없는 상황을 포함된다. 예를 들어, 수업 시간표나 회의 일정표를 작성하는 사람은 관련된 모든 사람의 제약조건을 만족시키는 문제에 맞닥드리게 된다. 이러한 어려움 중의 상당부분은 지도 색책 문제로 귀결된다. 이 문제에서 지도에 있는 국가들, 국경을 맞대고 있는 나라를 다른 색깔을 정해서 칠해야 한다. 이번 활동은 이 문제에 관한 것이다.
교과학습 연계
- 수학: 숫자 2 레벨 이상. 다른 진법의 숫자 탐색. 이진수로 숫자 표현하기.
- 수학: 대수 2 레벨 이상. 순차 패턴 계속하기. 패턴 규칙 기술하기. 이진 패턴과 관계
14.3 그래프 색칠하기
지도 색칠
14.3.1 들어가며
이번 활동은 이야기를 중심으로 돌아간다. 학생이 지도에 있는 나라를 색칠하는 지도 제작자를 돕는다. 국경을 맞대고 있는 나라가 다른 색깔이기만 하면, 나라를 무슨 색으로 칠하든지 문제가 되지 않는다.
예를 들어, 다음 지도에는 나라가 네개 있다. 만약 Northland를 빨간색으로 칠한다면, Westland와 Eastland는 빨간색이 될 수 없다. 왜냐하면, Northland와 국경을 맞대고 있어서 경계를 구별할 수 없기 때문이다. Westland를 녹색으로 칠할 수 있고 Eastland도 녹색으로 칠하는 것이 용인된다. 왜냐하면 Westland와 국경을 맞대고 있지 않기 때문이다. (만약 두 나라가 한 점에서 만난다면, 국경을 공유하는 것으로 간주되지 않아서, 동일한 색깔을 칠할 수 있다.) Southland를 빨간색으로 색칠해서 지도상에 단지 두가지 색으로 색칠을 끝마칠 수 있다.
지도 제작자가 가난해서, 크래용을 많이 사용할 수 없다. 그래서, 가능한 적은 수의 크래용을 사용하는 아이디어를 내보자.
4 대륙
14.3.2 토론
학생들에게 해결하려는 문제를 기술하게 하고, 칠판에 색칠하는 프로세스를 시연하게 한다.
첫번째 워크시트 사본을 나눠준다. 단지 두가지 색을 사용하여 올바르게 지도를 색칠할 수 있다. 단지 두가지 색으로 제한하는 것이 다소 도전과제스럽게 다가올 수 있지만, 더 많은 색을 요구하는 지도와 비교하여 간단한 과제가 된다. 왜냐하면, 각 나라를 무슨 색으로 칠할지 선택지가 그다지 많지 않기 때문이다.
학생들에게 지도를 단지 두가지 색만을 가지고 색칠하게 해본다. 이 과정에서 “해야되는 필수” 규칙을 학생들이 발견한다: 한 나라를 색칠하게 되면, 국경을 맞대고 있는 나라는 반대색으로 색칠하는 규칙. 모든 나라를 색칠할 때까지 반복적으로 이 규칙이 적용된다. 규칙을 알려주기보다 학생들 스스로 규칙을 발견할 수 있다면 최선이다. 왜냐하면 학생들에게 프로세스에 대해서 더 나은 직관을 전달하기 때문이다.
학생들이 각 연습문제를 수행하면, 다음 연습문제를 전달한다.
색깔이 칠해진 패(counter) 같은 플레이스홀더(placeholder)를 사용하는 것이 낫다는 것을 학생들이 알아챌 수도 있다. 왜냐하면, 나라를 바로 색칠하는 것보다 마음이 바뀔 때 좀더 쉽게 색을 반영할 수 있기 때문이다.
고학년 학생들에게, 찾은 색깔 숫자가 최소인지를 어떻게 알 수 있는지 설명하게 한다. 예를 들어, 이번 지도에는 최소 삼색이 필요한데 이유는 나라 세개 그룹이 있는데, 각각의 나라는 다른 두 나라와 국경을 맞대고 있기 때문이다.
만약 학생이 모든 지도를 빨리 끝마치게 된다면, 다른 5가지 색이 필요한 지도를 제작하게 한다. 어떤 지도라도 단지 4가지 색으로 칠할 수 있다는 것이 증명되었다. 그래서 숙제로 준 작업은 한 동안 학생에게 시간이 걸릴 것이다. 경험상 학생이 믿기에 5가지 색이 필요한 지도를 빨리 제작할 수 있다. 하지만, 지도에서 4가지 색으로 색칠할 수 있는 방법은 항상 찾을 수 있다.
14.4 활동: 그래프 색칠하기 1
가능하면 적은 수의 색을 사용하여 지도에 있는 나라들에 색을 칠하세요. 하지만, 국경을 맞대고 있는 인접한 어떠한 나라도 동일한 색깔이면 되지 않도록 확실히 하세요.
14.5 활동: 그래프 색칠하기 2
가능하면 적은 수의 색을 사용하여 지도에 있는 나라들에 색을 칠하세요. 하지만, 국경을 맞대고 있는 인접한 어떠한 나라도 동일한 색깔이면 되지 않도록 확실히 하세요.
14.6 활동: 그래프 색칠하기 3
가능하면 적은 수의 색을 사용하여 지도에 있는 나라들에 색을 칠하세요. 하지만, 국경을 맞대고 있는 인접한 어떠한 나라도 동일한 색깔이면 되지 않도록 확실히 하세요.
14.7 활동: 그래프 색칠하기 4
가능하면 적은 수의 색을 사용하여 지도에 있는 나라들에 색을 칠하세요. 하지만, 국경을 맞대고 있는 인접한 어떠한 나라도 동일한 색깔이면 되지 않도록 확실히 하세요.
나라 색칠
14.7.1 변형과 확장
여기 보여진 것처럼. 단지 두가지 색을 사용하여 지도를 제작하는 간단한 방법이 있다. 다음 지도는 닫힌 폐곡선(시작하는 지점과 끝점이 만나는 선)을 중첩해서 그렸다. 폐곡선 상단 위에, 이런 곡선을, 임의의 모양으로 임의의 숫자만큼 그릴 수 있다. 그리고 이러한 지도는 단지 두가지 색으로 항상 색칠할 수 있다. 학생들은 이런 유형의 지도를 만들어서 실험해 볼 수 있다.
나라 색칠
종이 평면이나, 구면에 그린 지도를 색칠하기에는 색깔 네개면 충분하다. 토러스(도넛 모양)같은 괴상한 표면에 그려진 지도를 색칠하는데 얼마나 많은 색이 필요할지 궁금한데, 과학자도 마찬가지다. > 이 경우, 5가지 색이 필요할지도 모른다. 항상 5가지 색이면 충분하다. 학생들이 이러한 실험을 진행하고 싶을지도 모른다.
지도 색칠 문제에는 흥미로운 많은 변형이 있어서 현재 알려지지 않은 방향으로 이끌 수도 있다. 예를 들어, 만일 내가 나만 종이위 지도에 색을 칠한다면, 내가 똑똑하게 작업하고나면 네가지 색깔이면 충분하다는 것을 안다. 하지만, 혼자서 작업하는 대신에, 무능한 (혹은 악의적인) 동료와 공동 작업을 하고, 교대로 나라마다 색을 칠한다고 가정하자. 나는 똑똑하게 작업하는 반면에 지도위에 나라마다 색을 칠하는 작업을 돌아가며서 진행하는데 동료는 “법이 허용하는” 한도내에서만 작업한다고 가정하자. 동료의 적합하지만 그다지 똑똑하지 못한 색칠 혹은 체제 전복적인 색칠을 추가 보상해서 제대로 만드는데 크레용이 얼마나 필요할까? 최대 색칠 숫자는 아직까지 알려지지 않았다! 1992년 크레용이 33개면 충분하다는 것이 증명되었다. 2008년 크레용이 17개면 충분할 것이다는 것이 증명되어 향상되었다. 하지만, 아직까지 이렇게 많이 필요한지 알지 못한다. (전문가는 10개보다 적은 색깔이면 충분하지 않을까 추측한다.) 학생들은 이러한 상황을 즐겁게 놀 수 있다.> 두사람이 게임을 벌여 상대방이 필요한 색깔 숫자가 최대가 되도록 만드는 놀이를 한다.
제국 채색(empire coloing)으로 알려진 또 다른 지도 책색 변형이 있다. 동일한 나라 숫자를 가진 두장의 종이 위에 서로 다른 지도가 있다. 한장의 지도(예를 들어 지구) 위에 각 나라는 다른 지도 (달위에 식민지) 위에 한 나라와 정확하게 매핑되어 짝지어진다. (양쪽 지도에 대해) 국경을 맞대고 있는 나라마다 각기 다른 색을 채색하는 요구사항에 더해서 하나의 요구사항을 더 추가한다. 지구상의 각나라는 달에 있는 식민지와 동일한 색으로 채색되어야 한다. 이 문제에 대해서 얼마나 많은 색깔이 필요할까요? 현재 정답은 알려져 있지 않다.
14.8 컴퓨터 과학 핵심 개념
이번 활동에서 탐색한 지도 채색 문제는 본질적으로 특정한 지도를 채색하는데 필요한 최소색 숫자—2, 3, 4—를 찾는 것이다. 단지 4가지 색을 사용해서 어떤 지도도 채색될 수 있다는 추측은 1852년에 정립되었다. 하지만, 1976년이 되어서야 증명이 되었다. 컴퓨터 과학은 미해결된 문제로 가득차 있다. 네가지 색깔 정리가 연구자로부터 120년 이상 관심을 받을 후에야 증명되었다는 것을 알게되는 것은 수십년동안 해결책이 발견되지 않은 다른 문제에 학생들이 달려드는데 좋은 동기부여가 된다.
4 대륙
지도 책색은 그래프 채색(graph coloring)으로 알려진 일반적인 문제 분야에 속한다. 컴퓨터 과학에서 여기 보여지듯이 그래프는 관계의 추상적인 표현이다.
진흙도시 활동 9 에서 언급되었듯이, 그래프라는 단어는 숫자 데이터를 표현하기 위한 막대그래프 같은 차트를 의미하는 수학에서 다른 의미로 사용된다. 컴퓨터 과학자가 사용하는 그래프는 이것과 연관되어 있지 않다. 컴퓨터 과학에서 그래프는 기술적으로 객체를 표현하는 노드(node)라고 불리는 원 혹은 큰 점을 사용해서 표현한다. 객체와 객체 사이에는 선을 그어서 객체간에 일종의 관계가 있다는 것을 표기한다. 상기 그래프는 활동 처음에 나온 지도를 그래프로 표현한 것이다. 노드는 나라를 두 노드 사이의 선은 두 나라가 국경음 맞대고 있음을 표기한다. 그래프에서 채색 규칙은 어떠한 연결된 노드도 동일한 색으로 채색될 수 없다는 것이다. 지도와 달리, 일반적인 그래프가 필요로 하는 색 수에는 한계가 없다. 왜냐하면, 많은 다른 제약이 연결된 선에 가해질 수 있는 반면에 지도의 이차원적인 특성이 가능한 방식을 제약한다. 그래프 채색 문제(graph coloing problem)는 특정 그래프에 채색에 필요한 최소 색깔 숫자를 찾는 것이다.
과목 선택
다음 그래프에서 노드는 학교 수업 과목에 대응된다. 두 수업 과목 사이의 선은 적어도 한 학생이 두 과목을 수강한다는 것을 나타낸다. 그래서 동일 시간 시간표에 두 과목이 동시에 올라가면 안된다. 이러한 표기법을 사용하여 최소 시간이 필요한 가능한 시간표 만들기 문제는 채색 문제와 동일하다. 다른 색깔은 다른 시간대에 상응한다. 그래프 채색 알고리즘은 컴퓨터 과학에서 매우 흥미로운 주제이며, 많은 실제 생활에서 사용된다. 가난한 지도 제작자는 단지 픽션(fiction)으로 절대로 지도를 채색하는데 그래프 채색 알고리즘을 사용하지는 않을 것이다.
그래프에 기반한 문자 그대로 수천가지 다른 문제가 있다. 활동 9번째에서 언급된 최소생성나무와 활동 14번째에서 언급되는 지배 집합처럼 일부가 이 책에서 기술되었다. 그래프는 데이터를 표현하는 매우 일반적인 방식이고 다양한 상황을 표현하는데 사용될 수 있다. 예를 들어, 도로와 교차로로 구성된 지도, 분자에서 원자간 연결, 컴퓨터 네트워크를 통해 메시지가 전달되는 경로, 전자 기판(PCB) 위 소자들간 연결, 대형 프로젝트를 수행하는 작업들간의 관계를 예로 들 수 있다. 이러한 연유로 인해서 그래프 표현을 포함하는 문제는 오랜동안 컴퓨터 과학자를 매료시켰다.
이러한 문제 중 상당수는 매우 어렵다—개념적으로 어렵다기 보다는 해결방안을 도출하는데 매우 오랜 시간이 걸려서 어렵다. 선생님이 30명, 학생이 800명 있는 학교에 최선의 강의 시간표를 작성하는 것을 예로 들어 보자. 이러한 문제는 중간 정도 크기를 가지는 그래프 채색 문제로 가장 효율적인 해결책을 도출하는 것도 알려진 최선의 알고리즘을 사용해서 몇년, 심지어 수백년이 걸린다.
해결책을 찾아낸 시간이 되면, 문제는 이미 아무 상관업이 무관하게 된다—그리고, 컴퓨터가 작업을 마치기 전에 고장이 나거나 소모되지 않는다고 가정한다. 이러한 문제는 실제에서만 풀려질 수 있는데, 왜냐하면 기꺼이 최적이 아닌 하지만 매우 좋은 해결적을 받아들여 사용하려고 하기 때문이다. 만약 발견한 해결책이 가장 최선이라는 것을 보증하려고 한다면, 문제는 완전히 다루기 힘든 난해성을 가진다.
채색 문제를 해결하는데 소요되는 컴퓨터 시간은 그래프 크기가 증가함에 따라 기하급수적으로 증가한다. 지도채색 문제를 고려해보자. 이 문제는 지도를 채색하는 모든 가능한 방법을 시도해보고 해결할 수 있다. 최대로 채색에 색이 네개가 필요하다는 것을 이미 알고 있기 때문에, 네가지 색을 나라마다 적용해서 모든 가능한 조합을 평가할 필요가 있다. 만약 n개의 나라가 있다면 총 n^4개의 조합이 있다. 숫자는 매우 빠르게 증가한다: 나라가 하나씩 증가할 때마다 4승의 곱만큼 증가해서 시간이 4배로 증가한다. 설사 이 문제를 해결하기 고안된 컴퓨터조차도, 50개 나라를 색칠하는데 한 시간이 소요되고, 나라를 하나 더 추가하면 4시간이 소요되고, 10개 나라를 더 추가하게 되면 일년이상이 정답을 찾는데 소요된다. 점점더 빠른 컴퓨터를 발명한다고 해서 이런 종류의 문제는 사라지지 않는다.
그래프 채색은 해답을 찾는 시간이 기하급수적으로 늘어나는 것을 보여주는 좋은 문제 사례다. 이번 활동에 사용된 작은 지도 같은 매우 간단한 문제 예제로, 최적의 해결책을 찾기는 매우 쉽다. 하지만, 나라의 숫자가 10개국을 넘게 되면, 최적해를 손으로 찾기는 매우 어렵게 된다. 100개 이상의 나라에 대해서 최적해를 찾기 위해서 컴퓨터를 사용하여 지도 채색을 시도하는 것도 수년이 소요될 수 있다.
실생활의 많은 문제는 이와 같은 것이지만, 어쨌든 해결책을 찾아야만 한다. 컴퓨터 과학자는 완전하지는 않지만 훌륭한 답을 제시하는 방법을 사용한다. 휴리스틱(heuristic) 기법은 최적해에 무척 가깝고, 계산하기 빠르고, 실무적인 목적에 가깝게 부합하는 해결책을 제시한다. 학교에서 완벽한 강의 시간표 보다는 한 학급 더 배정하는 정도는 참아낼만 하고, 가난한 지도 제작자도 엄밀하게 보면 필요하지 않더라도, 여분의 색을 사용하는 것을 용인한다.
어느 누구도 전통적인 컴퓨터로 이런 종류의 문제를 해결하는 효율적인 방법이 있다는 것을 증명하지는 못했다. 하지만, 누구도 효율적인 방법이 존재한다는 것도 증명하지는 못했다. 그리고 컴퓨터 > 과학자는 효율적인 방법이 발견될 것이라는데 회의적이다. 다음 후속 두개의 활동을 통해서 이런 종류의 문제를 학습할 것이다.
