알티수학 쌤 수학 노트 센텀 알티수학 학원 · 부산 센텀 · 해운대

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항

글·그림 알티수학 쌤 · · 알티수학 인벤토리

색칠하는 경우의 수를 시스템적으로

처리할 수 있는 공식을 유도하겠습니다.

조금 긴 내용이지만

궁금해 하는 학생들을 위해 알려드리겠습니다.

결론만 딸랑 외워둬도 충분히 유용합니다.

고1내신 슈퍼 치트키!!

1. 그래프

꼭짓점과 꼭짓점 사이를 잇는 선으로 이뤄진

아래와 같은 그림을 그래프라 합니다.

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 1

무섭게 보이는 그림이지만

여기서는 아래와 같은 순환그래프만

계산할 거라서 쫄지 않아도 됩니다.

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 2

2. 채색 다항식

그래프 G의 모든 점(Vertex)을

k가지 색으로 색칠할 때,

서로 인접한(변으로 연결된) 점끼리는

다른 색을 칠하는 방법의 수를

P(G, k)P(G,\ k)

라 하면, 이 식은 k 에 대한 다항식으로 써집니다.

이 다항식을 채색 다항식이라 해요.

예를 들어,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 3

인 경우는

P(C3, k)=k(k−1)(k−2)P(C_3,\ k)=k(k-1)(k-2)

입니다.

학교 수학 범위에서는

