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

내용 삭제됨 내용 추가됨

인라인

2017년 4월 18일 (화) 03:40 판

그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 변이 X에 있는 꼭짓점과 Y의 꼭짓점을 잇는 형태로 되도록 꼭짓점의 집합을 두 개의 부분집합 X, Y로 나눌 수 있는 그래프이다. 다르게 표현하자면, 그래프의 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 경우 이분 그래프라고 한다.

정의

그래프 $\Gamma =(V,E)$ 와 자연수 $k\in \mathbb {N}$ 가 주어졌다고 하자. 만약 $V$ 가 다음과 같은 조건을 만족시키는 집합의 분할

V=V_{1}\sqcup V_{2}\sqcup \dotsb \sqcup V_{k}

을 가질 수 있다면, $\Gamma$ 를 $k$ 분 그래프(-分graph, 영어: $k$ -partite graph)라고 한다.

변으로 연결된 두 꼭짓점은 서로 다른 분할 성분에 속한다. 즉, 임의의 변 $(u,v)\in E$ 에 대하여, 만약 $u\in V_{i}$ 이며 $v\in V_{j}$ 라면, $i\neq j$ 이다.

즉, $\Gamma$ 의 색칠수가 $k$ 이하이어야 한다.

$k=2$ 일 때, 이를 이분 그래프라고 한다. 마찬가지로, $k=3$ 일 때, 이를 삼분 그래프(三分graph, 영어: tripartite graph)라고 한다.

성질

임의의 유한 그래프 $\Gamma$ 에 대하여 다음 두 조건이 서로 동치이다.

이분 그래프이다.
홀수 길이의 순환이 존재하지 않는다.

특히, 예를 들어 홀수 길이의 순환 그래프는 이분 그래프가 될 수 없다.

변별 알고리즘

주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 순환 그래프는 이분 그래프가 아니다.

예

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

완비 $k$ 분 그래프

집합 $V$ 의 $k$ 조각 분할

V=V_{1}\sqcup \dotsb V_{k}

가 주어졌다고 하자. 이 집합의 분할에 대응하는 완비 $k$ 분 그래프(영어: complete $k$ -partite graph)는 위와 같은 분할에 대하여 $k$ 분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다. 즉, 그 변의 집합은 다음과 같은 꼴이다.

E=\bigsqcup _{1\leq i<j\leq k}V_{i}\times V_{j}

데생당팡

리만 곡면에 대하여, 어떤 유한 평면 이분 그래프를 대응시킬 수 있다. 이를 데생당팡이라고 한다.

바깥 고리

“Graph, bipartite”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Bipartite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “k-partite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Complete bipartite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Complete tripartite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Complete k-partite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.

같이 보기

쾨니그의 정리

@@ 1번째 줄: / 1번째 줄: @@
 [[그림: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인 [[순환 그래프]]는 이분 그래프가 아니다.
+== 예 ==
+분 그래프는 공(空)그래프, 즉 꼭짓점과 변이 없는 그래프 밖에 없다. 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}}
 == 같이 보기 ==