이분 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻 넘어옴|쾨니그 정리|무한 그래프에 대한 정리|쾨니그 보조정리}}
{{다른 뜻 넘어옴|쾨니그 정리|[[기수 (수학)|기수]]에 대한 정리|쾨니그의 정리 (집합론)}}
[[파일:Complete bipartite graph K3,2.svg|섬네일|이분 그래프의 예]]
[[파일:Complete bipartite graph K32-RG001.svg|섬네일|위 그래프의 [[그래프 색칠]]]]
[[파일:Complete bipartite graph K32-001.svg|섬네일|2색변 이분 그래프의 예]]

[[그래프 이론]]에서, '''이분 그래프'''(二分graph, {{llang|en|bipartite graph}})란 모든 [[꼭짓점]]을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 [[그래프]]이다.

== 정의 ==
[[그래프]] <math>\Gamma=(V,E)</math>와 [[자연수]] <math>k\in\mathbb N</math>가 주어졌다고 하자. 만약 <math>V</math>가 다음과 같은 조건을 만족시키는 [[집합의 분할]]
:<math>V=V_1\sqcup V_2\sqcup\dotsb\sqcup V_k</math>
을 가질 수 있다면, <math>\Gamma</math>를 '''<math>k</math>분 그래프'''(-分graph, {{llang|en|<math>k</math>-partite graph}})라고 한다.
* 변으로 연결된 두 꼭짓점은 서로 다른 분할 성분에 속한다. 즉, 임의의 변 <math>(u,v)\in E</math>에 대하여, 만약 <math>u\in V_i</math>이며 <math>v\in V_j</math>라면, <math>i\ne j</math>이다.
즉, <math>\Gamma</math>의 [[색칠수]]가 <math>k</math> 이하이어야 한다.

<math>k=2</math>일 때, 이를 '''이분 그래프'''라고 한다. 마찬가지로, <math>k=3</math>일 때, 이를 '''삼분 그래프'''(三分graph, {{llang|en|tripartite graph}})라고 한다.

== 성질 ==
임의의 유한 [[그래프]] <math>\Gamma</math>에 대하여 다음 두 조건이 서로 [[동치]]이다.
* 이분 그래프이다.
* 홀수 길이의 [[순환 (그래프 이론)|순환]]이 존재하지 않는다.
특히, 예를 들어 홀수 길이의 [[순환 그래프]]는 이분 그래프가 될 수 없다.

이분 그래프의 [[색칠수]]는 2 이하이므로, [[비징의 정리]]에 대하여, 이분 그래프는 항상 1종 그래프이다. (꼭짓점의 최대 차수가 1 이하인 그래프는 자명하게 1종 그래프이다.)

=== 쾨니그 정리 ===
[[파일:Koenigs-theorem-graph.svg|섬네일|오른쪽|쾨니그 정리에 따르면, 이분 그래프에서, [[최대 부합]]의 변(청색) 수는 최소 꼭짓점 덮개의 꼭짓점(적색) 수와 같다.]]
'''쾨니그 정리'''(Kőnig定理, {{llang|en|Kőnig’s theorem}})에 따르면, 이분 그래프의 경우 대한 최소 꼭짓점 덮개 문제와 [[최대 부합]] 문제가 서로 [[동치]]이다.

구체적으로, 어떤 [[그래프]] <math>\Gamma</math>의 '''꼭짓점 덮개'''({{llang|en|vertex cover}}) <math>C\subset V(\Gamma)</math>는 다음을 만족시키는 집합이다.
* 모든 변 <math>e\in E(\Gamma)</math>에 대하여, <math>e</math>와 접하는 <math>c\in C</math>가 존재한다.
'''최소 꼭짓점 덮개'''({{llang|en|minimal vertex cover}})는 포함 관계에 대하여 [[최소 원소]]인 꼭짓점 덮개이다.

'''쾨니그 정리'''에 따르면, 유한 이분 그래프 <math>\Gamma</math>의 [[최대 부합]] <math>M\subset E(\Gamma)</math> 및 최소 꼭짓점 덮개 <math>C\subset V(\Gamma)</math>에 대하여,
:<math>|M|=|C|</math>
이다.<ref name="윤영진">{{서적 인용|저자=윤영진|제목=새로운 조합수학|출판사=교우사|날짜=2007|isbn=978-89-8172-379-8|url=http://www.kyowoo.co.kr/02_sub/view.php?p_idx=334|언어=ko}}</ref>{{rp|289}}

조합적 집합론에서는 쾨니그 정리를 일반화하는 [[홀 결혼 정리]]가 존재한다. 쾨니그 정리와 홀의 정리 및 [[딜워스의 정리]]는 서로 [[동치]]이다.

=== 변별 알고리즘 ===
주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 그래프의 꼭짓점들을 [[깊이 우선 탐색]]으로 나열한 뒤, 각 꼭짓점들을 이웃 꼭짓점들과 다른 색으로 계속해서 칠해 나가면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 된다. 이 알고리즘은 ''O''(|''V''|+|''E''|)이다.

== 예 ==
0분 그래프는 [[공 그래프]] (꼭짓점과 변이 없는 그래프) 밖에 없다. 1분 그래프는 이산 그래프 (즉, 아무런 변이 없는 그래프)와 동치인 개념이다.

모든 [[나무 (그래프 이론)|나무]]는 ([[순환 (그래프 이론)|순환]]이 없으므로) 이분 그래프이다. 짝수 길이의 [[순환 (그래프 이론)|순환]]은 이분 그래프이지만, 홀수 길이의 [[순환 (그래프 이론)|순환]]은 이분 그래프가 아니다.

=== 완전 <math>k</math>분 그래프 ===
{{본문|완전 이분 그래프}}
집합 <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>

=== 데생당팡 ===
{{본문|데생당팡}}
[[리만 곡면]]에 대하여, 어떤 유한 [[평면 그래프|평면]] 이분 그래프를 대응시킬 수 있다. 이를 '''[[데생당팡]]'''이라고 한다.

== 역사 ==
쾨니그 정리는 [[쾨니그 데네시]]<ref>{{저널 인용
  | 저자 = Kőnig Dénes  | 저자링크=쾨니그 데네시 | 제목 = Gráfok és mátrixok
  | journal = Matematikai és Fizikai Lapok
  | volume = 38
  | 날짜 = 1931
  | pages = 116–119 | zbl = 0003.32803 | 언어=hu}}</ref>와 [[에게르바리 예뇌]]<ref>{{저널 인용|성=Egerváry|이름=Jenő|저자링크=에게르바리 예뇌 |날짜=1931|제목=Matrixok kombinatorius tulajdonságairól|저널=Matematikai és Fizikai Lapok|권=38|쪽=16–28|언어=hu}}</ref>가 각자 독자적으로 1931년에 증명하였다.

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Graph, bipartite}}
* {{eom|title=König theorem}}
* {{매스월드|id=BipartiteGraph|title=Bipartite graph}}
* {{매스월드|id=BicolorableGraph|title=Bicolorable graph}}
* {{매스월드|id=Three-ColorableGraph|title=Three-colorable graph}}
* {{매스월드|id=k-PartiteGraph|title=''k''-partite graph}}
* {{매스월드|id=k-ColorableGraph|title=''k''-colorable graph}}
* {{매스월드|id=KoenigsLineColoringTheorem|title=König's Line Coloring Theorem}}
* {{매스월드|id=Koenig-EgevaryTheorem|title=König-Egeváry Theorem}}
* {{nlab|id=bipartite graph|title=Bipartite graph}}

[[분류:이분 그래프| ]]
[[분류:그래프족]]
[[분류:홀짝성]]