기초수학채색다항식#363

채색다항식

Chromatic Polynomials

채색다항식은 이름이 구별되는 q개의 색 중에서 골라 그래프의 꼭짓점을 올바르게 칠하는 방법의 수를 q의 식으로 나타낸 것이다. 주어진 색을 모두 쓸 필요는 없다. 곱의 법칙과 변의 삭제·축약으로 수형도·완전그래프·순환그래프의 식을 구하고, 채색수와 모든 색을 쓰는 경우의 수를 찾는다.

읽는 시간
약 10분
선수 개념
그래프의 채색수수형도

직관 — 최소 시간대와 배정 방법의 수

직관

시험을 세 시간대로 나눌 수 있다는 사실을 알았다고 하자. 이제 가능한 시간표가 몇 개인지 묻는다. 첫째 시간과 둘째 시간을 맞바꾼 시간표는 다른 배정이므로, 색 이름을 구별한 채 세어야 한다.

시험은 꼭짓점, 같은 학생이 치러 동시에 열 수 없는 두 시험은 변, 시간대는 색이다. 채색수가 필요한 최소 색 수를 물었다면, 채색다항식은 쓸 수 있는 색 수가 주어졌을 때 가능한 배정의 개수를 묻는다. 대상은 꼭짓점이 하나 이상인 유한한 단순 무방향그래프다.

이 페이지의 주 예제는 네 시험 A,B,C,DA,B,C,D가 AB,BC,CD,DAAB,BC,CD,DA로 충돌하는 사각형 둘레 C4C_4다. 시간대가 셋이면 시간표는 18개이고, 세 시간대를 모두 쓰는 시간표는 그중 12개다.

채색다항식은 이름이 다른 색으로 칠하는 방법의 수다

채색다항식 PG(q)P_G(q)는 이름으로 구별되는 qq개의 색 중에서 골라 그래프 GG의 꼭짓점을 올바르게 칠하는 방법의 수를 나타내는 다항식이다. 개수로 해석할 때 qq는 0 이상의 정수이고, 주어진 색을 모두 사용할 필요는 없다.

변 하나로 연결된 두 꼭짓점에서는 첫 점의 색이 qq가지, 둘째는 첫 점의 색을 뺀 q−1q-1가지다. 따라서

PK2(q)=q(q−1).(1)P_{K_2}(q)=q(q-1). \tag{1}
정의
기호이름원어뜻
PG(q)P_G(q)채색다항식chromatic polynomial사용 가능한 색 수에 따른 올바른 배정 수
qq색 수number of available colors이름이 구별되는 사용할 수 있는 색의 개수
χ(G)\chi(G)채색수chromatic number올바른 채색에 필요한 최소 색 수
G−eG-e변 삭제 그래프edge-deleted graph변 ee만 지우고 꼭짓점은 남긴 그래프
G/eG/e변 축약 그래프contracted graphee의 양 끝을 합치고 중복 연결은 하나로 정리한 그래프
Kn,CnK_n,C_n완전·순환그래프complete graph, cycle graph모든 쌍 연결·하나의 단순회로
T,nT,n수형도, 꼭짓점 수tree, order회로 없는 연결그래프와 그 점 수

교과서는 채색다항식을 χG(q)\chi_G(q), 채색수를 χ(G)\chi(G)로 쓰고, 올바른 채색을 ‘적절한 색칠’이라 부른다. 이 페이지는 두 기호를 혼동하지 않도록 채색다항식을 PG(q)P_G(q)로 쓴다. 식 (1)에 q=3q=3을 넣으면 3×2=63\times2=6이다. 색 이름 1·2·3에서 순서 있게 두 색을 고르는 여섯 배정이다.

채색다항식은 사용 가능한 색을 모두 써야 하나요?

아니다. 채색다항식은 주어진 색 중 일부만 쓴 배정도 센다. 서로 인접하지 않은 두 점에 색 3개가 주어지면 각각 세 색 중 하나를 골라 3×3=93\times3=9가지이고, 두 점이 같은 색인 세 경우도 들어 있다. 모든 색을 써야 하는 경우는 ‘모든 색을 써야 하면 채색다항식에서 무엇을 빼야 할까’ §에서 따로 센다.

