6-13. 그래프: Bipartite Graph (이분 그래프)

1. 이분 그래프(Bipartite Graph)의 이해

그래프 이론에서 이분 그래프(Bipartite Graph)는 특별한 성질을 갖는 그래프의 한 종류입니다. 일반적인 그래프는 노드(Vertex)와 간선(Edge)으로 이루어져 있으며, 각 간선은 두 노드를 연결합니다. 이분 그래프는 이러한 일반적인 그래프의 구조를 가지면서도, 노드들을 두 개의 독립적인 집합으로 나눌 수 있다는 특징을 가지고 있습니다. 이 두 집합을 보통 X와 Y로 표현하며, 그래프 내의 모든 간선은 X 집합의 노드와 Y 집합의 노드를 연결합니다. 즉, 같은 집합 내의 노드 간에는 간선이 존재하지 않습니다.

이러한 구조적 특징 때문에 이분 그래프는 다양한 문제 해결에 활용될 수 있습니다. 특히, 매칭(Matching) 문제, 할당(Assignment) 문제, 스케줄링(Scheduling) 문제 등에서 핵심적인 역할을 합니다.

예를 들어, 친구 관계를 이분 그래프로 표현할 수 있습니다. X 집합은 남학생, Y 집합은 여학생을 나타내고, 간선은 친구 관계를 의미합니다. 이 경우, 남학생끼리, 또는 여학생끼리 친구 관계를 맺는 경우는 없으므로, 이분 그래프의 조건을 만족합니다.

2. 이분 그래프의 수학적 정의

이분 그래프는 수학적으로 다음과 같이 정의될 수 있습니다.

그래프 $G = (V, E)$가 주어졌을 때, 여기서 $V$는 노드의 집합, $E$는 간선의 집합을 나타냅니다. $G$가 이분 그래프가 되기 위한 조건은 다음과 같습니다.

1. $V$는 두 개의 공집합이 아닌(non-empty) 부분 집합 $X$와 $Y$로 분할될 수 있어야 합니다. 즉, $V = X \cup Y$ 이고, $X \cap Y = \emptyset$ 이어야 합니다.
2. 모든 간선 $(u, v) \in E$에 대해, $u \in X$ 이고 $v \in Y$ 이거나, $u \in Y$ 이고 $v \in X$ 이어야 합니다. 즉, 같은 집합 내의 노드 간에는 간선이 존재하지 않아야 합니다.

이 정의를 통해 이분 그래프는 특정 구조를 가진 그래프임을 알 수 있으며, 이 구조적 특성이 다양한 알고리즘의 적용을 가능하게 합니다.

3. 이분 그래프 판별 알고리즘

주어진 그래프가 이분 그래프인지 판별하는 알고리즘은 비교적 간단하며, 주로 너비 우선 탐색(Breadth-First Search, BFS) 또는 깊이 우선 탐색(Depth-First Search, DFS)을 활용합니다.

1) 알고리즘 개요

알고리즘의 핵심 아이디어는 그래프의 각 노드에 색상을 할당하는 것입니다. 두 가지 색상(예: 0과 1)을 사용하여, 인접한 노드들은 서로 다른 색상을 갖도록 합니다. 만약 그래프를 전체적으로 색칠하는 과정에서 모순이 발생한다면, 즉 인접한 두 노드가 같은 색상을 갖게 된다면, 그 그래프는 이분 그래프가 아닙니다.

2) BFS 기반 판별 알고리즘

BFS를 사용하여 이분 그래프를 판별하는 알고리즘은 다음과 같습니다.

1. 그래프의 모든 노드를 방문하지 않은 상태로 초기화합니다. 각 노드의 색상은 -1로 초기화합니다(아직 색칠되지 않음을 의미).
2. 방문하지 않은 노드를 하나 선택하고, 해당 노드의 색상을 0으로 설정합니다.
3. BFS를 시작하여, 선택된 노드에서 인접한 노드들을 탐색합니다.
   • 인접한 노드가 아직 방문하지 않은 상태라면, 해당 노드의 색상을 현재 노드의 반대 색상으로 설정합니다.
   • 인접한 노드가 이미 방문한 상태이고, 현재 노드와 같은 색상을 가지고 있다면, 이분 그래프가 아님을 의미하므로 false를 반환합니다.
