그래프 색칠: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) |
Osteologia (토론 | 기여) |
||
56번째 줄:
연결 성분 <math>\Gamma_1,\dots,\Gamma_n</math>으로 구성된 그래프의 색칠 다항식은 다음과 같다.
:<math>P_\Gamma(t)=\prod_{i=1}^nP_{\Gamma_i}(t)</math>
(단순 무향) 그래프 <math>\Gamma</math> 및 <math>uv\in E(\Gamma)</math>에 대하여, <math>\Gamma-uv</math>를 <math>\Gamma</math>에서 변 <math>uv</math>를 제거한 그래프, <math>\Gamma/uv</math>를 <math>\Gamma</math>에서 변 <math>uv</math>를 제거하고 <math>u</math>와 <math>v</math>를 합친 그래프라고 하자. 그렇다면 다음이 성립한다.
:<math>P_\Gamma=P_{\Gamma-uv}-P_{\Gamma/uv}</math>
즉, 이를 사용하여 색칠 다항식을 재귀적으로 계산할 수 있다.
=== 알고리즘 ===
| |||