채색다항식에서 색 이름을 바꾼 배정도 따로 세나요?

따로 센다. 변 하나의 양 끝에 색 1·2를 주는 경우와 2·1을 주는 경우는 다른 배정이다. 교실·시간대처럼 구별되는 선택지를 색으로 나타내기 때문에 식 (1)은 이를 모두 센다.

수형도와 완전그래프의 채색다항식은 곱의 법칙으로 구한다

꼭짓점을 정한 순서로 하나씩 칠하고 단계마다의 선택 수를 곱의 법칙으로 곱한다. 이때 각 단계의 선택 수가 앞에서 고른 색과 무관하게 하나로 정해져야 한다.

꼭짓점이 n≥2n\ge2개인 수형도에서 뿌리를 정하자. 뿌리의 색은 qq가지이고, 나머지 점은 뿌리에서 가까운 순서로 칠하면 먼저 칠한 이웃 하나(부모)와만 색을 다르게 하면 된다. 먼저 칠한 다른 점과도 변이 있다면 회로가 생겨 수형도일 수 없기 때문이다. 따라서 q≥2q\ge2에서는

PT(q)=q(q−1)n−1.(2)P_T(q)=q(q-1)^{n-1}. \tag{2}

그림 1 위는 꼭짓점 5개 수형도를 뿌리 AA부터 칠할 때의 선택 수이고, 곱은 q(q−1)4q(q-1)^4이다. 가지가 어떻게 갈라지든 뿌리 밖의 각 점은 먼저 칠한 이웃 하나(부모)만 피하므로 꼭짓점 수만 결과에 남는다. n≥2n\ge2일 때 q=0,1q=0,1은 변 하나조차 올바르게 칠할 수 없어 0이고 식 (2)도 0이다. n=1n=1은 따로 PT(q)=qP_T(q)=q라 두면 000^0 같은 표기를 다룰 필요가 없다.

완전그래프의 점들은 모두 다른 색을 써야 한다. 첫 점부터 선택 수가 하나씩 줄어

PKn(q)=q(q−1)(q−2)⋯(q−n+1).(3)P_{K_n}(q)=q(q-1)(q-2)\cdots(q-n+1). \tag{3}

q≥nq\ge n일 때 이 곱은 서로 다른 qq개의 색에서 nn개를 골라 순서대로 놓는 순열의 수(교과서 기호 qPn{}_qP_n)이다. 0≤q<n0\le q<n이면 색이 부족해 배정이 없고, 곱에도 0인 인수가 들어가 같은 값 0을 준다. 예를 들어 삼각형에 색 3개가 있으면 3×2×1=63\times2\times1=6가지다.

수형도와 완전그래프의 모양이 섞인 그래프도 같은 방법으로 센다. 새로 칠할 점의 먼저 칠한 이웃이 모두 서로 인접하면, 그 이웃들은 이미 서로 다른 색이다. 그러면 새 점의 선택 수는 qq에서 그 이웃 수를 뺀 값으로 정해진다.

그림 1 아래는 삼각형 ABCABC에 점 DD를 CC에만 이은 그래프 HH다. A,B,C,DA,B,C,D 순서로 칠하면 CC는 서로 인접한 A,BA,B를 피해 q−2q-2가지, DD는 CC 하나만 피해 q−1q-1가지다.

PH(q)=q(q−1)(q−2)(q−1)=q(q−1)2(q−2).(4)P_H(q)=q(q-1)(q-2)(q-1)=q(q-1)^2(q-2). \tag{4}

색이 3개면 3×2×1×2=123\times2\times1\times2=12가지다.

