[algorithm] 이분그래프 (Bipartite Graph)

🧐 이분 그래프(Bipartite Graph)

 

---

1. 이분 그래프란?

이분 그래프는 정점 집합을 두 그룹으로 나눌 수 있는 그래프다.

 

✅ 이분그래프 조건

정점을 두 집합 U, V로 나누었을 때 모든 간선은 반드시 U의 정점과 V의 정점 사이에만 존재해야 한다.
(즉, 같은 집합에 있는 정점끼리는 연결되면 안 됨)

 

그래프를 색칠하는 관점에서 보면 두 가지 색만으로 인접한 정점끼리 서로 다른 색을 칠할 수 있다면 이분 그래프

 

 

✅ 완전 이분 그래프

 

 

✅ 부분 연결 이분그래프

 

✅ 불완전 이분그래프

 

 

✅ 예시

• 친구 관계 그래프에서 "남자 ↔ 여자"만 연결되어 있는 구조
• 체스판처럼 흑백이 번갈아 연결되어 있는 구조

---

2. 이분 그래프 판별 방법 (BFS / DFS)

이분 그래프인지 판별하는 대표적인 방법은 그래프 탐색 (BFS 또는 DFS) 를 활용해 색칠하는 방법이다.

 

 

✅ 알고리즘 개요

1. 아무 정점이나 선택해서 색 A로 칠하기
2. 인접한 정점은 반대 색(B)으로 칠하기
3. 다시 그 인접 정점의 인접 정점은 A로 칠하고… 반복
4. 어떤 순간에 인접한 두 정점이 같은 색이라면, 이분 그래프가 아님

 

✅ Python 예시 (BFS 기반)

from collections import deque

def is_bipartite(graph):
    n = len(graph)
    color = [0] * n  # 0: 방문 안 함, 1: 색 A, -1: 색 B

    for start in range(n):
        if color[start] != 0:
            continue

        queue = deque([start])
        color[start] = 1

        while queue:
            now = queue.popleft()
            for neighbor in graph[now]:
                if color[neighbor] == 0:
                    color[neighbor] = -color[now]
                    queue.append(neighbor)
                elif color[neighbor] == color[now]:
                    return False  # 같은 색이 인접했다면 이분 그래프 아님

    return True

 

 

 

---

3. 이분 그래프 활용

 

✅ 이분그래프 응용 예시

• 최대 매칭 알고리즘 (Bipartite Matching)
  예: 남녀 커플 매칭, 구직자 ↔ 기업 매칭 등
• 색칠 문제
  2색 문제 해결 시, 이분 그래프 조건을 만족하는지 확인
• 이분 그래프 기반 이분 탐색 문제
• Bipartite Check + Union-Find 조합으로 나오는 문제들