울산 옥동에 있는 더플러스수학학원블로그입니다.
수능, 교육청, 삼사, 경찰대 등의 문제 풀이 동영상, 서울대 등 심층면접문제, 수리논술문제 풀이 영상 제공, 학생이 자기주도적 학습에 도움준다.
또, 울산과고를 위해 교과서인 심화수학, 고급수학, AP Calculus 등의 수업학교프린트 풀이를 제공한다.
여기의 풀이영상은 학원의 유투브인 더플러스수학(https://youtube.com/@THEPLUSMATH)에 있다.
채색다항식(Coloring Polynomial)에 대한 수학수업 교안을 만들어 보자. 채색다항식은 그래프 이론에서 중요한 개념 중 하나로, 그래프의 정점을 색칠하는 방법의 수를 계산하는 데 사용된다. 이 글을 쓰게 되는 이유는 울산과고학생들의 고1 중간고사에 경우의 수와 순열과 조합이 들어간다고 해서 무엇을 가르쳐야 할까 고민하게 되었다. 얼핏 떠오르는 것은 다음과 같다. 학생들에게 합의 법칙, 곱의 법칙의 중요성을 강조하면서 수학문제를 잘 읽고 어떤 기준으로 분류할지 고민하라고 가르쳐야겠다. 그것 말고 또 눈에 띄는 문제가 있었다.
오른쪽 그림의 A,B,C,D,E에 주어진 다섯 가지 색의 전부 또는 일부를 사 용하여 칠하려고 한다. 같은 색을 여러 번 사용 해도 좋으나 이웃한 부분에는 서로 다른 색을 칠하는 경우의 수를 구하여라.
위의 밑줄 친 부분을 보면 채색다항식이 떠오른다. 그래! 채색다항식에 대하여 가르치자! 채색다항식을 소개하면서 이것을 이용하여 위의 문제를 나중에 채색다항식을 이용하여 풀겠다. 먼저 경우의 수 단원에서 채색다항식을 활용하여 문제 해결 방법을 가르치는 학습 교안에 대해 생각해 보자. 이 교안은 채색다항식의 개념을 도입하고, 등비수열의 합을 이용하여 복잡한 경우의 수 문제를 해결하는 방법에 초점을 맞출 것입니다.
학습 목표 1. 채색다항식과 경우의 수 문제 해결 사이의 관계를 이해한다. 2. 등비수열의 합 공식을 이해하고 적용할 수 있다. 3. 제거-축약정리를 이용하여 경우의 수를 쉽게 구할 수 있는 모양으로 바꾼다. 3. 복잡한 경우의 수 문제를 해결하기 위해 위 세 가지 개념을 통합하는 방법을 배운다.
1. 채색다항식 소개
채색다항식은 그래프 이론에서 중요한 개념으로, 특정한 조건을 만족시키면서 그래프의 정점들을 색칠하는 방법의 수를 나타냅니다. 이 조건은 주로 인접한 정점들이 같은 색으로 색칠되지 않아야 한다는 것입니다. 채색다항식은 그래프의 구조와 색의 수에 따라 달라지며, 그래프 이론뿐만 아니라 조합론, 최적화, 알고리즘 설계 등 여러 분야에서 활용됩니다.
채색다항식의 정의 그래프 G의 채색다항식 P(G,k)는 G의 정점을 인접한 정점끼리 서로 다른 색으로 색칠하는 k색 사용 가능한 경우의 수를 나타냅니다. 여기서 k는 자연수입니다. 채색다항식은 다항식 형태로 표현되며, 그 계수는 특정한 색상 구성에 대한 적법한 색칠 방법의 수를 나타냅니다.
기본 개념
- 그래프(Graph): 몇 개의 점과 그들을 잇는 선으로 이루어진 도형을 그래프라 한다. - 점(Vertex): 그래프의 기본 단위, 위치나 교차점을 나타냄. - 선분(Edge): 두 정점을 연결하는 선, 정점 간의 관계를 표현. - 적법한 색칠(Legal Coloring): 인접한 두 정점이 서로 다른 색으로 칠해져 있는 색칠 방법. 예를 들어 아래의 그림을 보자. 이 그림은 그래프이다.
그림1
여기서 점 A,B,C,D,E,F는 점(vertex)이고 ¯AB,¯BF,¯FC,¯FE,¯FD는 선분이다. 여기서 위의 그래프를 4개의 색으로 이웃하는 점들은 서로 다른 색으로 칠하는 방법의 수는 모두 몇 가지인가? 이 방법의 수를 찾는 것이 우리의 주제이다. 색을 칠할 때, 먼저 F부터 칠하면 4가지, 여기서 E에 칠하는 방법은 3가지, D에 칠하는 방법은 3가지, C에 칠하는 방법은 3가지이다. 그런데 B,A를 칠하는 방법은 조금 다르다. B에 칠하는 방법은 3가지, A에 칠하는 방법은 B와 다른 색을 칠하지만 F와는 같은 색을 칠할 수 있고, 다른 색을 칠할 수 있으므로 칠하는 방법은 2가지이다. 따라서 모두 칠하는 방법은 곱의 법칙에 의해 4×3×3×3×(3×3)=4×35가지이다. 위의 그래프에서 보듯이 일렬로 되어있는 그래프인 경우는 칠하는 방법은 간단하다. 아래의 예를 보자.
그림2
그래프가 모두 일렬 선분으로 연결되어 있다면 A부터 칠하면 4가지, B는 A 와 다른 색을 칠해야 하기 때문에 3가지, C는 B 와 다른 색을 칠해야 하지만 A와는 같은 색을 칠해도 되기 때문에 3가지, D도 C와 마찬가지로 3가지, 이렇게 계속하면 F도 3가지이므로 총 경우의 수는
4×35
이다. 또, 그림1의 경우는 그림2의 경우가 F에 연결되어 있으므로 F부터 칠하면 그 다음의 경우는 모두 그림2의 경우와 똑같아서 쉽게 셀 수 있다. 다른 경우를 생각해 보자. 그래프가 회로(6각형)를 이루는 경우, 즉 다음의 그래프를 생각해 보자.
그림3
이제 그림 3의 경우에 색칠하는 경우의 수를 세어야 하는데 이것을 세는 것이 이 글의 주된 목적이다. 위의 회로를 일렬로 세워서 색칠한 경우의 수를 카운트해 보자. 위의 그래프를 일렬로 세우면 아래와 같다. 이 경우는 선분 AF를 제거한 경우와 같다. 즉,
그림4
위의 그래프를 색칠하는 방법의 수는 A,B,C,D,E,F의 순으로 색칠하면 4×35이다. 이 경우의 수에는 두 가지 경우를 포함하고 있다. (i) A≠F (ii) A=F 그런데 그림3의 경우 색칠하는 방법의 수는 그림4에서 (i) A≠F 인 경우의 수이다. 따라서 경우의 수는 4×35−(A=F)인 경우의 수 이다. 즉, 그런데 A=F 인 경우는 그림3에서 A,F를 붙여서 하나로 만든 경우(선분 AF를 축약한 것), 즉 선분의 양 끝점이 같게 만든 것과 같다. 그 그림은 아래에 있다. 기호로는 G/AF 즉,
그림5
그림5의 경우는 오각형을 위의 조건으로 색칠하는 경우의 수와 같다. 또 이 경우는 위의 방식으로 (i) A≠E (ii) A=E 로 나누면 즉, 위의 방법과 마찬가지로 선분을 제거, 축약하면 4×34−(A=E)인 경우의 수 이다.
그림6
이제까지의 과정을 정리하면 4×35−{4×34−(A=E)인 경우의 수} 이 과정을 계속하면 4×35−{4×34−{4×33−(A−D)인 경우의 수}}
4×35−{4×34−{4×33−{4×32−(A=C)인 경우의 수}}} A=C인 경우는 점이 하나이므로 칠할 수 있는 방법의 수는 4이다.
그림7
따라서
4×35−{4×34−{4×33−{4×32−{4×31}}}}
4×35−4×34+4×33−4×32+4×31
이다. 이것은 등비수열의 합이므로
4×3{1−(−3)5}1−(−3)=3×(35+1)
이다. 이 과정을 가르치는 명칭이 있다. 그게 제거 축약정리라고 한다. 아래에서 살펴보겠다.
위의 과정으로 처음에 준 문제를 풀어보자.
오른쪽 그림의 A,B,C,D,E 에 주어진 다섯 가지 색의 전부 또는 일부를 사 용하여 칠하려고 한다. 같은 색을 여러 번 사용해도 좋으나 이웃한 부분에는 서로 다른 색을 칠하는 경우의 수를 구하여라. (풀이) 먼저 각 영역을 점으로 하여 그래프로 표현해 보자.
그림8
그림9
그림9를 채색다항식의 논리로 개수를 세어보자. 먼저 A를 칠하는 개수는 5이다. 또, B,C,D,E는 모두 A와 다른 색을 칠해야 하므르 따라서 다음 그래프의 개수를 구해서 5배 하면 된다.
그림10
즉 위의 그래프의 채색할 수 있는 개수는 위의 그래프를 5가지 색이 아니라 4개의 색으로 칠하는 방법의 수이다.
4×33−4×32+4×3=84
따라서 5×84=420이다. 위의 과정을 이산수학에서 제거-축약정리라고 한다. 이를 정리하자. 채색다항식과 제거-축약 정리는 그래프 이론에서 중요한 개념입니다. 이들은 그래프의 색칠 가능성을 탐구하는 데 사용됩니다.
제거-축약 정리 (Deletion-Contraction Theorem)
제거-축약 정리는 그래프의 채색다항식을 계산하는 데 사용되는 기본적인 방법 중 하나입니다. 이 정리는 그래프에서 한 선분을 제거하거나 축약(두 정점을 하나로 합치는 것)하여 새로운 그래프를 생성하고, 이를 통해 원래 그래프의 채색다항식을 유추하는 방식을 설명합니다.
제거-축약 정리에 따르면, 그래프 G의 채색다항식 P(G,k)는 다음과 같이 계산할 수 있습니다:
한 선분 e를 제거한 그래프 G−e와 해당 선분을 축약한 그래프 G/e에 대해, P(G,k)=P(G−e,k)−P(G/e,k).
- 여기서 G−e는 한 선분 e를 제거한 그래프이며, G/e는 선분 e를 축약한 그래프입니다.
제거-축약 정리는 귀납적으로 적용될 수 있으며, 최종적으로 간단한 그래프의 채색다항식(예: 완전 그래프 또는 경로 그래프)을 통해 복잡한 그래프의 채색다항식을 계산할 수 있게 합니다. 이 방법은 특히 복잡한 그래프의 채색다항식을 계산할 때 유용합니다.
다음 문제를 제거-축약정리로 풀어보자.
오른쪽 그림의 A,B,C,D,E 에 주어진 세 가지 색의 전부 또는 일부를 사용하여 칠하려고 한다. 이웃 한 부분에는 서로 다른 색을 칠하고, A 와 D 에도 서로 다른 색을 칠할 때, 5개의 부분에 색을 칠하는 방법의 수를 구하여라.
단, B 와 D,C 와 E 는 이웃하지 않은 것으로 본다.
(풀이) A 와 D 에도 서로 다른 색으로 칠하므로 위 그림을 그래프로 만들기 위해 다음 그림처럼 만들자.
그림11
다시 우리가 채색다항식으로 색칠할 그래프는 다음과 같다.
그림12
이제 위의 그래프를 제거축약정리로 색칠한 개수를 구해보자. 먼저 선분 AD를 제거하고 축약하여 그림으로 그리면
참고 반드시 위의 방법으로 푸는 것이 가장 좋은 것이 아니다. 어떤 선분을 제거하고 축약하는 것이 나은 지는 푸는 사람의 취향에 따라 선택하면 된다. 나는 일직선으로 만들 수 있다면 좋고, 또는 회로를 만들면 좋다고 생각한다. 왜냐하면 이러한 경우에는 각각 공식을 쉽게 적용할 수 있기 때문이다. 정석문제풀이에 적용한 것입니다.
과고1학년, 2학년 대신대비를 위해 더플러스수학학원의 구술시스템에서 실제로 하고 있는 문제를 보시려거나 과학고 3학년 AP미적분학을 준비하고자 하거나 대학교1학년 미적분학에 대해 공부하려고 하면 더플러스수학 프리미엄콘텐츠 를 이용해 보세요. https://naver.me/FsR64KUy