4. 모든 노드를 탐색한 후, 모순이 발생하지 않았다면 이분 그래프이므로 true를 반환합니다.

3) DFS 기반 판별 알고리즘

DFS를 사용하여 이분 그래프를 판별하는 알고리즘은 다음과 같습니다.

1. 그래프의 모든 노드를 방문하지 않은 상태로 초기화합니다. 각 노드의 색상은 -1로 초기화합니다.
2. 방문하지 않은 노드를 하나 선택하고, 해당 노드의 색상을 0으로 설정합니다.
3. DFS를 시작하여, 선택된 노드에서 인접한 노드들을 탐색합니다.
   • 인접한 노드가 아직 방문하지 않은 상태라면, 해당 노드의 색상을 현재 노드의 반대 색상으로 설정하고, DFS를 재귀적으로 호출합니다.
   • 인접한 노드가 이미 방문한 상태이고, 현재 노드와 같은 색상을 가지고 있다면, 이분 그래프가 아님을 의미하므로 false를 반환합니다.
4. 모든 노드를 탐색한 후, 모순이 발생하지 않았다면 이분 그래프이므로 true를 반환합니다.

4) 코드 예시 (Python, BFS)

from collections import deque

def is_bipartite(graph):
  """
  주어진 그래프가 이분 그래프인지 판별합니다.

  Args:
    graph: 인접 리스트로 표현된 그래프. graph[i]는 노드 i에 인접한 노드들의 리스트입니다.

  Returns:
    그래프가 이분 그래프이면 True, 그렇지 않으면 False를 반환합니다.
  """
  n = len(graph)
  colors = [-1] * n  # 각 노드의 색상을 저장. -1: 미방문, 0: 색상 0, 1: 색상 1

  for start_node in range(n):
    if colors[start_node] == -1:  # 아직 방문하지 않은 노드인 경우
      queue = deque([start_node])
      colors[start_node] = 0  # 시작 노드의 색상 설정

      while queue:
        u = queue.popleft()
        for v in graph[u]:
          if colors[v] == -1:  # 아직 방문하지 않은 노드인 경우
            colors[v] = 1 - colors[u]  # 인접 노드에 다른 색상 할당
            queue.append(v)
          elif colors[v] <mark class="highlight"> colors[u]:  # 이미 방문했고 색상이 같은 경우
            return False  # 이분 그래프가 아님

  return True  # 모든 노드를 탐색했고 모순이 없으면 이분 그래프

5) 알고리즘 분석

BFS 및 DFS 기반의 이분 그래프 판별 알고리즘은 시간 복잡도 O(V + E)를 갖습니다. 여기서 V는 노드의 수, E는 간선의 수입니다. 이는 각 노드와 간선을 한 번씩 방문하기 때문입니다. 공간 복잡도는 인접 리스트(또는 인접 행렬)를 사용하는 경우 O(V + E), BFS/DFS에 필요한 큐 또는 스택의 공간으로 인해 O(V)입니다.

4. 이분 그래프의 응용

이분 그래프는 다양한 실생활 및 컴퓨터 과학 문제에 적용될 수 있습니다.

1) 매칭 문제

이분 그래프의 가장 대표적인 응용 중 하나는 매칭(Matching) 문제입니다. 매칭은 그래프의 간선 중에서 서로 인접하지 않은 간선들의 집합을 의미합니다. 이분 그래프에서는 X 집합의 노드와 Y 집합의 노드를 연결하는 간선들을 선택하여 매칭을 구성합니다.

• 최대 매칭(Maximum Matching): 선택된 간선의 수가 최대가 되도록 하는 매칭.
• 완전 매칭(Perfect Matching)==: 모든 노드가 매칭에 참여하는 매칭.

매칭 문제는 다음과 같은 상황에 적용될 수 있습니다.

