직관 — 최소 시간대와 배정 방법의 수
시험을 세 시간대로 나눌 수 있다는 사실을 알았다고 하자. 이제 가능한 시간표가 몇 개인지 묻는다. 첫째 시간과 둘째 시간을 맞바꾼 시간표는 다른 배정이므로, 색 이름을 구별한 채 세어야 한다.
시험은 꼭짓점, 같은 학생이 치러 동시에 열 수 없는 두 시험은 변, 시간대는 색이다. 채색수가 필요한 최소 색 수를 물었다면, 채색다항식은 쓸 수 있는 색 수가 주어졌을 때 가능한 배정의 개수를 묻는다. 대상은 꼭짓점이 하나 이상인 유한한 단순 무방향그래프다.
이 페이지의 주 예제는 네 시험 가 로 충돌하는 사각형 둘레 다. 시간대가 셋이면 시간표는 18개이고, 세 시간대를 모두 쓰는 시간표는 그중 12개다.
채색다항식은 이름이 다른 색으로 칠하는 방법의 수다
채색다항식 는 이름으로 구별되는 개의 색 중에서 골라 그래프 의 꼭짓점을 올바르게 칠하는 방법의 수를 나타내는 다항식이다. 개수로 해석할 때 는 0 이상의 정수이고, 주어진 색을 모두 사용할 필요는 없다.
변 하나로 연결된 두 꼭짓점에서는 첫 점의 색이 가지, 둘째는 첫 점의 색을 뺀 가지다. 따라서
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 채색다항식 | chromatic polynomial | 사용 가능한 색 수에 따른 올바른 배정 수 | |
| 색 수 | number of available colors | 이름이 구별되는 사용할 수 있는 색의 개수 | |
| 채색수 | chromatic number | 올바른 채색에 필요한 최소 색 수 | |
| 변 삭제 그래프 | edge-deleted graph | 변 만 지우고 꼭짓점은 남긴 그래프 | |
| 변 축약 그래프 | contracted graph | 의 양 끝을 합치고 중복 연결은 하나로 정리한 그래프 | |
| 완전·순환그래프 | complete graph, cycle graph | 모든 쌍 연결·하나의 단순회로 | |
| 수형도, 꼭짓점 수 | tree, order | 회로 없는 연결그래프와 그 점 수 |
교과서는 채색다항식을 , 채색수를 로 쓰고, 올바른 채색을 ‘적절한 색칠’이라 부른다. 이 페이지는 두 기호를 혼동하지 않도록 채색다항식을 로 쓴다. 식 (1)에 을 넣으면 이다. 색 이름 1·2·3에서 순서 있게 두 색을 고르는 여섯 배정이다.
채색다항식은 사용 가능한 색을 모두 써야 하나요?
아니다. 채색다항식은 주어진 색 중 일부만 쓴 배정도 센다. 서로 인접하지 않은 두 점에 색 3개가 주어지면 각각 세 색 중 하나를 골라 가지이고, 두 점이 같은 색인 세 경우도 들어 있다. 모든 색을 써야 하는 경우는 ‘모든 색을 써야 하면 채색다항식에서 무엇을 빼야 할까’ §에서 따로 센다.
채색다항식에서 색 이름을 바꾼 배정도 따로 세나요?
따로 센다. 변 하나의 양 끝에 색 1·2를 주는 경우와 2·1을 주는 경우는 다른 배정이다. 교실·시간대처럼 구별되는 선택지를 색으로 나타내기 때문에 식 (1)은 이를 모두 센다.
수형도와 완전그래프의 채색다항식은 곱의 법칙으로 구한다
꼭짓점을 정한 순서로 하나씩 칠하고 단계마다의 선택 수를 곱의 법칙으로 곱한다. 이때 각 단계의 선택 수가 앞에서 고른 색과 무관하게 하나로 정해져야 한다.
꼭짓점이 개인 수형도에서 뿌리를 정하자. 뿌리의 색은 가지이고, 나머지 점은 뿌리에서 가까운 순서로 칠하면 먼저 칠한 이웃 하나(부모)와만 색을 다르게 하면 된다. 먼저 칠한 다른 점과도 변이 있다면 회로가 생겨 수형도일 수 없기 때문이다. 따라서 에서는
그림 1 위는 꼭짓점 5개 수형도를 뿌리 부터 칠할 때의 선택 수이고, 곱은 이다. 가지가 어떻게 갈라지든 뿌리 밖의 각 점은 먼저 칠한 이웃 하나(부모)만 피하므로 꼭짓점 수만 결과에 남는다. 일 때 은 변 하나조차 올바르게 칠할 수 없어 0이고 식 (2)도 0이다. 은 따로 라 두면 같은 표기를 다룰 필요가 없다.
완전그래프의 점들은 모두 다른 색을 써야 한다. 첫 점부터 선택 수가 하나씩 줄어
일 때 이 곱은 서로 다른 개의 색에서 개를 골라 순서대로 놓는 순열의 수(교과서 기호 )이다. 이면 색이 부족해 배정이 없고, 곱에도 0인 인수가 들어가 같은 값 0을 준다. 예를 들어 삼각형에 색 3개가 있으면 가지다.
수형도와 완전그래프의 모양이 섞인 그래프도 같은 방법으로 센다. 새로 칠할 점의 먼저 칠한 이웃이 모두 서로 인접하면, 그 이웃들은 이미 서로 다른 색이다. 그러면 새 점의 선택 수는 에서 그 이웃 수를 뺀 값으로 정해진다.
그림 1 아래는 삼각형 에 점 를 에만 이은 그래프 다. 순서로 칠하면 는 서로 인접한 를 피해 가지, 는 하나만 피해 가지다.
색이 3개면 가지다.
figures/sequential_choices.py사각형 둘레의 채색다항식은 왜 차례로 곱할 수 없을까?
사각형 둘레 를 순서로 칠하면 마지막 점 의 이웃 가 서로 인접하지 않는다. 두 점이 같은 색이면 는 가지, 다른 색이면 가지여서 선택 수가 하나로 정해지지 않는다.
그래서 대각선 위치의 두 점 가 같은 색인지로 경우를 나눈다(그림 2). 같은 색이면 는 의 색 하나로 정해진다. 다른 색이면 는 의 색을 피해 가지다.
두 경우는 겹치지 않고 모든 배정을 빠짐없이 나누므로 합의 법칙으로 더한다.
공통인수 로 묶으면 괄호 안은 이다.
색 3개에서는 식 (5)가 , 식 (6)이 이라 모두 18가지다. 색 0개·1개·2개일 때는 식 (8)이 차례로 0·0·2를 준다.
figures/c4_case_split.py채색다항식의 삭제·축약 공식은 왜 뺄셈일까?
변 를 지운 를 세면 가 같은 색인, 원래 그래프에서는 허용되지 않는 배정까지 들어가기 때문이다. 그런 배정은 두 끝을 하나로 합친 의 배정과 하나씩 대응하므로 그 수만큼 뺀다. 자세히 보면 의 채색 중 의 색이 다른 것은 변을 다시 넣어도 괜찮아 의 채색이다. 두 색이 같은 것은 합친 점에 그 색을 준 의 채색과 정확히 대응한다.
축약할 때 변 자체는 없앤다. 두 점이 공통 이웃을 가졌다면 같은 두 점 사이 연결이 겹치는데, ‘색이 달라야 한다’는 같은 조건이므로 하나만 남긴다. 원래 단순 그래프였으므로 이 처리 뒤에도 자기 연결이나 중복 변이 없는 단순 그래프로 다룰 수 있다.
그림 2의 경우 나누기도 같은 원리다. 에 대각선 를 더한 그래프에서 그 변을 지우면 , 합치면 세 점 수형도다. 대각선이 있는 그래프의 채색은 가 다른 식 (6)의 경우이고, 세 점 수형도의 채색은 가 같은 식 (5)의 경우다. 그래서 식 (9)의 왼쪽 식에 넣으면 식 (7)이 된다.
그림 3의 사각형 둘레에서 변 를 로 고르자. 지우면 네 점의 수형도가 되고, 를 로 합치면 삼각형이 된다. 식 (2)·(3)·(9)를 적용하면
로 식 (8)과 같다. 색 3개이면 가지다.
figures/deletion_contraction.py변이 없는 점 그래프에서는 각 점이 자유롭게 색을 골라 이다. 식 (9)를 변이 줄어드는 그래프에 반복하면 변이 없는 그래프의 식들의 합과 차가 되므로, 채색의 개수는 의 다항식이다. 또 는 꼭짓점 수가 그대로이고 는 하나 적어서, 빼는 항은 최고차항을 바꾸지 않는다. 그래서 꼭짓점이 개인 그래프의 채색다항식은 최고차항의 계수가 1인 차 다항식이다.
채색다항식은 이름이 다른 사용 가능한 색으로 올바르게 칠하는 배정 수다. 모든 색을 쓸 필요는 없으며, 차례로 곱할 수 없으면 삭제한 그래프의 배정에서 축약한 그래프의 배정을 뺀다.
채색다항식의 차수와 계수는 무엇을 알려 주나요?
채색다항식의 차수는 꼭짓점 수 이고, 최고차항의 계수는 1, 상수항은 0이다. 이면 의 계수는 변의 개수 에 대해 이다. 식 (9)에서 빼는 항 의 최고차항이 이라 변이 하나 늘 때마다 이 계수가 1씩 줄기 때문이다. 식 (8)을 전개한 도 변 4개와 맞는다.
채색다항식이 같으면 같은 그래프인가요?
그렇지 않다. 네 점을 일렬로 이은 수형도와 중심 한 점에 세 잎을 붙인 수형도는 꼭짓점의 차수 목록이 다르지만 모두 식 (2)에 따라 이다. 같은 다항식은 연결 모양을 모두 복원하는 정보가 아니다.
순환그래프의 채색다항식은 어떤 규칙을 따를까?
꼭짓점이 개인 순환그래프 에서 변 하나를 지우면 점을 일렬로 이은 수형도가 되고, 그 변의 양 끝을 합치면 이 된다. 따라서 식 (2)와 식 (9)로 한 단계 작은 순환그래프의 식에서 다음 식을 얻는다.
출발은 의 다. 색 3개에서는 이 6이므로 는 , 는 , 은 이다. 이 반복을 한 식으로 모으면 다음과 같다.
이면 로 식 (3)과 같다. 식 (12)가 에서 맞으면 식 (11)에 넣어 에서도 맞으므로, 부터 한 단계씩 모든 순환그래프로 이어진다.
식 (12)를 식 (11)에 넣는 계산
을 식 (11)에 넣으면 이다. 앞의 두 항은 로 묶여 이 된다. 마지막 항은 이므로 이다. 둘을 합치면 에 대한 식 (12)다.
를 넣으면 이라 이 짝수면 2, 홀수면 0이다. 에서는 이면 가 양수다. 그래서 짝수 길이 순환그래프의 채색수는 2, 홀수 길이는 3이고, 채색수에서 홀짝으로 얻은 결론과 같다.
채색다항식으로 채색수를 어떻게 찾을까?
채색수는 채색다항식의 값이 처음으로 양수가 되는 자연수다. 색으로 칠할 수 있으면 색이 더 많을 때도 같은 배정을 쓸 수 있으므로, 값은 보다 작은 색 수에서 0이고 이상에서 양수다. 교과서는 이를 자연수 에 대한 필요충분조건으로 적는다.
그림 4는 꼭짓점 4개인 수형도 , , 의 값을 비교한다. 처음 양수가 되는 색 수는 와 가 2, 가 4이므로 채색수도 각각 2, 2, 4다. 에 변 를 더하면 , 에 대각선 둘을 더하면 이므로 같은 에서 값이 줄거나 같다. 식 (9)에서 보듯 한 그래프에 변 하나를 더하면 그 양 끝이 같은 색인 배정만큼 빠지기 때문이다.
figures/polynomial_values_compare.py반대로 다항식에서 채색수를 읽을 수도 있다. 꼭짓점 4개 그래프의 채색다항식이 이면 이고 이므로 채색수는 3이다. 이 식은 식 (6)과 같고, 에 대각선 를 더한 그래프의 채색다항식이다.
채색수에서 다항식을 정하는 유형도 있다. 꼭짓점 4개이고 채색수가 4이면 이다. 인수정리로 을 모두 인수로 갖고, 최고차항의 계수가 1인 4차식이므로 이다. 곧 에 대한 식 (3)이다.
채색다항식의 값이 양수이면 그 색 수가 채색수인가요?
아니다. 채색수는 채색다항식의 값이 양수가 되는 가장 작은 자연수다. 는 이지만 가 이미 양수이므로 채색수는 2다. 식 (13)의 두 조건을 함께 확인해야 한다.
모든 색을 써야 하면 채색다항식에서 무엇을 빼야 할까?
모든 색을 써야 하면 채색다항식의 값에서 어떤 색을 빠뜨린 배정을 빼야 한다. 색이 3개일 때 포함배제의 원리를 쓰면 다음과 같다.
특정한 한 색을 쓰지 않는 배정은 나머지 두 색으로 칠한 것이라 가지이고, 빠뜨릴 색을 고르는 방법이 3가지다. 두 색을 함께 쓰지 않는 배정은 가지씩 세 쌍이 있는데, 앞에서 두 번씩 빠졌으므로 한 번씩 다시 더한다. 세 색을 모두 쓰지 않는 배정은 이라 식에 남지 않는다.
주 예제에 넣으면 다. 네 시험을 세 시간대에 빈 시간대 없이 배정하는 방법이 12가지다. 그림 5는 18가지 배정을 모두 늘어놓은 것으로, 이고 인 여섯 가지만 두 색을 쓴다.
figures/all_colors_used.py채색다항식의 흔한 오해
- 사각형 둘레도 차례로 곱해 로 셀 수 있다. — 의 이웃 가 같은 색일 수 있어 선택 수가 일정하지 않다. 이 식은 색 3개에서 12를 주지만 실제는 식 (8)의 18이다.
- 삭제·축약 식에서는 두 항을 더한다. — 더하면 삭제한 그래프의 배정 수가 된다. 에서 더하면 색 3개일 때 이지만 실제는 이다.
- 다항식의 차수가 채색수다. — 꼭짓점 4개 수형도의 채색다항식은 4차지만 채색수는 2다. 차수는 꼭짓점 수를 알려 준다.
- 변이 많은 그래프일수록 같은 에서 채색다항식의 값이 작거나 같다. — 한 그래프에 변을 더해 얻은 그래프끼리만 성립한다. 삼각형에 어느 점과도 잇지 않은 점 하나를 더한 꼭짓점 4개 그래프는 변이 3개지만 색 2개에서 0이고, 변이 4개인 는 2다.
직접 해보기
- 꼭짓점 6개인 수형도를 색 3개로 칠하는 방법은 몇 가지인가? 그중 세 색을 모두 쓰는 방법은 몇 가지인가?
- 사각형 둘레 에 새 점 를 더해 , 와 각각 이은 ‘집 모양’ 그래프의 채색다항식과 채색수를 구하시오.
- 순환그래프 의 다섯 점 모두에 새 점 를 이은 바퀴 모양 그래프의 채색다항식을 식 (12)를 써서 구하고, 채색수를 구하시오.
- 삼각형 하나와, 그와 떨어진 변 하나로 이루어진 꼭짓점 5개 그래프의 채색다항식과 색 3개일 때의 값을 구하시오.
- 꼭짓점이 3개이고 채색수가 2인 그래프 에서 이다. 를 구하시오.
답과 풀이
- 식 (2)에서 가지다. 식 (14)에 , 을 넣으면 가지다.
- 사각형 둘레를 칠하는 가지 각각에서 의 이웃 는 서로 인접해 색이 다르므로 는 가지다. 따라서 이다. , 이므로 채색수는 3이다.
- 를 먼저 칠하면 가지다. 둘레의 다섯 점은 모두 와 인접하므로 의 색을 뺀 개의 색으로 를 올바르게 칠해야 한다. 식 (12)의 자리에 을 넣으면 이므로 이다. , 이므로 채색수는 4다. 전개한 식의 의 계수 이 변 10개와 맞는다.
- 두 부분은 이어져 있지 않아 색 선택이 서로 영향을 주지 않으므로 각각의 식을 곱한다. 삼각형의 와 변의 을 곱해 이고, 색 3개이면 가지다. 전개한 식의 의 계수 가 변 4개와 맞는다.
- 채색수가 2이므로 이고, 인수정리로 을 인수로 갖는다. 최고차항의 계수가 1인 3차식이므로 로 놓는다. 에서 이므로 , 곧 세 점을 일렬로 이은 수형도의 식이다.
더 읽기
- 교육부 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가지 세기
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 차례로 곱하는 조건과 사각형 둘레의 경우 나누기, 순환그래프의 식, 채색수 판정과 역으로 식 정하기, 모든 색을 쓰는 경우의 수, 해보기 다섯 문항 보강, 값 비교를 변을 더한 그래프끼리로 바로잡고 해보기 3을 바퀴 모양 그래프로 교체 (에이전트 수정, 그림 1→5)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림