변 색칠 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Desargues_graph_3color_edge.svg|섬네일|오른쪽|그래프의 3색 변 색칠]]
[[파일:Complete-edge-coloring.svg|섬네일|오른쪽|[[완전 그래프]] <math>K_8</math>의 7색 변 색칠]]
[[그래프 이론]]에서 '''변 색칠'''(邊色漆, {{llang|en|edge colo(u)ring}}은 [[그래프]]의 변들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다.<ref>{{서적 인용|제목=Graph edge coloring: Vizing’s theorem and Goldberg’s conjecture|이름=Michael|성=Stiebitz|이름2= Diego |성2=Scheide|이름3= Bjarne |성3=Toft|이름4= Lene M.|성4= Favrholdt|출판사=Wiley|날짜=2012-02|url=http://www.wiley.com/WileyCDA/WileyTitle/productCd-111809137X.html|isbn= 978-1-118-09137-1|언어=en}}</ref><ref>{{서적 인용|성=Fiorini|이름=S.|성2=Wilson|이름2=R.|제목=Edge-colourings of graphs|출판사=Pittman|날짜=1977|언어=en}}</ref> 이를 사용하여 그래프의 불변량을 정의할 수 있다.

== 정의 ==
(단순) [[그래프]] <math>G</math>의 '''변 색칠''' <math>(C,c)</math>은 다음 데이터로 구성된다.
* 집합 <math>C</math>
* 함수 <math>c\colon\operatorname E(G)\to C</math>
이는 다음 조건을 만족시켜야 한다.
* 서로 인접하는 두 변 <math>e,e'\in\operatorname E(G)</math>에 대하여, <math>c(e)\ne c(e')</math>
변 색칠 <math>(C,c)</math>에서, <math>C</math>의 원소를 '''색'''(色, {{llang|en|colo(u)r}})이라고 한다.

즉, 그래프 <math>G</math>의 변 색칠은 그 [[선 그래프]] <math>\operatorname L(G)</math>의 [[그래프 색칠]]과 동치인 개념이다.

그래프가 가질 수 있는 변 색칠에서, 색의 수의 최솟값을 '''색칠 지표'''(色漆指標, {{llang|en|chromatic index}})라고 하며, <math>\chi'(G)=\chi(\operatorname L(G))</math>로 쓴다. (이는 꼭짓점 [[색칠수]] <math>\chi(G)</math>와 구분하기 위함이다.)

=== 유일 ''k''-변 색칠 그래프 ===
자연수 <math>k</math>와 그래프 <math>G</math>가 주어졌다고 하자. 만약 <math>G</math> 위의, 같은 색 집합 <math>C</math>에 대한 임의의 두 변 색칠 <math>(C,c)</math> 및 <math>(C,c')</math>에 대하여, <math>c=\sigma\circ c'</math>인 [[순열]] <math>\sigma\in\operatorname{Sym}(C)</math>이 항상 존재한다면, <math>G</math>를 '''유일 ''k''-변 색칠 그래프'''({{llang|en|uniquely <math>k</math>-edge-colorable graph}})라고 한다.

== 성질 ==
'''비징의 정리'''(Визинг의定理, {{llang|en|Vizing’s theorem}})에 따르면, 임의의 유한 그래프 <math>G</math>에 대하여
:<math>\chi'(G)-\Delta(G)\in\{0,1\}</math>
이다. 여기서
:<math>\Delta(G)=\max_{v\in\operatorname V(G)}\deg g\in\mathbb N</math>
는 <math>G</math>의 꼭짓점의 차수의 최댓값이다.
이에 따라서, 모든 그래프는 다음과 같이 '''1종 그래프'''(一種graph, {{llang|en|class 1 graph}}) 및 '''2종 그래프'''(二種graph, {{llang|en|class 2 graph}})로 분류된다.
* '''1종 그래프'''의 경우 <math>\chi'(\Gamma)=\Delta(\Gamma)</math>이다.
* '''2종 그래프'''의 경우 <math>\chi'(\Gamma)=\Delta(\Gamma)+1</math>이다.
(이 정리는 [[다중 그래프]]에 대하여 성립하지 않는다.)

유한 그래프의 색칠 지표가 주어진 자연수와 같은지 여부는 [[NP-완전]] 문제이다.

== 예 ==
'''[[쾨니그의 정리]]'''에 따라, 모든 유한 [[이분 그래프]]는 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인 경우는 미해결 문제로 남아 있다.

[[에르되시-레니 모형]]({{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종 그래프이다.

== 역사 ==
비징의 정리는 [[우크라이나]]의 수학자 바딤 게오르기예비치 비징({{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}}
* {{매스월드|id=EdgeColoring|title=Edge coloring}}
* {{매스월드|id=MinimumEdgeColoring|title=Minimum edge coloring}}
* {{매스월드|id=EdgeChromaticNumber|title=Edge chromatic number}}
* {{매스월드|id=VizingsTheorem|title=Vizing’s theorem}}
* {{매스월드|id=Class1Graph|title=Class 1 graph}}
* {{매스월드|id=Class2Graph|title=Class 2 graph}}
* {{웹 인용|url=http://web.iyte.edu.tr/~tinabeseri/tina-tez.pdf|제목=Edge coloring of a graph|이름=Tina|성=Beşeri|날짜=2004-07|기타=석사 학위 논문|출판사=İzmir Yüksek Teknoloji Enstitüsü|언어=en}}

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