비징의 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''비징의 정리'''(Визинг의定理, {{llang|en|Vizing’s theorem}})는 [[그래프]]의 [[변 색칠수]]와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다.

== 정의 ==
'''비징의 정리'''에 따르면, (단순 무향) 그래프 <math>\Gamma</math>의 변 색칠수 <math>\chi'(\Gamma)</math> 및 <math>\Gamma</math>의 최대 차수
:<math>\Delta(\Gamma)=\max_{v\in V(\Gamma)}\Delta(v)</math>
사이에 다음과 같은 관계가 성립한다.
:<math>\Delta(\Gamma)\le\chi'(\Gamma)\le\Delta(\Gamma)+1</math>
이에 따라서, 모든 그래프는 다음과 같이 '''1종 그래프'''({{llang|en|class 1 graph}}) 및 '''2종 그래프'''({{llang|en|class 2 graph}})로 분류된다.
* '''1종 그래프'''의 경우 <math>\chi'(\Gamma)=\Delta(\Gamma)</math>이다.
* '''2종 그래프'''의 경우 <math>\chi'(\Gamma)=\Delta(\Gamma)+1</math>이다.
이 정리는 [[다중 그래프]]에 대하여 성립하지 않는다.

== 성질 ==
[[에르되시-레니 모형]]({{llang|en|Erdős–Rényi model}})에서, <math>n</math>개의 꼭짓점을 갖는 무작위 그래프가 1종 그래프일 확률 <math>p(n)</math>은 다음과 같은 극한을 갖는다.<ref>{{인용
 | last = Erdős | first = Paul | authorlink = 에르되시 팔
 | 공저자 = Robin J. Wilson
 | 날짜 = 1977
 | title = Note on the chromatic index of almost all graphs
 | journal = Journal of Combinatorial Theory (Series B)
 | volume = 23
 | pages = 255–257
 | url = http://www.renyi.hu/~p_erdos/1977-20.pdf
 | doi = 10.1016/0095-8956(77)90039-9
 | issue = 2–3 | 언어=en}}</ref>
:<math>\lim_{n\to\infty}p(n)=1</math>
즉, 에르되시-레니 모형에서 거의 모든 그래프는 1종 그래프이다.

최대 차수가 7 이상인 [[평면 그래프]]는 1종 그래프이다. 이 정리는 최대 차수가 8 이상인 경우는 비징이 증명하였고,<ref>{{저널 인용
 | last = Визинг | first = В. Г. | 날짜 = 1965
 | title = Критические графы с данным хроматическим классом
 | journal = Дискретный Анализ  | volume = 5 | pages = 9–17|zbl=0171.44902|언어=ru}}</ref> 7인 경우는 2001년에 증명되었다.<ref>{{저널 인용
 | last = Sanders | first = Daniel P. | 공저자 = Yue Zhao | 날짜 = 2001
 | title = Planar graphs of maximum degree seven are class I
 | journal = Journal of Combinatorial Theory (Series B) | volume = 83 | issue = 2 | pages = 201–212
 | doi = 10.1006/jctb.2001.2047 | zbl = 1024.05031 | 언어=en}}</ref> 최대 차수가 5 이하인 경우, 2종 [[평면 그래프]]가 존재하며, 이러한 그래프들은 [[정다면체]]로부터 작도할 수 있다. 최대 차수가 6인 경우는 미해결 문제로 남아 있다.

[[쾨니그의 정리]]에 따라, 모든 [[이분 그래프]]는 1종 그래프이다.

== 역사 ==
[[우크라이나]]의 수학자 바딤 게오르기예비치 비징({{llang|ru|Вади́м Гео́ргиевич Визинг}}, {{llang|uk|Вадим Георгійович Візінг|바딤 게오르기요비치 비징}})이 1964년에 증명하였다.<ref>{{저널 인용
 | last = Визинг | first = В. Г. | 날짜 = 1964
 | title = Об оценке хроматического класса ''p''-графа | mr = 0180505
 | journal = Дискретный Анализ | volume = 3 | pages = 25–30 | 언어=ru}}</ref>

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Vizing theorem}}

[[분류:그래프 색칠]]
[[분류:그래프 이론 정리]]