완전 이분 그래프 문서 원본 보기

[[그래프 이론]]에서 '''완전 이분 그래프'''(完全二分graph, {{llang|en|complete bipartite graph}})란 [[꼭짓점]]의 집합이 서로 겹치지 않는 두 집합 X와 Y의 [[합집합]]이고 X의 모든 꼭짓점이 Y의 각각의 꼭짓점과 하나의 변으로 연결되어 있는 [[이분 그래프]]이다.

== 정의 ==
집합 <math>V</math>의 <math>k</math>조각 [[집합의 분할|분할]]
:<math>V=V_1\sqcup\dotsb V_k</math>
가 주어졌다고 하자. 이 [[집합의 분할]]에 대응하는 '''완전 <math>k</math>분 그래프'''({{llang|en|complete <math>k</math>-partite graph}})는 위와 같은 분할에 대하여 <math>k</math>분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다. 즉, 그 변의 집합은 다음과 같은 꼴이다.
:<math>E=\bigsqcup_{1\le i<j\le k}V_i\times V_j</math>

<math>V_1,\dotsc,V_k</math>의 [[집합의 크기]]가 각각 <math>n_1,\dotsc,n_k</math>일 때, 이에 대응하는 완전 <math>k</math>분 그래프는 <math>K_{n_1,\dotsc,n_k}</math>로 표기한다.

<math>k=1</math>일 경우, 이는 [[완전 그래프]]와 같다. <math>k=2</math>일 경우 이를 '''완전 이분 그래프'''(完全二分graph, {{llang|en|complete bipartite graph}}), <math>k=3</math>일 경우 이를 '''완전 삼분 그래프'''(完全三分graph, {{llang|en|complete tripartite graph}})라고 한다.

== 성질 ==
=== 색칠 ===
정의에 따라, 완전 <math>k</math>분 그래프는 [[이분 그래프|<math>k</math>분 그래프]]이며, 그 [[채색수]]는 <math>k</math> 이하이다.
:<math>\chi(K_{n_1,\dotsc,n_k})\le k</math>
특히, 만약 <math>0<\min\{n_1,\dotsc,n_k\}</math>일 경우, 그 [[채색수]]는 <math>k</math>이다.
:<math>0<\min\{n_1,\dotsc,n_k\}\implies\chi(K_{n_1,\dotsc,n_k})=k</math>

=== 크기 ===
완전 <math>k</math>분 그래프 <math>K_{n_1,\dotsc,n_k}</math>의 꼭짓점의 수는
:<math>|V(K_{n_1,\dotsc,n_k})|=\sum_{i=1}^kn_k</math>
이며, 변의 수는
:<math>|V(K_{n_1,\dotsc,n_k})|=\prod_{i=1}^kn_k</math>
이다.

=== 그래프의 평면성 ===
{{본문|평면 그래프}}
[[평면 그래프]]는 <math>K_{3,3}</math>를 [[그래프 마이너]]로 가질 수 없다. 반대로, [[평면 그래프]]가 아닌 모든 그래프는 <math>K_{3,3}</math> 또는 <math>K_5</math>를 [[그래프 마이너]]로 갖는다 (바그너 정리 {{llang|en|Wagner’s theorem}})

== 예 ==
<gallery>
파일:Complete bipartite graph K3,1.svg|''K''<sub>3,1</sub>
파일:Complete bipartite graph K3,2.svg|''K''<sub>3,2</sub>
파일:Complete bipartite graph K3,3.svg|''K''<sub>3,3</sub>
</gallery>

== 역사 ==
이미 1669년에 [[아타나시우스 키르허]]가 완전 이분 그래프의 그림을 출판하였다.<ref name="knuth">{{서적 인용|장=Two thousand years of combinatorics|이름=Donald E.|성=Knuth|저자링크=도널드 크누스|제목=Combinatorics: Ancient and Modern|publisher=Oxford University Press|날짜=2013|editor1-first=Robin|editor1-last=Wilson|editor2-first=John J.|editor2-last=Watkins|쪽=7–37|언어=en}}</ref>

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

== 외부 링크 ==
* {{eom|title=Graph, bipartite}}
* {{매스월드|id=CompleteBipartiteGraph|title=Complete bipartite graph}}
* {{매스월드|id=CompleteTripartiteGraph|title=Complete tripartite graph}}
* {{매스월드|id=CompletekPartiteGraph|title=Complete ''k''-partite graph}}
{{위키데이터 속성 추적}}

[[분류:그래프]]