• 구인-구직 매칭: 회사와 지원자를 연결하여 적합한 채용을 결정.
• 결혼 문제: 남성과 여성 간의 선호도를 고려하여 최적의 결혼 조합을 찾는 문제.
• 작업 할당: 작업과 작업을 수행할 수 있는 사람을 연결하여 효율적인 작업 할당을 결정.

2) 네트워크 플로우

이분 그래프는 네트워크 플로우(Network Flow) 문제에도 활용될 수 있습니다. 네트워크 플로우는 그래프 내에서 소스(Source) 노드에서 싱크(Sink) 노드로 흘려보낼 수 있는 최대 유량을 계산하는 문제입니다.

이분 그래프를 활용하여 네트워크 플로우 문제를 해결하는 방법은 다음과 같습니다.

1. 이분 그래프를 구축합니다.
2. 소스 노드와 싱크 노드를 추가합니다. 소스 노드는 X 집합의 모든 노드에 연결하고, 싱크 노드는 Y 집합의 모든 노드에 연결합니다. 이때, 각 간선의 용량(Capacity)은 1로 설정합니다.
3. 포드-풀커슨(Ford-Fulkerson) 알고리즘 또는 에드몬드-카프(Edmonds-Karp) 알고리즘과 같은 최대 유량 알고리즘을 사용하여 최대 유량을 계산합니다. 최대 유량은 이분 그래프의 최대 매칭 크기와 동일합니다.

3) 기타 응용

• 스케줄링 문제: 작업과 시간을 이분 그래프로 표현하여, 각 작업이 특정 시간에 수행될 수 있는지 여부를 매칭을 통해 결정.
• 데이터 마이닝: 연관 규칙 분석에서 항목 집합 간의 관계를 이분 그래프로 표현하고, 특정 항목 집합 간의 연관성을 분석.
• 이미지 처리: 이미지 분할, 객체 감지 등에서 픽셀 또는 객체 간의 관계를 모델링하는 데 사용.

5. 주의사항과 트러블 슈팅

1) 그래프 표현

이분 그래프를 구현할 때는 그래프를 표현하는 방식을 신중하게 선택해야 합니다. 일반적으로 인접 리스트(Adjacency List) 방식을 사용하며, 필요한 경우 인접 행렬(Adjacency Matrix) 방식을 사용할 수도 있습니다. 인접 리스트는 메모리 효율적이며, 희소 그래프(sparse graph)에 적합합니다. 인접 행렬은 노드 간의 연결 여부를 빠르게 확인해야 하는 경우에 유용하지만, 밀집 그래프(dense graph)에 적합하며, 메모리 사용량이 많습니다.

2) 사이클의 존재

이분 그래프는 사이클이 존재할 수 있습니다. 그러나 이분 그래프의 사이클은 항상 짝수 길이를 갖습니다. 홀수 길이의 사이클이 존재한다면, 해당 그래프는 이분 그래프가 아닙니다.

3) 구현상의 오류

BFS 또는 DFS 기반의 이분 그래프 판별 알고리즘을 구현할 때, 다음과 같은 오류에 유의해야 합니다.

• 초기화 오류: 노드의 색상 초기화를 제대로 하지 않으면, 잘못된 결과를 얻을 수 있습니다.
• 탐색 범위 오류: 모든 노드를 올바르게 탐색하지 않으면, 그래프의 모든 연결 상태를 파악하지 못할 수 있습니다.
• 예외 처리 오류: 인접 노드의 색상을 갱신하는 과정에서 예외 상황(예: 이미 방문한 노드의 색상이 현재 노드와 같은 경우)을 제대로 처리하지 않으면, 정확한 판별이 어려울 수 있습니다.

6. 결론

이분 그래프는 그래프 이론의 중요한 개념이며, 다양한 실용적인 문제 해결에 활용될 수 있습니다. 이분 그래프의 정의, 판별 알고리즘, 응용 사례 등을 이해하는 것은 그래프 이론과 알고리즘 분야에서 중요한 역량을 키우는 데 도움이 됩니다. 특히, 매칭 문제, 네트워크 플로우 문제, 스케줄링 문제 등에서 이분 그래프는 핵심적인 역할을 수행하므로, 관련 지식을 숙지하는 것이 중요합니다.