위는 꼭짓점 5개 수형도를 뿌리 A부터, 아래는 삼각형 ABC에 D를 C에만 이은 그래프 H를 A, B, C, D 순서로 칠할 때 각 점 옆에 적은 선택 수다. 먼저 칠한 이웃끼리 모두 인접해서 선택 수가 앞의 배정과 무관하게 정해지고, 아래에 적은 곱이 채색다항식이다.
그림 1 위는 꼭짓점 5개 수형도를 뿌리 A부터, 아래는 삼각형 ABC에 D를 C에만 이은 그래프 H를 A, B, C, D 순서로 칠할 때 각 점 옆에 적은 선택 수다. 먼저 칠한 이웃끼리 모두 인접해서 선택 수가 앞의 배정과 무관하게 정해지고, 아래에 적은 곱이 채색다항식이다. figures/sequential_choices.py

사각형 둘레의 채색다항식은 왜 차례로 곱할 수 없을까?

사각형 둘레 C4C_4를 A,B,C,DA,B,C,D 순서로 칠하면 마지막 점 DD의 이웃 A,CA,C가 서로 인접하지 않는다. 두 점이 같은 색이면 DD는 q−1q-1가지, 다른 색이면 q−2q-2가지여서 선택 수가 하나로 정해지지 않는다.

그래서 대각선 위치의 두 점 A,CA,C가 같은 색인지로 경우를 나눈다(그림 2). 같은 색이면 CC는 AA의 색 하나로 정해진다. 다른 색이면 CC는 A,BA,B의 색을 피해 q−2q-2가지다.

A,C가 같은 색:q(q−1)⋅1⋅(q−1)=q(q−1)2(5)A,C\text{가 같은 색}:\quad q(q-1)\cdot1\cdot(q-1)=q(q-1)^2 \tag{5} A,C가 다른 색:q(q−1)(q−2)(q−2)=q(q−1)(q−2)2(6)A,C\text{가 다른 색}:\quad q(q-1)(q-2)(q-2)=q(q-1)(q-2)^2 \tag{6}

두 경우는 겹치지 않고 모든 배정을 빠짐없이 나누므로 합의 법칙으로 더한다.

PC4(q)=q(q−1)2+q(q−1)(q−2)2(7)P_{C_4}(q)=q(q-1)^2+q(q-1)(q-2)^2 \tag{7}

공통인수 q(q−1)q(q-1)로 묶으면 괄호 안은 (q−1)+(q2−4q+4)=q2−3q+3(q-1)+(q^2-4q+4)=q^2-3q+3이다.

PC4(q)=q(q−1)(q2−3q+3).(8)P_{C_4}(q)=q(q-1)(q^2-3q+3). \tag{8}

색 3개에서는 식 (5)가 3×2×2=123\times2\times2=12, 식 (6)이 3×2×1×1=63\times2\times1\times1=6이라 모두 18가지다. 색 0개·1개·2개일 때는 식 (8)이 차례로 0·0·2를 준다.

사각형 둘레 C₄를 A, B, C, D 순서로 칠할 때 대각선 위치의 A, C가 같은 색인 경우(위)와 다른 색인 경우(아래)의 선택 수다. 위의 곱이 식 (5), 아래의 곱이 식 (6)이다.
그림 2 사각형 둘레 C₄를 A, B, C, D 순서로 칠할 때 대각선 위치의 A, C가 같은 색인 경우(위)와 다른 색인 경우(아래)의 선택 수다. 위의 곱이 식 (5), 아래의 곱이 식 (6)이다. figures/c4_case_split.py

채색다항식의 삭제·축약 공식은 왜 뺄셈일까?

변 e=uve=uv를 지운 G−eG-e를 세면 u,vu,v가 같은 색인, 원래 그래프에서는 허용되지 않는 배정까지 들어가기 때문이다. 그런 배정은 두 끝을 하나로 합친 G/eG/e의 배정과 하나씩 대응하므로 그 수만큼 뺀다. 자세히 보면 G−eG-e의 채색 중 u,vu,v의 색이 다른 것은 변을 다시 넣어도 괜찮아 GG의 채색이다. 두 색이 같은 것은 합친 점에 그 색을 준 G/eG/e의 채색과 정확히 대응한다.

