비징의 정리
그래프 이론에서 비징의 정리(Визинг의定理, 영어: Vizing’s theorem)는 그래프의 변 색칠수와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다.
정의
[편집]비징의 정리에 따르면, (단순 무향) 그래프 의 변 색칠수 및 의 최대 차수
사이에 다음과 같은 관계가 성립한다.
이에 따라서, 모든 그래프는 다음과 같이 1종 그래프(영어: class 1 graph) 및 2종 그래프(영어: class 2 graph)로 분류된다.
- 1종 그래프의 경우 이다.
- 2종 그래프의 경우 이다.
이 정리는 다중 그래프에 대하여 성립하지 않는다.
성질
[편집]에르되시-레니 모형(영어: Erdős–Rényi model)에서, 개의 꼭짓점을 갖는 무작위 그래프가 1종 그래프일 확률 은 다음과 같은 극한을 갖는다.[1]
즉, 에르되시-레니 모형에서 거의 모든 그래프는 1종 그래프이다.
최대 차수가 7 이상인 평면 그래프는 1종 그래프이다. 이 정리는 최대 차수가 8 이상인 경우는 비징이 증명하였고,[2] 7인 경우는 2001년에 증명되었다.[3] 최대 차수가 5 이하인 경우, 2종 평면 그래프가 존재하며, 이러한 그래프들은 정다면체로부터 작도할 수 있다. 최대 차수가 6인 경우는 미해결 문제로 남아 있다.
쾨니그의 정리에 따라, 모든 이분 그래프는 1종 그래프이다.
역사
[편집]우크라이나의 수학자 바딤 게오르기예비치 비징(러시아어: Вади́м Гео́ргиевич Визинг, 우크라이나어: Вадим Георгійович Візінг 바딤 게오르기요비치 비징[*])이 1964년에 증명하였다.[4]
각주
[편집]- ↑ Erdős, Paul; Robin J. Wilson (1977), “Note on the chromatic index of almost all graphs” (PDF), 《Journal of Combinatorial Theory (Series B)》 (영어) 23 (2–3): 255–257, doi:10.1016/0095-8956(77)90039-9
- ↑ Визинг, В. Г. (1965). “Критические графы с данным хроматическим классом”. 《Дискретный Анализ》 (러시아어) 5: 9–17. Zbl 0171.44902.
- ↑ Sanders, Daniel P.; Yue Zhao (2001). “Planar graphs of maximum degree seven are class I”. 《Journal of Combinatorial Theory (Series B)》 (영어) 83 (2): 201–212. doi:10.1006/jctb.2001.2047. Zbl 1024.05031.
- ↑ Визинг, В. Г. (1964). “Об оценке хроматического класса p-графа”. 《Дискретный Анализ》 (러시아어) 3: 25–30. MR 0180505.
외부 링크
[편집]- “Vizing theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.