"이분 그래프"의 두 판 사이의 차이

2,197 바이트 추가됨 ,  4년 전
편집 요약 없음
[[그림:Complete bipartite graph K3,2.svg|thumb|200px|이분 그래프의 예]]
 
[[그래프 이론]]에서, '''이분 그래프'''(二分graph, {{llang|en|bipartite graph}})란 모든 변이 X에 있는 꼭짓점과 Y의 꼭짓점을 잇는 형태로 되도록 꼭짓점의 집합을 두 개의 부분집합 X, Y로 나눌 수 있는 그래프이다.
다르게 표현하자면, 그래프의 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 경우 이분 그래프라고 한다.
같은 말로 [[색칠수]] χ(G)가 2이하인 경우이다.
[[File:Complete bipartite graph K32-001.svg|thumb|2색변 이분 그래프의 예]]
 
[[그래프 이론]]에서, '''이분 그래프'''(二分graph, {{llang|en|bipartite graph}})란 모든 변이 X에 있는 꼭짓점과 Y의 꼭짓점을 잇는 형태로 되도록 꼭짓점의 집합을 두 개의 부분집합 X, Y로 나눌 수 있는 그래프이다. 다르게 표현하자면, 그래프의 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 경우 이분 그래프라고 한다.
 
== 정의 ==
[[그래프]] <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>에 대하여 다음 두 조건이 서로 [[동치]]이다.
홀수 길이의 [[순환 그래프]]가 이분 그래프가 아니라는 점은 쉽게 증명할 수 있다. 아울러 다음과 같은 더 강력한 정리가 쉽게 증명된다. 그래프가 이분 그래프일 필요충분조건은 홀수 길이의 [[순환 (그래프 이론)|순환]]이 없다는 것이다.
* 이분 그래프이다.
* 홀수 길이의 [[순환 (그래프 이론)|순환]]이 존재하지 않는다.
특히, 예를 들어 홀수 길이의 [[순환 그래프]]는 이분 그래프가 될 수 없다.
 
== 변별 알고리즘 ==
[[File:Complete bipartite graph K32-RG001.svg|thumb|이분 그래프의 변별 알고리즘 적용]]
주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 [[순환 그래프]]는 이분 그래프가 아니다.
 
== 예 ==
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>
 
=== 데생당팡 ===
{{본문|데생당팡}}
[[리만 곡면]]에 대하여, 어떤 유한 [[평면 그래프|평면]] 이분 그래프를 대응시킬 수 있다. 이를 '''[[데생당팡]]'''이라고 한다.
 
== 바깥 고리 ==
* {{eom|title=Graph, bipartite}}
* {{매스월드|id=BipartiteGraph|title=Bipartite graph}}
* {{매스월드|id=k-partiteGraph|title=''k''-partite graph}}
* {{매스월드|id=CompleteBipartiteGraph|title=Complete bipartite graph}}
* {{매스월드|id=CompleteTripartiteGraph|title=Complete tripartite graph}}
* {{매스월드|id=Completek-partiteGraph|title=Complete ''k''-partite graph}}
 
== 같이 보기 ==