P(C4, k)=n(n−1)(n2−3n+3)\textcolor{#ff5f45}{P(C_4,\ k)=n(n-1)\left(n^2-3n+3\right)}

만 자주 나오기 때문에

이것만 외워두는것도 충분히 좋습니다.

3. 삭제-수축 정리

('제거-축약 정리' 라고도 합니다.)

임의의 그래프 G 를 n 가지 이하의 색을 칠하고

인접한 점은 다른 색이 되도록 색칠한 경우의 수를

P(G, n)P(G,\ n)

이라 하면,

G 의 임의의 한 선 e 에 대해

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 4

가 성립합니다.

여기서,

G - e 는 G 에서 선 e 를 삭제한 것이고,

G · e 는 G 에서 e 의 양 끝점을 포개서 하나로

만든 그래프입니다. 즉,

e 의 양 끝점을 포개서 하나로 만들면

e 는 없어지는거죠.

증명은 의외로 간단한데 아래와 같습니다.

G 에서 e 의 양 끝점을 A, B 라고 합니다.

G 에서 e 를 삭제한 뒤에 (A, B 의 연결을 끊은 뒤에)

인접한 점을 서로 다른 색으로

잘 색칠한 경우의 수는

P(G−e, n)P(G-e,\ n)

입니다. 이 때,

두 점 A, B 는 서로 다른 색일 수도 있고,

서로 같은 색일 수도 있죠.

그러므로, 서로 같은 색의 경우를 제외해 주면

P(G, n)P(G,\ n)

이 됩니다.

그럼 A 와 B 가 서로 같은 색의 경우는

식으로 어떻게 표현하면 될까요?

이 경우의 수는 A 와 B 가 서로 같은 색이므로,

A 와 B 와 그 두 점을 잇는 선 e 를 모두 뭉쳐서

하나의 점으로 생각한 그래프에서

인접한 점이 다른 색이 되도록 색칠한 경우의 수와

일대일 대응이 됩니다. 즉,

P(G⋅e, n)P(G\cdot e,\ n)

인거죠. 따라서,

증명이 완료되었습니다.

이 정리를

삭제-수축 정리 (Deletion-Contraction)

라고 합니다.

4. 순환그래프의 채색다항식

이제 순환그래프의 채색다항식을

유도해 보겠습니다.

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 5

와 같은 그래프를 순환그래프라 합니다.

점이 m 개인 (m≥3) 순환그래프를

CmC_m

이라하고, n 가지 이하의 색을 쓰는

경우의 수를 수열로 표시해서

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 6

이라 하겠습니다.

(1)

점이 m 개인 순환그래프에서

선 e 를 하나 삭제하면

그냥 일직선으로 연결된 그래프가 되죠.

이 경우에 첫 점을 색칠하는 경우의 수는 n 가지,

두 번째 점 부터는 모두 n-1 가지 이므로,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 7

가 됩니다.

(2)

점이 m 개인 순환그래프에서

두 점을 일치시키고 사이의 선을 없애면

점이 m-1 개인 순환그래프가 되죠.

따라서,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 8

가 됩니다.

그러므로 (1), (2) 를

삭제-수축 정리에 대입하면,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 9

이 됩니다.

이 관계식이, 점이 m 개인 순환그래프의

채색 다항식의 점화식입니다.

5. 점화식을 풀어서

앞의 점화식은 일반항으로 쉽게 풀 수 있습니다.

즉,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 10

에서,

우변의 첫 항을 아래와 같이 분리하면,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 11

이고,

점화식에 대입하면,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 12

입니다.

이 식을 보기좋게 이항해서 정리하면,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 13

입니다.

이제,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 14

으로 두면,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 15

따단~ 등비수열이 됩니다.

초기값

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 16

는 앞에서 구했고,

따라서,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 17

입니다.

이것을 계산하면,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 18

가 되구요.

등비수열을 풀면,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 19

에서,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 20

이 됩니다.

그러므로,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 21

으로 원래수열로 되돌려주면

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 22

에서

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 23

가 됩니다.

예를 들어, m=4 를 대입하면,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 24

가 됩니다.

6. 결론

아래 몇 가지만 좀 외워 두면 좋습니다.

(1) 올림피아드 하는 학생들은

아래 공식 정도는 외워야 할것 같구요.

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 25

(2) 내신이라면,

m=4 일 때가 대부분 빈출하는편이고,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 26

혹시 m=5 가 출제된다면

이것은 수작업으로 케이스 나누는것이

너무 실수하기 쉬워서

공식으로 푸는것이 대박 변별력 입니다.

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 27

7. 예제 (1)

예를 들어,

아래와 같은 지도의 (가)~(마) 지역을

5색으로 색칠할 때,

이웃한 영역은 서로 다른 색이 되도록

색칠하는 방법의 가짓수를 구해보겠습니다.

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 28

열심히 케이스를 나눠서 풀어도 됩니다만

여기서는, 공식을 써보겠습니다.

(가) ~ (마) 가 점이고 인접 관계를 선으로 이으면

이 지도는 그래프가 됩니다,

일단, (마)에 한 색을 골라서 쓰는 방법이 5 가지

이제 남은 4색으로 (가), (나), (다), (라) 를

색칠해야 하는데,

(가), (나), (다), (라) 는 m=4 인 순환그래프이므로,

앞에서 외워 놓은 공식은 아래와 같죠.

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 29

여기에 n=4(색) 을 대입하면, 84 이고,

따라서, 경우의 수는

5×84=4205\times 84=420

이 답입니다.

8. 예제 (2)

아래 문제를 살펴봅시다.

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 30

공식으로 풀어보면

만의 자리에서 십의 자리까지가 C_4 이므로

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 31

에서 n=3 을 쓰면, 18 이 답이 됩니다.

물론, 일의 자리에는 만의 자리와 같은 수를

사용하므로 선택의 여지가 없구요.

간단하죠ㅋ

9. 예제 (3)

하나만 더 볼까요?

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 32

이 문제는 단순히 C_5 입니다.

따라서,

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 33

에서 n=3 을 대입하면,

답 30 이 바로 나옵니다.

간단하네요ㅋ

10. 예제 (4)

인간적으로 고1 수학에서 C_5 를 내는건

상도덕에 어긋나는것 아닐까요?

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 34

물론 제가 알려드린 공식을 쓰면 간단하죠.

삭제-수축 정리(deletion-contraction principle) 와 순환 그래프 채색 다항식(chromatic polynomial)의 일반항 계산 과정과 예시 문항 — 그림 35

에서 n=4 를 대입하고, 그 결과에 5를 곱해주면 1200이 나옵니다.

30초 컷이 가능하죠.

그리고 참고로, 입체도형을 색칠하는 방법에 관한 이론은 아래를 참고해주세요~

제 수업에서는 재미있는 것들을

많이 가르쳐 드립니다.

관심있는 학생들은 수학이 더 재미있어지고,

열심히 해야 하는 학생들은 오답률이 줄어듭니다~

저희 학원 (센텀 알티수학) 은

부산 해운대 센텀에 있는 수학 학원 입니다.

#채색다항식 #그래프 #순환그래프 #삭제수축정리 #센텀학원 #경우의수 #제거축약정리

같은 분류의 글 — 알티수학 인벤토리