이분 그래프

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

정의

그래프 $\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$ 에 대하여 다음 두 조건이 서로 동치이다.

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

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

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

변별 알고리즘

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

예

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.
“König theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Bipartite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Bicolorable graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Three-colorable graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “k-partite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “k-colorable graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “König's Line Coloring Theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “König-Egeváry Theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.
“Bipartite graph”. 《nLab》 (영어).