축약할 때 변 uvuv 자체는 없앤다. 두 점이 공통 이웃을 가졌다면 같은 두 점 사이 연결이 겹치는데, ‘색이 달라야 한다’는 같은 조건이므로 하나만 남긴다. 원래 단순 그래프였으므로 이 처리 뒤에도 자기 연결이나 중복 변이 없는 단순 그래프로 다룰 수 있다.

PG−e(q)=PG(q)+PG/e(q),PG(q)=PG−e(q)−PG/e(q).(9)P_{G-e}(q)=P_G(q)+P_{G/e}(q),\qquad P_G(q)=P_{G-e}(q)-P_{G/e}(q). \tag{9}

그림 2의 경우 나누기도 같은 원리다. C4C_4에 대각선 ACAC를 더한 그래프에서 그 변을 지우면 C4C_4, 합치면 세 점 수형도다. 대각선이 있는 그래프의 채색은 A,CA,C가 다른 식 (6)의 경우이고, 세 점 수형도의 채색은 A,CA,C가 같은 식 (5)의 경우다. 그래서 식 (9)의 왼쪽 식에 넣으면 식 (7)이 된다.

그림 3의 사각형 둘레에서 변 ADAD를 ee로 고르자. 지우면 네 점의 수형도가 되고, A,DA,D를 XX로 합치면 삼각형이 된다. 식 (2)·(3)·(9)를 적용하면

PC4(q)=q(q−1)3−q(q−1)(q−2)=q(q−1){(q−1)2−(q−2)}=q(q−1)(q2−3q+3)(10)\begin{aligned} P_{C_4}(q)&=q(q-1)^3-q(q-1)(q-2)\\ &=q(q-1)\{(q-1)^2-(q-2)\}\\ &=q(q-1)(q^2-3q+3) \end{aligned} \tag{10}

로 식 (8)과 같다. 색 3개이면 24−6=1824-6=18가지다.

위부터 C₄, 변 e = AD를 삭제한 네 점 수형도, A와 D를 X로 합친 삼각형이고 각 그래프 아래에 채색다항식을 적었다. 삭제는 꼭짓점 수를 보존하고 축약은 하나 줄이며, 식 (10)은 가운데 식에서 아래 식을 뺀다.
그림 3 위부터 C₄, 변 e = AD를 삭제한 네 점 수형도, A와 D를 X로 합친 삼각형이고 각 그래프 아래에 채색다항식을 적었다. 삭제는 꼭짓점 수를 보존하고 축약은 하나 줄이며, 식 (10)은 가운데 식에서 아래 식을 뺀다. figures/deletion_contraction.py

변이 없는 nn점 그래프에서는 각 점이 자유롭게 색을 골라 qnq^n이다. 식 (9)를 변이 줄어드는 그래프에 반복하면 변이 없는 그래프의 식들의 합과 차가 되므로, 채색의 개수는 qq의 다항식이다. 또 G−eG-e는 꼭짓점 수가 그대로이고 G/eG/e는 하나 적어서, 빼는 항은 최고차항을 바꾸지 않는다. 그래서 꼭짓점이 nn개인 그래프의 채색다항식은 최고차항의 계수가 1인 nn차 다항식이다.

핵심

채색다항식은 이름이 다른 사용 가능한 색으로 올바르게 칠하는 배정 수다. 모든 색을 쓸 필요는 없으며, 차례로 곱할 수 없으면 삭제한 그래프의 배정에서 축약한 그래프의 배정을 뺀다.

채색다항식의 차수와 계수는 무엇을 알려 주나요?

채색다항식의 차수는 꼭짓점 수 nn이고, 최고차항의 계수는 1, 상수항은 0이다. n≥2n\ge2이면 qn−1q^{n-1}의 계수는 변의 개수 mm에 대해 −m-m이다. 식 (9)에서 빼는 항 PG/eP_{G/e}의 최고차항이 qn−1q^{n-1}이라 변이 하나 늘 때마다 이 계수가 1씩 줄기 때문이다. 식 (8)을 전개한 q4−4q3+6q2−3qq^4-4q^3+6q^2-3q도 변 4개와 맞는다.

