이분 그래프

이분 그래프

정의 1

그래프 $G$ 의 버텍스 $V(G)$ 에 대해 파티션 $\left\{ A,B \right\}$ 가 존재하고 모든 $xy \in E(G)$ 에 대해 $x \in A, y \in B$ 혹은 $x \in B , y \in A$ 이면 $G$ 를 이분 그래프라 부르고 $G = G(A,B)$ 와 같이 나타내기도 한다.

설명

이분 그래프는 그 이름 그대로 버텍스가 두 부류로 나뉘며, 같은 부류끼리는 인접하지 않은 그래프다. 가령 다음의 그림을 보면 주황색 버텍스 끼리는 인접하지 않고, 파란색 버텍스끼리는 인접하지 않다.

20200211\_153238.png

보다시피 다른 파티션에 있다고 해서 반드시 인접해야하는 것은 아니다. 만약 그렇다면 완전 이분 그래프Complete Bipartite Graph라 부른다. 만약 파티션이 세 개의 집합으로 만들어진다면 삼분 그래프Tripartite Graph라 부른다. 당연히 $n$ 개의 파티션에 대해 일반화가 가능하지만, 보통 연구의 대상으로는 이분 그래프로 충분한 경우가 많다.

한편 이분 그래프는 다음과 같이 사이클과 관련된 정리가 알려져있다.

정리

$G$ 는 연결 그래프라고 하자. $G$ 가 이분 그래프인것과 $G$ 의 모든 사이클의 길이는 짝수인 것은 동치다.

증명

$(\Rightarrow)$

$G = G(A,B)$ 가 이분 그래프라고 두자. $G$ 의 사이클이 $A$ 의 버텍스에서 시작했다면 $B$ 로 갔다가 $A$ 로 돌아올 때 두 번의 에지를 거쳐야한다. 따라서 $B$ 에 몇 번을 가더라도 닫힌 패스가 되려면 결국 짝수번만큼의 에지를 거칠 수밖에 없다. 따라서 $G$ 의 모든 사이클의 길이는 짝수여야한다.


$(\Leftarrow)$

$G$ 의 버텍스 $v \in V(G)$ 하나를 픽스하자. 시점이 $v$ 이고 종점이 $w$ 인 가장 짧은 패스 중 길이가 짝수인 $w \in V(G)$ 들을 모아놓은 집합을 $A \subset V(G)$ 라고 하고 그렇지 않은 버텍스의 집합을 $B := V(G) \setminus A$ 와 같이 두자. 만약 $A$ 에 속한 두 버텍스 $a_{1}$ 와 $a_{2}$ 가 인접하다면 다음과 같은 사이클 $$ v \to \cdots \to a_{1} \to a_{2} \to \cdots \to v $$ 의 길이는 $A$ 의 정의에 따라 홀수가 된다. 그러나 전제에서 $G$ 의 모든 사이클의 길이는 짝수이므로 이는 모순이고, $A$ 에 있는 버텍스끼리는 인접하지 않다. 이는 $B$ 의 버텍스도 마찬가지다. 다라서 $G$ 는 이분 그래프 $G(A,B)$ 여야만 한다.


  1. Wilson. (1970). Introduction to Graph Theory: p18. ↩︎

댓글