이분 그래프 (Bipartite Graph)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 3분 · 1,020자/단어 #algorithm #graph #bipartite #bfs #dfs #2-coloring

정의

이분 그래프 (Bipartite Graph) 는 정점 집합 V 를 두 개의 독립 집합 L, R 로 분할할 수 있고, 모든 간선이 L 과 R 을 잇는 그래프. 같은 집합 내 정점끼리는 간선이 없다.

수학적 정의: G = (L ∪ R, E), 모든 (u, v) ∈ E 에 대해 u ∈ L, v ∈ R (또는 반대).

판정: 홀수 사이클이 없으면 이분 그래프. BFS/DFS 로 2-coloring 가능 여부를 O(V+E) 에 확인.

문제 상황과 동기

PS 에서 그룹 분리, 매칭 문제 는 대부분 이분 그래프.

naive: 모든 정점 부분집합 (2^V) 순회, 간선 유효성 체크 → 불가능.
BFS/DFS 2-coloring: 한 번 순회로 O(V+E).

핵심 통찰: 홀수 사이클 = 3색 이상 필요. 2색으로 칠해지면 곧 L/R 분할.

실무: 추천 시스템 (user-item), 작업 스케줄링 (task-worker), 관계망 (남녀 매칭).

시각화

핵심 아이디어

2-coloring: 시작 정점을 색 0, 인접 정점을 색 1, 그 인접을 다시 0…

BFS/DFS 순회 중 이미 방문한 정점이 같은 색이면 → 홀수 사이클 → 이분 그래프 아님.
모든 연결 요소에서 성공하면 이분 그래프.

invariant: color[u] XOR color[v] == 1 for all (u, v) ∈ E.

König 정리: 이분 그래프에서 최대 매칭 크기 = 최소 정점 덮개 크기.

Hall’s marriage theorem: L 의 모든 부분집합 S 에 대해 N(S) (S 의 이웃 집합) 크기가 |S| 이상이면 완전 매칭 존재.

알고리즘

is_bipartite(G):
    color[] = -1
    for u in V:
        if color[u] < 0:
            if not bfs_2color(u):
                return false
    return true

bfs_2color(start):
    queue = [start]
    color[start] = 0
    while queue not empty:
        u = queue.pop()
        for v in adj[u]:
            if color[v] < 0:
                color[v] = 1 - color[u]
                queue.push(v)
            elif color[v] == color[u]:
                return false  # 홀수 사이클
    return true

구현

// 이분 그래프 판정 BFS O(V+E)
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> adj[100005];
int color[100005];

bool bfs_2color(int start) {
  queue<int> q;
  q.push(start);
  color[start] = 0;
  while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v : adj[u]) {
          if (color[v] < 0) {
              color[v] = 1 - color[u];
              q.push(v);
          } else if (color[v] == color[u]) {
              return false;  // 홀수 사이클
          }
      }
  }
  return true;
}

int main() {
  cin >> n >> m;
  fill(color, color + n, -1);
  for (int i = 0; i < m; i++) {
      int u, v; cin >> u >> v; u--; v--;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  bool is_bip = true;
  for (int i = 0; i < n; i++) {
      if (color[i] < 0) {
          if (!bfs_2color(i)) {
              is_bip = false;
              break;
          }
      }
  }
  cout << (is_bip ? "이분 그래프" : "이분 그래프 아님") << "\n";
  if (is_bip) {
      vector<int> L, R;
      for (int i = 0; i < n; i++) {
          if (color[i] == 0) L.push_back(i + 1);
          else R.push_back(i + 1);
      }
      cout << "L: " << L.size() << ", R: " << R.size() << "\n";
  }
}

# 이분 그래프 판정 BFS O(V+E)
from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
color = [-1] * n

for _ in range(m):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  adj[u].append(v)
  adj[v].append(u)

def bfs_2color(start):
  q = deque([start])
  color[start] = 0
  while q:
      u = q.popleft()
      for v in adj[u]:
          if color[v] < 0:
              color[v] = 1 - color[u]
              q.append(v)
          elif color[v] == color[u]:
              return False  # 홀수 사이클
  return True

is_bip = True
for i in range(n):
  if color[i] < 0:
      if not bfs_2color(i):
          is_bip = False
          break

if is_bip:
  L = [i+1 for i in range(n) if color[i] == 0]
  R = [i+1 for i in range(n) if color[i] == 1]
  print("이분 그래프")
  print(f"L: {len(L)}, R: {len(R)}")
else:
  print("이분 그래프 아님")

// 이분 그래프 판정 BFS O(V+E)
import java.util.*;
import java.io.*;

public class Main {
  static int n, m;
  static List<Integer>[] adj;
  static int[] color;

  static boolean bfs2Color(int start) {
      Queue<Integer> q = new LinkedList<>();
      q.add(start);
      color[start] = 0;
      while (!q.isEmpty()) {
          int u = q.poll();
          for (int v : adj[u]) {
              if (color[v] < 0) {
                  color[v] = 1 - color[u];
                  q.add(v);
              } else if (color[v] == color[u]) {
                  return false;  // 홀수 사이클
              }
          }
      }
      return true;
  }

  @SuppressWarnings("unchecked")
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      n = Integer.parseInt(st.nextToken());
      m = Integer.parseInt(st.nextToken());
      adj = new ArrayList[n];
      color = new int[n];
      Arrays.fill(color, -1);
      for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken()) - 1;
          int v = Integer.parseInt(st.nextToken()) - 1;
          adj[u].add(v);
          adj[v].add(u);
      }
      boolean isBip = true;
      for (int i = 0; i < n; i++) {
          if (color[i] < 0) {
              if (!bfs2Color(i)) {
                  isBip = false;
                  break;
              }
          }
      }
      if (isBip) {
          int L = 0, R = 0;
          for (int c : color) {
              if (c == 0) L++;
              else R++;
          }
          System.out.println("이분 그래프");
          System.out.println("L: " + L + ", R: " + R);
      } else {
          System.out.println("이분 그래프 아님");
      }
  }
}