채색다항식이 같으면 같은 그래프인가요?

그렇지 않다. 네 점을 일렬로 이은 수형도와 중심 한 점에 세 잎을 붙인 수형도는 꼭짓점의 차수 목록이 다르지만 모두 식 (2)에 따라 q(q−1)3q(q-1)^3이다. 같은 다항식은 연결 모양을 모두 복원하는 정보가 아니다.

순환그래프의 채색다항식은 어떤 규칙을 따를까?

꼭짓점이 n≥4n\ge4개인 순환그래프 CnC_n에서 변 하나를 지우면 nn점을 일렬로 이은 수형도가 되고, 그 변의 양 끝을 합치면 Cn−1C_{n-1}이 된다. 따라서 식 (2)와 식 (9)로 한 단계 작은 순환그래프의 식에서 다음 식을 얻는다.

PCn(q)=q(q−1)n−1−PCn−1(q)(n≥4).(11)P_{C_n}(q)=q(q-1)^{n-1}-P_{C_{n-1}}(q)\qquad(n\ge4). \tag{11}

출발은 C3=K3C_3=K_3의 q(q−1)(q−2)q(q-1)(q-2)다. 색 3개에서는 C3C_3이 6이므로 C4C_4는 3×23−6=183\times2^3-6=18, C5C_5는 3×24−18=303\times2^4-18=30, C6C_6은 3×25−30=663\times2^5-30=66이다. 이 반복을 한 식으로 모으면 다음과 같다.

PCn(q)=(q−1)n+(−1)n(q−1)(n≥3).(12)P_{C_n}(q)=(q-1)^n+(-1)^n(q-1)\qquad(n\ge3). \tag{12}

n=3n=3이면 (q−1)3−(q−1)=(q−1)(q2−2q)=q(q−1)(q−2)(q-1)^3-(q-1)=(q-1)(q^2-2q)=q(q-1)(q-2)로 식 (3)과 같다. 식 (12)가 Cn−1C_{n-1}에서 맞으면 식 (11)에 넣어 CnC_n에서도 맞으므로, n=3n=3부터 한 단계씩 모든 순환그래프로 이어진다.

식 (12)를 식 (11)에 넣는 계산

PCn−1(q)=(q−1)n−1+(−1)n−1(q−1)P_{C_{n-1}}(q)=(q-1)^{n-1}+(-1)^{n-1}(q-1)을 식 (11)에 넣으면 q(q−1)n−1−(q−1)n−1−(−1)n−1(q−1)q(q-1)^{n-1}-(q-1)^{n-1}-(-1)^{n-1}(q-1)이다. 앞의 두 항은 (q−1)n−1(q-1)^{n-1}로 묶여 (q−1)n−1(q−1)=(q−1)n(q-1)^{n-1}(q-1)=(q-1)^n이 된다. 마지막 항은 −(−1)n−1=(−1)n-(-1)^{n-1}=(-1)^n이므로 (−1)n(q−1)(-1)^n(q-1)이다. 둘을 합치면 nn에 대한 식 (12)다.

q=2q=2를 넣으면 1+(−1)n1+(-1)^n이라 nn이 짝수면 2, 홀수면 0이다. q=3q=3에서는 n≥3n\ge3이면 2n±22^n\pm2가 양수다. 그래서 짝수 길이 순환그래프의 채색수는 2, 홀수 길이는 3이고, 채색수에서 홀짝으로 얻은 결론과 같다.

채색다항식으로 채색수를 어떻게 찾을까?

채색수는 채색다항식의 값이 처음으로 양수가 되는 자연수다. kk색으로 칠할 수 있으면 색이 더 많을 때도 같은 배정을 쓸 수 있으므로, 값은 χ(G)\chi(G)보다 작은 색 수에서 0이고 χ(G)\chi(G) 이상에서 양수다. 교과서는 이를 자연수 kk에 대한 필요충분조건으로 적는다.

