그래프 G가 bipartite면 G는 홀수 cycle을 가지지 않는다. (bipartite) / Graph Theory #2

Bipartite의 정의

제목에서 “그래프 G가 bipartite면 G는 홀수 cycle을 가지지 않는다.” 라고 했지만 역도 성립한다.

A graph is bipartite iff it has no odd cycle.

위의 정리를 이해하려면 bipartite graph가 무엇인지 알아야 한다. 정의는 다음과 같다.

A graph G is bipartite if V(G) is the union of two disjoint (possibly empty) independent sets.

정의가 한 번에 이해가 되지는 않는다. 자세히 풀어보면, 그래프 G의 vertices가 두 개의 disjoint independent sets의 합집합이라고 한다. 그 두 개의 집합을 XY라고 하자. XY의 관계는 다음과 같다.

  1. XY는 vertex의 집합이다.
  2. XYG의 vertices의 partition이다. 즉, X\cup Y=V(G)이고 X\cap Y=\phi이다.
  3. X는 independent set이어서 V(X) 간에 edge가 존재하지 않는다. 마찬가지로 V(Y) 간에도 edge가 존재하지 않는다.

그림으로 이해해보면 아래와 같은 그래프가 bipartite이다. 그림과 같이 disjoint independent set XY를 정의하면, XY-bipartite라고 부르기도 한다.

간단하게 정리면 vertices를 두 개의 집합으로 partition하고 각 집합 내부에는 edge가 없고, 집합 간에 edge만 있는 것을 bipartite라고 한다.

Thm. A graph is bipartite iff it has no odd cycle.

닫힌 홀수 walk가 홀수 cycle을 포함한다. 따라서 이 정리가 성립한다면, 그래프 안에서 닫힌 홀수 walk가 있으면 bipartite가 아니라고도 정리할 수 있겠다.

Bipartite → No odd cycle

그래프 G가 bipartite이므로 위의 그림과 같이 XY-bipartite라고 가정하자. X의 vertex 중 하나인 x_i에서 시작해서 path를 만들어보자. Path의 길이가 홀수이면 x_i외의 endpoint가 Y에 속한 vertex라는 것을 알 수 있다. (길이가 짝수라면 다른 endpoint도 X에 속한 vertex가 된다.) 따라서, path의 endpoint가 x_i가 되는 것이 불가능하고, cycle이 될 수 없다. 결과적으로, 그래프 G가 bipartite일 때, 홀수 cycle이 존재할 수 없다.

No odd cycle → Bipartite

정리를 살짝 변형해서 다음과 같이 적자.

If the graph G with n vertices has no odd cycle, it is bipartite.

n에 대해서 수학적 귀납법을 적용하여 증명을 진행해보자. n=2인 경우, edge의 유무와 상관없이 그래프는 항상 bipartite가 된다. 조금 더 진행하여 보면 n=3인 경우, edge가 1개, 2개일 때는 홀수 cycle이 없지만 edge가 3개인 경우 홀수 cycle이 생기므로 edge가 3개인 경우는 다루지 않는다. edge가 1개, 2개인 경우도 모두 bipartite가 된다는 것을 확인할 수 있다.

이제 vertices가 n=k-1개인 그래프 G가 홀수 cycle이 없을 때, G가 bipartite라고 가정하자. 그래프 GXY-bipartite라고 할 때, XY의 vertices를 각각x_iy_i라고 하자.

하나의 vertex vG에 추가한 G'~(n=k)이 홀수 cycle이 없으면, G'가 여전히 bipartite인지 경우를 나누어서 확인하여 보자.

  1. vx_i 혹은 y_i와만 edge를 가지는 경우
    만약 vx_i와 edge를 가지고 y_i와는 edge를 가지지 않는다면 vY에 속하면 G'는 bipartite이다. 반대의 경우라면 반대로 vX에 속하면 G'가 bipartite가 된다.
  2. v의 neighbor인 x_iy_jG (G'이 아니고 G이다.) 에서 connected인 경우
    x_iy_j가 connected라면, x_i에서 y_j로 가는 walk가 존재하고 이 walk의 길이는 홀수이다. v가 추가되었기 때문에 이 walk를 다음과 같이 닫힌 walk로 만들 수 있다. (x_i~\cdots~y_j~v~x_i) 이 닫힌 walk의 길이는 홀수이다. 닫힌 홀수 walk는 홀수 cycle을 포함하기 때문에, G'은 홀수 cycle을 가진다. 따라서, 이 경우는 제외할 수 있다.
  3. v의 neighbor인 x_iy_jG (G'이 아니고 G이다.) 에서 disconnected인 경우
    x_iy_j는 disconnected이기 때문에, x_i에서 y_j로 가는 walk 가 없다. 집합 Yx_i와 connected vertices만 모은 Y_ix_i와 disconnected vectices만 모은 Y_i'로 partition하자. y_jY_i'에 속할 것이다. 마찬가지로, 집합 Xx_i와 connected vertices만 모은 X_ix_i와 disconnected vertices만 모은 X_i'로 partition하자. 아래의 그림처럼 X_iY_i는 connected이고, X_iY_iX_i'Y_i'와 disconnected이다.
    이 때, X_iY로 옮기고, Y_iX로 옮기면 x_iy_i가 모두 Y의 vertices가 된다. 따라서, vX의 vertex로 설정하면 bipartite가 유지된다.

위의 3가지 경우에 따라서 n=k-1일 때, G가 bipartite이면 n=k일 때도 bipartite가 유지되는 것을 확인하였다. 따라서 “If the graph G with n vertices has no odd cycle, it is bipartite.” 가 성립한다.

Leave a Comment

Index