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