Seungkwan's Lab.

이분 그래프와 홀수 사이클

알고리즘
어떠한 그래프 G가 이분 그래프이면 길이가 홀수인 사이클이 존재하지 않습니다. 반대로 어떠한 그래프에 길이가 홀수인 사이클이 존재하지 않는다면 그 그래프는 이분 그래프입니다. 이에 대한 증명을 해보겠습니다.

용어 설명

이분 그래프 (Bipartite Graph): 그래프의 모든 정점을 그룹 A, B로 나눌수 있고, 같은 그룹내에서의 간선이 없는 그래프


이 그래프의 정점들을 {1, 3, 5, 7},  {2, 4, 6} 으로 나누면, 같은 그룹내에서의 간선이 없으므로 이분그래프입니다. 예시는 방향성 그래프이지만, 비방향성 그래프에서도 정의는 같습니다.


강결합 컴포넌트 (Strongly Connected Component): 방향성 그래프에서 다음 조건을 만족하는 정점들의 집합을 강결합 컴포넌트(SCC)라고 합니다.
1. SCC내의 임의의 두 정점 u, v사이의 u → v 경로와, v → u 경로가 항상 존재한다.
2. SCC내의 임의의 정점 u와, 외부의 임의의 정점 v 사이에, u → v 경로와, v → u 경로가 동시에 존재하는 경우는 없다.
즉, SCC는 내부의 모든 정점에서 내부의 다른 모든 정점으로 갈 수 있는 최대 그룹이라고 할 수 있습니다.
또한 모든 방향성 그래프는 한개 이상의 SCC들로 그룹화 될 수 있습니다.

이 그래프는 {1, 2, 4}, {3}, {5, 6} 이렇게 3개의 SCC들로 분리할 수 있습니다.

SCC에 대한 자세한 내용은 여기 참고


walk: 그래프 이론에서 walk란 중복되는 정점과 간선을 허용하는 경로입니다.
closed walk: 시작 정점과 끝 정점이 같은 walk

 예를들어 위의 그래프에서 [2 → 3 → 6 → 5 → 2 → 1] 는 walk 이고, [→ 4 → 2 → 3 → 6 → 5 → 2 → 1] 는 closed walk 입니다.

lemma 1:

어떠한 그래프가 홀수 길이의 closed walk를 가지고 있다면, 이 그래프는 반드시 홀수 길이의 사이클도 가지고 있다.

증명
길이가 홀수인 closed walk A가 있다 가정합시다.
1. 시작점과 끝점을 제외한 중복되는 정점이 없다면, A자체로 길이가 홀수인 사이클입니다.
2. 만약 중복되는 정점 x가 있다면, A = [a →  x … x  c  a] 와 같은 모양일 것입니다.
2-1. 만약 처음 x에서 두번 째 x까지의 길이가 홀수라면, [x  x]도 길이가 홀수인 closed walk이므로, [x  x]에 대해 이 과정을 처음부터 다시합니다.
2-2. 만약 짝수라면, [a →  x →  a] 처럼 두 x사이의 경로를 없앤 것도 길이가 홀수인 closed walk이다. 이것에 대해 이 과정을 처음부터 다시합니다.
위의 과정을 반복하여 중복되는 정점을 없애면, 결국 언젠가는 중복되는 정점이 모두 사라질 것이고, 길이가 홀수인 사이클이 남게 됩니다.



예를들어 이 그래프에서 [1 → 4 → 2 → 3 → 6 → 5 → 2 → 1] 는 길이가 홀수인 closed walk입니다. 중복되는 정점 2가 있고, [2 ~ 2]의 길이가 짝수이므로, 그 사이의 경로를 없애면 [1 → 4 → 2 → 1]이 됩니다. 이것 역시 길이가 홀수인 closed walk가 될 수밖에 없는데 , 더이상 중복되는 정점이 없으므로 이 자체로 길이가 홀수인 사이클입니다.

1. 어떠한 그래프 G가 이분 그래프이면, 길이가 홀수인 사이클이 존재하지 않는다.

이건 좀 직관적으로도 알 수 있을만큼 자명합니다. 굳이 증명을 하자면 어떠한 사이클 a[1]  a[2]  a[3] … a[k] → a[1]이 존재할 때 a[1]이 그룹 A에 속한다면, 이분 그래프이기 때문에 a[2]는 그룹 B에 속하고, a[3]는 그룹 A에 속합니다. 즉, a[i] 는 i가 홀수일때는 그룹 A에 속하고, i가 짝수일 때는 그룹 B에 속합니다. 이 사이클의 전체 길이가 홀수이기 위해서는 k가 홀수여야 합니다. 하지만 k가 홀수 일 때는 a[k]가 그룹 A에 속하고, 따라서 간선 (a[k]  a[1]) 이 존재할 수 없습니다.

2. 어떠한 그래프 G에 길이가 홀수인 사이클이 존재하지 않는다면, 그래프 G는 이분 그래프이다.

방향성 그래프의 경우에는 그래프를 강결합 컴포넌트들로 분리하여 따로 생각합니다. 비방향성 그래프이지만 연결 그래프가 아닐 때도 마찬가지로 컴포넌트별로 따로 생각합니다. 서로 다른 두 컴포넌트를 거치는 사이클은 존재할 수 없으므로, 각 컴포넌트들 내에서만 생각해도 문제가 없습니다.

그래프 G의 모든 사이클의 길이가 짝수라고 가정하고, 아무 정점이나 하나 잡아서 u라 합시다. 그래프의 모든 정점을 다음과 같이 그룹 A, B로 나눌 수 있습니다.
A = 그래프의 모든 정점 v중에, u에서 v로의 최단 거리가 짝수인 것들
B = 그래프의 모든 정점 v중에, u에서 v로의 최단 거리가 홀수인 것들
u자신은 그룹 A에 속한다.

이 때, 만약 A에 속하는 임의의 정점 a에 대해 u → a로 가는 길이가 짝수인 경로는 정의에 의해 당연히 존재합니다. 놀랍게도 a → u 로 가는 경로도 반드시 존재하며 길이가 짝수입니다. u와 a가 같은 컴포넌트에 있으므로 a → u로 가는 경로가 존재한다는 것은 자명합니다. 또한, 만약 a → u로 가는 경로가 홀수일 경우 u → v 경로와 합쳐저서 길이가 홀수인 closed walk가 됩니다. 그렇게되면 lemma1에 의해 길이가 홀수인 사이클도 존재하게 되는데, 이는 사이클의 길이가 짝수라는 가정에 모순입니다. 따라서 a → u로 가는 경로의 길이는 반드시 짝수입니다. 

그렇다면 A에 속하는 두 정점 a, b에 대해 u → a 로 가는 길이가 짝수인 경로가 존재하고, b → u로 가는 길이가 짝수인 경로 역시 존재한는 말이 됩니다. 이 때 만약 a에서 b로 가는 간선이 존재한다면 u → a → b → u 라는 길이가 홀수인 closed walk가 존재하게 되고, 이는 역시 가정에 모순입니다. 따라서 A에 속하는 임의의 두 정점  a, b 사이의 간선은 존재할 수 없습니다.

B에 대해서도 같은 방식으로 내부의 간선이 없다는 것을 증명할 수 있고, 따라서 어떠한 그래프 G에 길이가 홀수인 사이클이 존재하지 않는다면, 그래프 G는 이분 그래프입니다.