직관 — 겹치면 안 되는 시험을 나눈다
다섯 시험 중 같은 학생이 치르는 시험은 동시에 열 수 없다고 하자. 시험을 점으로, 시간이 겹치면 안 되는 쌍을 선으로 잇는다. 같은 시간대를 같은 색으로 표시하면 필요한 시간대 수를 색의 개수로 바꿔 생각할 수 있다.
방의 수나 감독 인원 같은 추가 제약은 넣지 않은 가상 모형이다. 유한한 단순 무방향그래프에서 꼭짓점을 칠하며, 변을 칠하는 문제와 구별한다.
그래프의 채색수는 가능한 색 수의 최솟값이다
그래프의 올바른 채색은 인접한 두 꼭짓점의 색이 항상 다르도록 꼭짓점마다 색을 정하는 것이다. 그때 쓸 수 있는 색의 최소 개수를 채색수라고 한다. 꼭짓점이 하나 이상인 그래프에서 정의하며, 변이 없어도 색 하나는 필요하다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 그래프 | graph | 충돌 관계를 나타낸 단순 그래프 | |
| 채색수 | chromatic number | 사용할 수 있는 최소 색 수 | |
| 순환그래프 | cycle graph | 개의 점을 한 단순회로로 이은 그래프 | |
| 완전그래프 | complete graph | 모든 서로 다른 점 쌍이 인접하는 그래프 | |
| 완전이분그래프 | complete bipartite graph | 두 무리 개·개의 점에서 다른 무리끼리만 모두 이은 그래프 | |
| 최대 차수 | maximum degree | 꼭짓점의 차수 중 가장 큰 값 |
교과서는 꼭짓점에 색을 칠하는 것을 ‘그래프의 색칠’, 인접한 두 꼭짓점이 모두 다른 색이 되게 칠하는 것을 ‘적절한 색칠’이라고 한다. 이 글의 올바른 채색과 같다. 채색수는 로 나타내고, 는 그리스 문자 카이다. 색 번호 1·2·3은 시간대의 구별일 뿐 순서나 크기 의미는 없다.
충돌 관계는 학생 명단에서 만든다. 다섯 학생이 각자 두 시험을 치른다고 하자.
| 학생 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 치르는 시험 |
한 학생이 함께 치르는 두 시험을 변으로 이으면 충돌은 다. 이것은 이며 그림 1 위처럼 에 차례로 색 을 주면 인접한 점의 색이 모두 다르다. 따라서 세 시간대면 충분하다.
figures/coloring_choices.py서로 연결되지 않은 꼭짓점은 같은 색이어야 하나요?
같아도 되고 달라도 된다. 올바른 채색은 인접한 쌍의 색만 다르게 요구한다. 그림 1 위의 와 는 인접하지 않아 같은 색 1을 쓰며, 최소 색 수를 구할 때는 이렇게 재사용할 수 있는 색을 굳이 새 색으로 바꿀 필요가 없다.
변이 없는 그래프의 채색수는 0인가요?
꼭짓점이 하나 이상이면 1이다. 충돌이 없어서 모든 점에 같은 색을 줄 수 있지만, 점마다 색을 주려면 적어도 한 색은 있어야 한다. 꼭짓점 자체가 없는 그래프는 이 글의 범위에서 제외했다.
3색으로 칠했으니 채색수도 3일까?
아직 최소라는 이유가 필요하다. 두 색만 쓴다고 가정하고 에 1을 주자. 색 이름은 바꿔 불러도 되므로 이렇게 정해도 일반성을 잃지 않는다. 그러면 에 2, 에 1, 에 2, 에 1이 강제된다. 그림 1 아래처럼 마지막 변 의 양 끝 색이 같아 실패한다.
따라서 2색은 불가능하고 3색은 가능하므로 식 (1)의 최솟값은 다음과 같다.
일반적으로 짝수 길이의 순환그래프는 두 색을 번갈아 칠해 닫을 수 있고, 변이 있으므로 1색은 불가능해 채색수가 2다. 홀수 길이는 마지막 충돌 때문에 2색이 불가능하다. 마지막 점만 세 번째 색으로 칠하면 3색이 가능하므로 채색수는 3이다.
수형도는 몇 색으로 칠할 수 있나요?
꼭짓점이 2개 이상인 수형도는 2색이다. 뿌리에서 단순경로 길이가 짝수인 점과 홀수인 점을 다른 색으로 칠하면, 변으로 이은 두 점은 한 단계 차이라 충돌하지 않는다. 변이 있으므로 1색은 불가능하다. 점 하나인 수형도는 1색이다.
채색수의 하한과 상한은 어떻게 정할까?
‘이 색 수로 칠할 수 있다’는 상한 와 ‘이보다 적게는 안 된다’는 하한 를 따로 구해 맞춘다. 두 값이 같아지면 그 값이 채색수다.
상한은 실제 색 올바른 채색 하나로 보인다. 하한은 꼭 필요한 부분 구조로 보인다. 그래프 가 부분그래프 를 가지면 를 칠한 색으로 도 칠할 수 있으므로 다. 서로 모두 인접한 개의 점, 곧 가 있으면 그 점들은 서로 다른 색을 써야 한다.
모든 서로 다른 두 점이 인접한 완전그래프는 점마다 다른 색이 필요해 이다. 완전이분그래프는 무리마다 한 색이면 되므로 채색수가 2다. 그림 2의 는 변 6개로 4색이 필요하지만, 은 변 9개인데도 2색이면 된다. 변의 개수가 아니라 어느 점끼리 이어졌는지가 채색수를 정한다.
figures/complete_vs_bipartite.py어떤 그래프든 쓸 수 있는 상한도 있다. 한 점의 이웃은 많아야 개라서, 이웃이 쓴 색을 모두 피해도 개 중 하나는 남는다. 차수가 가장 큰 점만 보면 되는 상한이다.
는 라서 식 (4)의 상한 3이 식 (2)와 같고, 도 상한 가 실제 값이다. 그러나 은 이라 상한이 4인데 실제로는 2다. 식 (4)는 늘 성립하지만 최솟값까지 알려 주지는 않는다.
눈앞에서 가능한 가장 작은 색을 고르면 최소가 될까?
항상 그렇지는 않다. 아직 칠하지 않은 점을 하나씩 선택하고, 이미 칠한 이웃과 충돌하지 않는 가장 작은 번호의 색을 고르는 방법은 올바른 채색을 만들지만 순서의 영향을 받는다.
그림 3 위의 경로 에서 순서를 로 정하자. 먼저 는 아직 칠한 이웃이 없어서 둘 다 1이다. 는 때문에 2가 되고, 는 이웃 가 2와 1이어서 3이 된다. 그러나 그림 3 아래처럼 순서로 칠하면 의 두 색이면 충분하다.
figures/greedy_orders.py이 방법은 어떤 순서로 칠해도 식 (4)의 색을 넘지 않는다. 각 점을 칠할 때 이미 칠한 이웃이 개 이하이기 때문이다. 그래서 한 절차가 사용한 색 수는 ‘이만큼이면 가능하다’는 상한일 뿐이다. 최소라고 결론 내리려면 식 (3)의 하한을 함께 제시해야 한다. 가능한 배정의 개수까지 세는 문제는 다음 채색다항식에서 다룬다.
지도를 칠하는 데 필요한 색은 몇 가지일까?
경계선을 함께 쓰는 지역끼리 다른 색을 쓰는 지도 색칠은 꼭짓점 채색으로 바뀐다. 지역을 꼭짓점으로, 경계선을 함께 쓰는 두 지역을 변으로 이으면 된다. 필요한 최소 색 수는 그 그래프의 채색수다.
그림 4의 지도는 가운데 지역 를 다섯 지역 가 고리로 둘러싼다. 고리의 이웃 관계는 앞의 와 같고, 는 다섯 지역과 모두 이웃한다. 이 그래프를 라 하자. 고리만 칠하는 데 이미 3색이 필요하고 그 3색이 모두 의 이웃에 쓰이므로, 에는 네 번째 색이 필요하다.
figures/map_wheel.py식 (5)의 하한 4는 완전 부분그래프가 아니라 홀수 회로와 그 모두에 이웃한 점이라는 구조에서 나온다. 하한을 찾을 때 서로 모두 인접한 점만 보면 놓치는 경우다.
각 지역이 한 덩어리로 이어진 평면 지도는 네 가지 색이면 언제나 충분하다. 1976년 아펠과 하켄이 컴퓨터를 이용해 증명한 4색 정리다. 이런 지도의 이웃 관계는 평면그래프가 되며, 그림 4는 그 네 색이 실제로 모두 필요한 예다.
그래프의 채색수는 인접한 꼭짓점끼리 색이 다른 채색의 최소 색 수다. 가능한 채색과 더 적은 색이 불가능한 이유를 함께 보여야 최솟값을 확정할 수 있다.
채색수의 흔한 오해
- 가장 큰 차수만 알면 채색수가 정해진다. — 삼각형과 사각형 둘레의 최대 차수는 모두 2지만 채색수는 각각 3과 2다. 식 (4)는 상한만 준다.
- 서로 모두 인접한 점이 3개뿐이면 3색이면 된다. — 그림 4의 그래프는 서로 모두 인접한 점이 최대 3개인데 식 (5)처럼 4색이 필요하다.
- 어떤 그래프든 네 가지 색이면 충분하다. — 4색 정리는 평면 지도에 관한 것이다. 다섯 점이 모두 이어진 는 5색이 필요하고, 변 10개가 평면그래프의 한계 를 넘는다.
직접 해보기
- 삼각형 에 새 점 와 변 를 붙였다. 채색수와 가능한 배정을 하나 구하시오.
- 여섯 점을 둘레로 이은 의 채색수를 최소성까지 설명하시오.
- 완전그래프 과 완전이분그래프 의 채색수를 각각 구하시오.
- 다섯 점의 경로 를 순서로 가장 작은 가능한 번호의 색을 주면 몇 색을 쓰는가? 실제 채색수와 비교하시오.
- 가운데 지역 하나를 여섯 지역이 고리 모양으로 둘러싼 지도를 칠하는 데 필요한 최소 색 수를 구하시오.
답과 풀이
- 삼각형 때문에 적어도 3색이 필요하다. 에 을 주면 충분하므로 채색수는 3이다.
- 둘레를 로 칠할 수 있다. 변이 있어 1색으로는 불가능하므로 채색수는 2다.
- 은 여섯 점이 모두 서로 인접해 6색이 필요하고, 하나씩 주면 되므로 6이다. 는 세 점 무리에 1, 네 점 무리에 2를 주면 되고 변이 있어 1색은 안 되므로 2다.
- 에 1, 에 2를 준다. 마지막 의 두 이웃이 모두 2이므로 에는 1을 주어 총 2색을 쓴다. 변 때문에 1색은 불가능하므로 이번 순서에서는 실제 채색수 2를 얻었다.
- 고리 여섯 지역은 짝수 길이 이라 로 칠할 수 있다. 가운데 지역은 모든 고리 지역과 이웃하므로 세 번째 색이 필요하다. 식 (5)와 같은 이유로 이다.
더 읽기
- 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-07]의 채색수와 문제 해결.
- 우리교과서 이산 수학 공개본 — 인쇄 155~159쪽의 그래프의 색칠·적절한 색칠, 채색수의 성질과 지도 색칠 예제를 대조했다. 본문의 그래프와 지도는 별도로 구성했다.
- Levin, Coloring — 4.4절의 올바른 꼭짓점 채색, 완전 부분그래프 하한, 최대 차수 상한, 4색 정리, 바퀴 그래프 연습을 대조했다. 변 채색은 이번 글에 포함하지 않는다.
영상 노트
- 00:00 학생 명단에서 시험 충돌 그래프를 만들기
- 00:50 그림 1 위의 3색 배정과 아래의 2색 실패로 식 (2) 얻기
- 01:50 식 (3)의 하한·상한, 그림 2의 K₄와 K₃,₃ 비교
- 02:50 식 (4)의 최대 차수 상한과 그림 3의 칠하는 순서 비교
- 03:50 그림 4의 지도를 그래프로 바꿔 식 (5)의 4색 얻기, 4색 정리의 범위
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 교과서 ‘적절한 색칠’ 용어 연결, 학생 명단에서 충돌 그래프 만들기, 하한·상한과 최대 차수 상한, 완전·완전이분그래프, 지도 색칠과 4색 정리 추가, 허수아비 오해 교체, 해보기 보강 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림