χ(G)=k  ⟺  PG(k−1)=0 이고 PG(k)>0.(13)\chi(G)=k\iff P_G(k-1)=0\ \text{이고}\ P_G(k)>0. \tag{13}

그림 4는 꼭짓점 4개인 수형도 TT, C4C_4, K4K_4의 값을 비교한다. 처음 양수가 되는 색 수는 TT와 C4C_4가 2, K4K_4가 4이므로 채색수도 각각 2, 2, 4다. TT에 변 ADAD를 더하면 C4C_4, C4C_4에 대각선 둘을 더하면 K4K_4이므로 같은 qq에서 값이 줄거나 같다. 식 (9)에서 보듯 한 그래프에 변 하나를 더하면 그 양 끝이 같은 색인 배정만큼 빠지기 때문이다.

꼭짓점 4개인 수형도 T(경로 A–B–C–D), 사각형 둘레 C₄, 완전그래프 K₄의 채색다항식 값을 q = 1, 2, 3, 4에서 비교한 막대그래프다. 처음 양수가 되는 q가 채색수다. T에 변을 더하면 C₄, C₄에 변을 더하면 K₄라서 같은 q에서 값이 작아지거나 같다.
그림 4 꼭짓점 4개인 수형도 T(경로 A–B–C–D), 사각형 둘레 C₄, 완전그래프 K₄의 채색다항식 값을 q = 1, 2, 3, 4에서 비교한 막대그래프다. 처음 양수가 되는 q가 채색수다. T에 변을 더하면 C₄, C₄에 변을 더하면 K₄라서 같은 q에서 값이 작아지거나 같다. figures/polynomial_values_compare.py

반대로 다항식에서 채색수를 읽을 수도 있다. 꼭짓점 4개 그래프의 채색다항식이 q(q−1)(q−2)2q(q-1)(q-2)^2이면 P(2)=0P(2)=0이고 P(3)=3×2×12=6>0P(3)=3\times2\times1^2=6>0이므로 채색수는 3이다. 이 식은 식 (6)과 같고, C4C_4에 대각선 ACAC를 더한 그래프의 채색다항식이다.

채색수에서 다항식을 정하는 유형도 있다. 꼭짓점 4개이고 채색수가 4이면 P(0)=P(1)=P(2)=P(3)=0P(0)=P(1)=P(2)=P(3)=0이다. 인수정리로 q, q−1, q−2, q−3q,\ q-1,\ q-2,\ q-3을 모두 인수로 갖고, 최고차항의 계수가 1인 4차식이므로 P(q)=q(q−1)(q−2)(q−3)P(q)=q(q-1)(q-2)(q-3)이다. 곧 K4K_4에 대한 식 (3)이다.

채색다항식의 값이 양수이면 그 색 수가 채색수인가요?

아니다. 채색수는 채색다항식의 값이 양수가 되는 가장 작은 자연수다. C4C_4는 PC4(3)=18>0P_{C_4}(3)=18>0이지만 PC4(2)=2P_{C_4}(2)=2가 이미 양수이므로 채색수는 2다. 식 (13)의 두 조건을 함께 확인해야 한다.

모든 색을 써야 하면 채색다항식에서 무엇을 빼야 할까?

모든 색을 써야 하면 채색다항식의 값에서 어떤 색을 빠뜨린 배정을 빼야 한다. 색이 3개일 때 포함배제의 원리를 쓰면 다음과 같다.

(세 색을 모두 쓰는 배정 수)=PG(3)−3PG(2)+3PG(1).(14)(\text{세 색을 모두 쓰는 배정 수})=P_G(3)-3P_G(2)+3P_G(1). \tag{14}

특정한 한 색을 쓰지 않는 배정은 나머지 두 색으로 칠한 것이라 PG(2)P_G(2)가지이고, 빠뜨릴 색을 고르는 방법이 3가지다. 두 색을 함께 쓰지 않는 배정은 PG(1)P_G(1)가지씩 세 쌍이 있는데, 앞에서 두 번씩 빠졌으므로 한 번씩 다시 더한다. 세 색을 모두 쓰지 않는 배정은 PG(0)=0P_G(0)=0이라 식에 남지 않는다.

