📂그래프이론

이분 그래프

정의 ¹

그래프 $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)$ 와 같이 나타내기도 한다.

설명

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

보다시피 다른 파티션에 있다고 해서 반드시 인접해야하는 것은 아니다. 만약 그렇다면 완전 이분 그래프^{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)$ 여야만 한다.

■