이분 그래프 (bipartite graph)

 

  그래프의 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 이분 그래프(bipartite graph)라고 한다. 즉, 정점을 어떠한 방법으로든 두 개의 집합으로 나눴을 때 각 집합의 정점끼리 간선이 존재하지 않게 나눌 수만 있다면 이분 그래프이다.

 

  예를들어 위 이미지에서 1,2,3은 이분 그래프이고 4는 이분 그래프가 아니다(4번의 경우 동일한 집합끼리 간선이 연결되어 있다. 이와 같이 홀수 길이의 사이클이 있다면 이분 그래프가 될 수 없다.). 또 3과 같이 서로 연결된 부분이 없더라도 어쨌든 이분 그래프의 정의를 위반시키지 않으므로 이분 그래프이다.

 

  이분 그래프 판별방법은 다음과 같다.

1. 모든 정점에 대해 각 정점에서 dfs 혹은 bfs를 진행하면서 2개 종류의 집합을 번갈아가며 설정한다. (뭐 true, false로 하던지 -1,1로 하던지 상관없다. 체크만 가능하면 된다.)

2. 이 때 dfs 혹은 bfs를 진행하다가 인접한(간선이 연결된) 정점이 자신과 동일한 종류의 집합이라면 이분 그래프가 아니다. 모두 통과되었다면 이분 그래프이다.

 

  이분 그래프 판별 예시 - boj1707 문제에 대해 이분 그래프 판별을 하는 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (k-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            ArrayList<Integer>[] edges = new ArrayList[v+1];
            for (int i = 1; i <= v; i++) edges[i] = new ArrayList<>();
            boolean[] chk = new boolean[v+1];
            while(e-->0) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                chk[a] = chk[b] = true;
                edges[a].add(b);
                edges[b].add(a);
            }
            Boolean[] arr = new Boolean[v+1];
            boolean answer = true;
            for (int i = 1; i <= v && answer; i++) {
                if (arr[i]!=null || !chk[i]) continue;
                Stack<Integer> stk = new Stack<>();
                stk.add(i);
                arr[i] = true;
                while(!stk.isEmpty() && answer) {
                    int cur = stk.pop();
                    for (int j = 0; j < edges[cur].size(); j++) {
                        int next = edges[cur].get(j);
                        if (arr[next] == null) {
                            arr[next] = !arr[cur];
                            stk.add(next);
                        } else if (arr[next] == arr[cur]) {
                            answer = false;
                            break;
                        }
                    }
                }
            }
            sb.append(answer?"YES\n":"NO\n");
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

References

1. https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

2. https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

이분 그래프 - 위키백과, 우리 모두의 백과사전