주 예제에 넣으면 18−3×2+3×0=1218-3\times2+3\times0=12다. 네 시험을 세 시간대에 빈 시간대 없이 배정하는 방법이 12가지다. 그림 5는 18가지 배정을 모두 늘어놓은 것으로, A=CA=C이고 B=DB=D인 여섯 가지만 두 색을 쓴다.

사각형 둘레 C₄를 색 1, 2, 3으로 올바르게 칠한 18가지를 맨 위 꼭짓점 자리대로 적고, 대각선 쌍 A, C와 B, D의 같고 다름으로 나눴다. 왼쪽 여섯 가지만 두 색을 쓰고, 나머지 12가지가 세 색을 모두 쓴다.
그림 5 사각형 둘레 C₄를 색 1, 2, 3으로 올바르게 칠한 18가지를 맨 위 꼭짓점 자리대로 적고, 대각선 쌍 A, C와 B, D의 같고 다름으로 나눴다. 왼쪽 여섯 가지만 두 색을 쓰고, 나머지 12가지가 세 색을 모두 쓴다. figures/all_colors_used.py

채색다항식의 흔한 오해

  • 사각형 둘레도 차례로 곱해 q(q−1)(q−1)(q−2)q(q-1)(q-1)(q-2)로 셀 수 있다. — DD의 이웃 A,CA,C가 같은 색일 수 있어 선택 수가 일정하지 않다. 이 식은 색 3개에서 12를 주지만 실제는 식 (8)의 18이다.
  • 삭제·축약 식에서는 두 항을 더한다. — 더하면 삭제한 그래프의 배정 수가 된다. C4C_4에서 더하면 색 3개일 때 24+6=3024+6=30이지만 실제는 24−6=1824-6=18이다.
  • 다항식의 차수가 채색수다. — 꼭짓점 4개 수형도의 채색다항식은 4차지만 채색수는 2다. 차수는 꼭짓점 수를 알려 준다.
  • 변이 많은 그래프일수록 같은 qq에서 채색다항식의 값이 작거나 같다. — 한 그래프에 변을 더해 얻은 그래프끼리만 성립한다. 삼각형에 어느 점과도 잇지 않은 점 하나를 더한 꼭짓점 4개 그래프는 변이 3개지만 색 2개에서 0이고, 변이 4개인 C4C_4는 2다.

직접 해보기

  1. 꼭짓점 6개인 수형도를 색 3개로 칠하는 방법은 몇 가지인가? 그중 세 색을 모두 쓰는 방법은 몇 가지인가?
  2. 사각형 둘레 ABCDABCD에 새 점 EE를 더해 AA, BB와 각각 이은 ‘집 모양’ 그래프의 채색다항식과 채색수를 구하시오.
  3. 순환그래프 C5C_5의 다섯 점 모두에 새 점 OO를 이은 바퀴 모양 그래프의 채색다항식을 식 (12)를 써서 구하고, 채색수를 구하시오.
  4. 삼각형 하나와, 그와 떨어진 변 하나로 이루어진 꼭짓점 5개 그래프의 채색다항식과 색 3개일 때의 값을 구하시오.
  5. 꼭짓점이 3개이고 채색수가 2인 그래프 GG에서 PG(2)=2P_G(2)=2이다. PG(q)P_G(q)를 구하시오.