stdin

결과

이분 그래프
L: 3, R: 3

복잡도

항목	값
시간 (BFS/DFS)	O(V + E)
공간	O(V + E) (adjacency list + color[])
전처리	없음

König 정리와 이분 매칭

이분 그래프에서:

최대 매칭 (maximum matching): 최대 간선 부분집합 (양 끝점 중복 없음).
최소 정점 덮개 (minimum vertex cover): 모든 간선을 커버하는 최소 정점 집합.

König 정리: |최대 매칭| = |최소 정점 덮개|.

증명 (Kőnig-Egerváry): 최대 매칭 M 에서 증가 경로가 없으면, M-alternating path 의 끝점들이 최소 정점 덮개.

응용: 간선 선택 문제 = 정점 선택 문제 dual.

변형

가중치 이분 매칭 (Hungarian algorithm): 최대 가중 매칭 O(V^3).
Hopcroft-Karp: 최대 매칭 O(E√V) (다음 항목 이분 매칭 참고).
완전 이분 그래프 K_{m,n}: 모든 L-R 간선 존재. 간선 수 m·n.
Hall’s marriage theorem: 완전 매칭 존재 조건.

함정

1. 연결 요소 여러 개

각 연결 요소마다 BFS 시작. 한 번만 돌리면 놓침.

2. 자기 루프

자기 루프 (u, u) 가 있으면 같은 색 = 홀수 사이클 = 이분 아님. 입력 필터링.

3. 멀티 엣지

중복 간선은 2-coloring 에 영향 없음. 단, 매칭 문제에서는 카운트 주의.

4. 방향 그래프

이분 그래프 판정은 무방향 그래프. 방향 그래프는 underlying undirected 로 변환 후 체크.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 1707	이분 그래프	-	kokoa-lab
BOJ 11375	열혈강호 (이분 매칭)	-	kokoa-lab
BOJ 2188	축사 배정 (이분 매칭)	-	kokoa-lab
BOJ 9370	미확인 도착지 (이분 체크)	-	kokoa-lab

참고

이 글의 용어 (4개)

깊이 우선 탐색 (DFS)algorithm: 정의 깊이 우선 탐색 (Depth-First Search, DFS) 는 그래프 G=(V, E) 에서 갈 수 있는 만큼 깊이 들어가다가 막히면 백트래킹하는 알고리즘. 스택 (LIF…
너비 우선 탐색 (BFS)algorithm: 정의 너비 우선 탐색 (Breadth-First Search, BFS) 는 그래프 G=(V, E) 에서 시작 정점 s 로부터 가까운 정점부터 순서대로 방문하는 알고리즘. 큐 (F…
이분 매칭 (Bipartite Matching)algorithm: 정의 이분 매칭 (Bipartite Matching) 은 이분 그래프 G = (L ∪ R, E) 에서 간선 부분집합 M ⊆ E 을 선택하되, M 의 어떤 두 간선도 정점을 공유하…
Maximum Flow: Ford-Fulkerson, Edmonds-Karp, Dinicalgorithm: 정의 Maximum Flow (최대 유량) 문제는 방향 그래프 $G = (V, E)$ 와 소스 $s$, 싱크 $t$ 가 주어졌을 때, 각 간선의 용량 제약 아래에서 $s$ 에서 …