‘그래프’라고 하면 흔히 함수 y = f(x)를 나타내 주는 그림, 혹은 여러 통계 자료를 나타내 주는 막대그래프, 꺾은선그래프 등을 생각하시는 분들이 많을 것입니다. 이 기사에서 다룰 그래프는 이것과는 다른 개념으로, 점들과 두 점을 잇는 변들로 이루어진 구조를 말합니다. 이러한 그래프에 대해 다루는 것이 바로 그래프 이론이며, 정보과학뿐만 아니라 물리, 화학 등 다양한 분야에 걸쳐 활용되고 있습니다. 이번 기사에서는 그래프의 한 종류인 이분 그래프(bipartite graph)에 대해 다뤄보고자 합니다. 그래프에 대한 기본적인 내용을 알고 가는 것이 기사 내용을 이해하는 데 도움이 되기 때문에, 이 내용의 경우 정지훈 기자가 작성한 <그래프이론, 세상을 바꾸다> 기사를 참고하시면 됩니다.
이분 그래프 (Bipartite Graph)
이분 그래프는 그래프의 한 종류로, 인접한 꼭짓점을 서로 다른 색으로 칠할 때 두 가지 색으로만 칠할 수 있는 그래프를 말합니다. 즉 꼭짓점들의 집합 V와 변들의 집합 E로 이루어진 그래프 G = (V, E)가 이분 그래프라면, 꼭짓점들의 집합 V가 두 집합 A, B로 나눠져 E에 속한 모든 변들이 A와 B사이에만 존재하도록 할 수 있다는 것을 의미합니다.
V = {1, 2, 3, 4, 5, 6}
E = {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {3, 6}, {4, 5}, {5, 6}}
[그림1]은 이분 그래프의 예시로, 오른쪽 그림처럼 A = {1, 3, 5}, B = {2, 4, 6}으로 나눠줬을 때 모든 변들이 A와 B사이에만 존재하게 되는 것을 확인할 수 있습니다. 하지만 만약 이 그래프에 {2, 4} 변을 하나 추가한다면 어떻게 될까요? 이 때는 어떻게 나누더라도 모든 변들이 A와 B사이에만 존재하게 할 수 없습니다. 그렇다면 임의의 그래프가 이분 그래프임을 확인할 수 있는 방법이 있을까요?
이분 그래프와 순환(Cycle)
이분 그래프가 되기 위한 조건을 생각하기에 앞서 먼저 살펴봐야 할 개념이 있는데, 바로 순환(cycle)입니다. 순환이란 말 그대로 한 꼭짓점에서 시작하여 원래의 꼭짓점으로 돌아올 수 있는 경로를 말합니다. 순환을 이루는 변의 개수를 순환의 길이라고 합니다. [그림1]의 경우 길이가 4인 <1, 2, 5, 4, 1>, 길이가 6인 <1, 2, 3, 6, 5, 4, 1>을 예시로 들 수 있습니다. 과연 그래프에서 순환이 이분 그래프인지 파악하는 데 도움을 줄 수 있을까요? [그림2]와 같이 순환을 이루는 꼭짓점들을 색칠해 봅시다.
1부터 빨간색으로 색칠할 때, 1과 인접한 2는 파란색으로 칠해져야 합니다. 마찬가지로 3은 빨간색, 4는 파란색으로 칠해져야 합니다. 즉 홀수의 경우 빨간색, 짝수의 경우 파란색으로 칠해져야 함을 알 수 있습니다. [그림2]를 보면 길이가 4인 왼쪽 순환은 마지막 꼭짓점과 처음 꼭짓점이 이분 그래프의 조건을 만족하는 한편, 길이가 3인 오른쪽 순환의 경우 마지막 꼭짓점인 1과 처음 꼭짓점인 이 같은 색으로 칠해져 이분 그래프의 조건을 만족할 수 없게 됩니다. 일반화하면 홀수 길이의 순환을 포함하고 있는 그래프는 이분 그래프가 될 수 없다는 결론을 얻을 수 있습니다. [그림1]의 그래프에 {2, 4}변을 추가했을 때도 마찬가지로 홀수 길이의 순환이 생기기 때문에 이분 그래프가 될 수 없었던 것입니다.
그렇다면 홀수 길이의 순환을 가지지 않을 때 반드시 이분 그래프가 될 수 있을까요? 지금부터는 이것에 대해 살펴보도록 하겠습니다.
BFS(Breadth-First Search)를 활용한 알고리즘
그래프에 홀수 길이의 순환이 있는지 판단하려면 그래프를 이루는 모든 꼭짓점과 변을 탐색해야 합니다. 이를 그래프 탐색(graph traversal)이라고 하는데, 그래프 탐색의 방법에는 대표적으로 BFS(Breadth-First Search)와 DFS(Depth-First Search)가 있습니다. 이 중 BFS를 활용하면 홀수 길이의 순환이 있는지 확인할 수 있는데, 지금부터 BFS가 어떻게 이루어지는지 살펴보겠습니다.
BFS를 수행하려면 탐색을 시작할 꼭짓점을 하나 정해줘야 하는데, 이것을 라고 하겠습니다. 를 시작으로 BFS는 다음 과정에 따라 진행됩니다.
① L0={s}라고 하자. 지금부터 L1, L2, ...에 나머지 꼭짓점들을 넣어 줄 것이다.
② i = 0에서 시작하자. ③-④는 Li로부터 Li+1을 만드는 과정이다.
③ Li에 있는 꼭짓점에서 인접한 모든 꼭짓점을 Li+1에 추가하되, L0, L1, ... , Li 에 속하지 않는 꼭짓점만 추가한다.
④ 에 모든 꼭짓점들을 다 추가했다면 를 1 늘린다.
⑤ 모든 꼭짓점들을 넣어줄 때까지 ③-④를 반복한다.
아래 동영상에는 BFS뿐만 아니라 DFS에 대한 설명도 포함되어 있습니다.
실제 예시를 통해 BFS가 어떻게 실행되는지 보겠습니다. 예를 들어 [그림1]의 그래프에서 s = 1로 두고 BFS를 실행한다면 [그림3]과 같은 결과를 얻게 됩니다. 이 결과로부터 어떻게 홀수 길이의 순환이 있는지 확인할 수 있을까요? 우선 꼭짓점들의 집합 L0, L1, ... 사이의 관계에 대해 살펴봅시다. 어떤 i와 2 이상인 j에 대해, Li 와 Li+j 사이에는 어떠한 변도 존재할 수 없습니다. 만약 그러한 변이 존재한다면 위 방법대로 BFS를 실행했을 때 Li+j 쪽에 속한 꼭짓점이 Li+j가 아니라 Li+1에 들어가야 할 테니까요.
만약 Li 에 속한 꼭짓점끼리의 변이 존재한다면 어떻게 될까요? 두 꼭짓점을 u, v라고 할 때 s에서 까지 이어지는 두 개의 경로를 생각해 봅시다. 두 경로에서 마지막으로 겹치는 꼭짓점을 w라고 하면 w-u-v-w로 구성된 순환은 어떤 순환이 될까요? 바로 홀수 길이의 순환이 되며, 따라서 이 경우 이분 그래프가 될 수 없습니다. [그림3]에서 {2, 4}를 추가했을 때 u=2, v=4, w=1을 대입해 보면 길이 3의 순환이 있는 것을 확인할 수 있죠.
이러한 경우가 아니라면 모든 i에 대해 오직 Li, Li+j 사이에만 변이 존재할 수 있습니다. 눈치채셨나요? A를 L0 U L2 U ..., 즉 L0, L2, ... 를 모두 합한 집합으로 하고 B = L1 U L3 U ... 으로 하면 오직 A와 B 사이에만 변이 존재하게 되고, 이분 그래프가 될 수 있습니다. 이것으로 우리는 홀수 길이의 순환이 없을 때 반드시 이분 그래프가 된다는 것을 보였습니다.
이분 매칭 문제
지금까지 주어진 그래프가 이분 그래프인지 판단할 수 있는 방법에 대해 알아보았다면, 이제 이분 그래프를 활용한 대표적인 실생활 속 문제에 대해 알아보겠습니다. 가장 유명한 문제로는 이분 매칭(bipartite matching)이 있는데, A와 B의 크기가 같은 이분 그래프가 주어졌을 때 A의 꼭짓점과 B의 꼭짓점을 하나씩 짝지어 모든 쌍이 인접하게 할 수 있는지, 나아가 최대 얼마나 많은 짝을 지어줄 수 있는지 판단하는 문제입니다. 예를 들어 [그림4]의 경우 빨강, 초록, 파랑으로 짝지어줄 수 있겠죠.
이분 매칭은 다양한 상황에서 활용될 수 있습니다. 이 기사에서 이분 매칭의 구체적인 해결 방법을 다루지는 않지만, 아래 동영상을 참고하시면 도움이 될 것입니다.
지금까지 이분 그래프에 대해 구체적으로 알아보았고, 그 활용에 대해서도 간단히 살펴보았습니다. 이분 그래프는 그래프 이론의 극히 일부에 불과하지만, 이 기사를 통해 그래프 이론에 대해 조금이나마 친숙해지는 시간이 되기를 바라며 기사를 마칩니다.
정민재 학생기자 | Mathematics & Computer Science | 지식더하기
참고자료
[1] https://www.ksakosmos.com/post/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%B4%EB%A1%A0-%EC%84%B8%EC%83%81%EC%9D%84-%EB%B0%94%EA%BE%B8%EB%8B%A4
[2] https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html
첨부 이미지 출처
모든 이미지는 자체 제작하였습니다.
첨부 동영상 링크
[1] https://www.youtube.com/watch?v=-wsYtm0x3nw
[2] https://www.youtube.com/watch?v=PwXNTA0rpXc