답과 풀이
  1. 식 (2)에서 3×25=963\times2^5=96가지다. 식 (14)에 P(2)=2×15=2P(2)=2\times1^5=2, P(1)=0P(1)=0을 넣으면 96−3×2+0=9096-3\times2+0=90가지다.
  2. 사각형 둘레를 칠하는 PC4(q)P_{C_4}(q)가지 각각에서 EE의 이웃 A,BA,B는 서로 인접해 색이 다르므로 EE는 q−2q-2가지다. 따라서 P(q)=q(q−1)(q−2)(q2−3q+3)P(q)=q(q-1)(q-2)(q^2-3q+3)이다. P(2)=0P(2)=0, P(3)=3×2×1×3=18>0P(3)=3\times2\times1\times3=18>0이므로 채색수는 3이다.
  3. OO를 먼저 칠하면 qq가지다. 둘레의 다섯 점은 모두 OO와 인접하므로 OO의 색을 뺀 q−1q-1개의 색으로 C5C_5를 올바르게 칠해야 한다. 식 (12)의 qq 자리에 q−1q-1을 넣으면 (q−2)5−(q−2)(q-2)^5-(q-2)이므로 P(q)=q{(q−2)5−(q−2)}P(q)=q\{(q-2)^5-(q-2)\}이다. P(3)=3(1−1)=0P(3)=3(1-1)=0, P(4)=4(32−2)=120>0P(4)=4(32-2)=120>0이므로 채색수는 4다. 전개한 식의 q5q^5의 계수 −10-10이 변 10개와 맞는다.
  4. 두 부분은 이어져 있지 않아 색 선택이 서로 영향을 주지 않으므로 각각의 식을 곱한다. 삼각형의 q(q−1)(q−2)q(q-1)(q-2)와 변의 q(q−1)q(q-1)을 곱해 q2(q−1)2(q−2)q^2(q-1)^2(q-2)이고, 색 3개이면 6×6=366\times6=36가지다. 전개한 식의 q4q^4의 계수 −4-4가 변 4개와 맞는다.
  5. 채색수가 2이므로 P(0)=P(1)=0P(0)=P(1)=0이고, 인수정리로 q(q−1)q(q-1)을 인수로 갖는다. 최고차항의 계수가 1인 3차식이므로 P(q)=q(q−1)(q−a)P(q)=q(q-1)(q-a)로 놓는다. P(2)=2(2−a)=2P(2)=2(2-a)=2에서 a=1a=1이므로 PG(q)=q(q−1)2P_G(q)=q(q-1)^2, 곧 세 점을 일렬로 이은 수형도의 식이다.

더 읽기

  • 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-07]은 채색수와 채색다항식을 모두 다룬다.
  • Buckingham, Graph Theory — 「The chromatic polynomial of a simple graph」와 「Edge deletion and contraction」의 경우 분할을 대조했다. ‘채색다항식의 삭제·축약 공식은 왜 뺄셈일까’ §의 축약 정리와 수형도 경계 사례를 여기에 맞췄다.

영상 노트

영상 노트
  • 00:00 최소 색 수와 가능한 배정 수 구별하기, 네 시험의 사각형 둘레 예제 소개
  • 00:40 그림 1로 수형도·완전그래프·그래프 H의 선택 수 곱하기, 식 (2)·(3)·(4)
  • 01:40 그림 2에서 A, C의 같고 다름으로 나눠 식 (7)·(8) 얻기
  • 02:40 그림 3에서 삭제·축약을 구분하고 식 (9)의 뺄셈 이유 설명하기
  • 03:40 식 (11)로 순환그래프 값을 이어 계산하고 식 (12)의 홀짝 확인하기
  • 04:30 그림 4에서 처음 양수가 되는 q로 채색수 읽기, 식 (13)
  • 05:20 그림 5와 식 (14)로 세 시간대를 모두 쓰는 12가지 세기

지도에서의 위치

그래프의 뜻기초수학그래프의 채색수기초수학수형도기초수학채색다항식지금 이 페이지
선수 개념
이 페이지
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 차례로 곱하는 조건과 사각형 둘레의 경우 나누기, 순환그래프의 식, 채색수 판정과 역으로 식 정하기, 모든 색을 쓰는 경우의 수, 해보기 다섯 문항 보강, 값 비교를 변을 더한 그래프끼리로 바로잡고 해보기 3을 바퀴 모양 그래프로 교체 (에이전트 수정, 그림 1→5)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림