이분 그래프(Bipartite Graph)란?

이분 그래프

인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프입니다.

다시 말해서, 그래프의 모든 정점이 두 그룹으로 나눠지고

서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프를 이분 그래프라고 합니다.

 

위 그림을 보면 빨간색, 파란색의 정점이 서로 인접하고 있으며, 같은 색끼리는 인접하지 않습니다.

그리고, 간선이 아예 없고 정점만 있는 경우도 이분 그래프가 됩니다.

 

이분 그래프는 현실에서도 굉장히 많이 사용하게 됩니다.

몇 가지 예시를 들자면,

• 학생 - 수업 : 학생들이 어떤 수업을 듣고 있는 지를 관계로 나타낼 수 있습니다.
• 영화 예약 사이트 회원 - 좋아하는 장르 : 각각의 회원들이 어떤 장르의 영화를 선호하는 지를 나타낼 수 있습니다.
• 구직자 - 가고 싶어하는 회사 : 구직자들이 원하는 회사가 어떤 회사인 지 나타낼 수 있습니다.

 

위 예시의 경우 같이 매칭하는 알고리즘을 이용하여 관계를 나타낼 수 있습니다.

 

이분 그래프 특징

• 연결 성분의 개수를 구하는 방법과 유사합니다.
• 모든 정점을 방문하며, 간선을 검사하기 때문에 시간복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같습니다.
• 또한, 이분 그래프인 지를 확인하는 방법은 BFS, DFS 를 이용하시면 됩니다.
• 이분 그래프는 Tree 나  Even cycle 일 때 성립이 된다. 즉 odd cycle 형태는 이분 그래프가 될 수 없다.

have no odd cycle

have no odd cycle

 

 

이분 그래프인 지 확인하는 방법

1.  BFS 또는 DFS로 탐색을 하면서 정점을 방문할 때마다 두 가지 색중 하나를 칠합니다.
2. 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠합니다.
3. 탐색 진행 중에 자신과 인접한 정점의 색이 자신과 동일하다면? 이분 그래프가 아니게 됩니다.
4. 모든 정점을 다 방문했는데, 인접한 정점의 색이 나와 동일한 정점이 없다면 이분 그래프이다.

여기서 주의할 점은, 연결 그래프와 비연결 그래프를 둘 다 고려해야 합니다.

그래프가 비연결 그래프인 경우엔 모든 정점에 대해서 확인하는 작업이 필요합니다.

 

 

 

코드 설명

이분 그래프인 지 확인하는 백준 문제 [1707] 로 설명을 하겠습니다.

 

 

DFS 방법

import java.io.*;
import java.util.*;

public class Main {
    static int V; // 정점
    static int E; // 간선
    static ArrayList<Integer>[] arrAdj;
    static int[] color;
    static boolean isBipartite = true; // bfs 탐색을 통해 이분 그래프인지 체크

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int K = Integer.parseInt(br.readLine());

        // 테스트 케이스 수행
        while(K-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());

            // 색상 정보 초기화
            color = new int[V + 1];
            // 그래프 인접 리스트
            arrAdj = new ArrayList[V + 1];
            for (int i = 0; i < V + 1; i++) {
                arrAdj[i] = new ArrayList<>();
            }


            // 양방향 간선 정보 세팅
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                arrAdj[x].add(y);
                arrAdj[y].add(x);
            }

            for(int i = 1; i < V + 1; i++){
                if(color[i] != 0) continue; // 이미 방문 완료된 정점이면 넘어간다.
                isBipartite = dfs(i, 1);

                // 중간에 아님이 판명된 경우 반복문을 멈춘다.
                if(!isBipartite) break;
            }

            // 이분 그래프 여부에 따라 출력
            System.out.println(isBipartite ? "YES" : "NO");
        }
    }
    private static boolean dfs(int node, int col){
        color[node] = col;
        int nextCol = col * -1;

        boolean result = true;
        for (int i : arrAdj[node]) {

            // 아직 방문되지 않은 경우
            if (color[i] == 0) 
                result = dfs(i, nextCol);
            else 
                if(color[i] == color[node]) return false;
            

            // false 를 반환 받았다면 바로 되돌아간다.
            if (!result) return false;
        }
        return true;
    }
}

 

---

 

 

BFS 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int V; // 정점
    static int E; // 간선
    static ArrayList<Integer>[] arrAdj;
    static int[] color;
    static boolean isBipartite = true; // bfs 탐색을 통해 이분 그래프인지 체크

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int K = Integer.parseInt(br.readLine());

        // 테스트 케이스 수행
        while(K-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());

            // 색상 정보 초기화
            color = new int[V + 1];
            // 그래프 인접 리스트
            arrAdj = new ArrayList[V + 1];
            for (int i = 0; i < V + 1; i++) {
                arrAdj[i] = new ArrayList<>();
            }


            // 양방향 간선 정보 세팅
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                arrAdj[x].add(y);
                arrAdj[y].add(x);
            }

            for(int i = 1; i < V + 1; i++){
                if(color[i] != 0) continue; // 이미 방문 완료된 정점이면 넘어간다.
                isBipartite = bfs(i);

                // 중간에 아님이 판명된 경우 반복문을 멈춘다.
                if(!isBipartite) break;
            }

            // 이분 그래프 여부에 따라 출력
            System.out.println(isBipartite ? "YES" : "NO");
        }
    }

    private static boolean bfs (int start) {
        // 전달된 번호부터 시작하여 BFS 탐색 수행
        color[start] = 1;

        Queue<Integer> qu = new LinkedList<>();
        qu.offer(start);

        while (!qu.isEmpty()) {
            int node = qu.poll();

            for (int i : arrAdj[node]) {
                // 아직 방문되지 않은 정점이라면 큐에 넣고 현재 색상과 다른 색상으로 저장
                if(color[i] == 0) {
                    qu.offer(i);
                    color[i] = color[node] * -1;

                // 이미 방문된 정점인 경우
                }else {
                    // 현재 정점의 동일한 색상이라면 이분 그래프가 아님
                    if (color[i] == color[node]) {
                        return false; // 이분그래프가 아님
                    }
                }
            }
        }
        return true; // 이분그래프
    }
}