이분 그래프(Bipartite Graph)의 정의

ORCASUIT·2023년 10월 23일

이분 그래프(Bipartite Graph)의 정의

이분 그래프(Bipartite Graph)는 정점(Vertex)의 집합을 두 개의 부분 집합으로 나눌 수 있고, 모든 간선(Edge)이 두 부분 집합에 있는 정점들을 연결하는 그래프를 의미합니다. 즉, 그래프의 모든 간선이 두 부분 집합을 연결하고, 같은 부분 집합 내의 정점끼리는 연결되지 않는 그래프입니다.

특징

같은 그룹 내의 정점끼리는 간선으로 연결되어 있지 않습니다.
두 다른 그룹 간의 모든 간선은 한 정점이 한 그룹, 다른 정점이 다른 그룹에 속하게 됩니다.

판별 방법

이분 그래프 여부를 판별하는 일반적인 방법은 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 사용하는 것입니다. 탐색을 하면서 정점을 두 가지 색으로 칠하게 되는데, 이때 같은 색의 정점끼리 연결된 간선이 있다면 그래프는 이분 그래프가 아닙니다.

예제

정점 집합: {A, B, C, D, E}
간선 집합: {(A, B), (B, C), (C, D), (D, E), (E, A)}

이 그래프는 이분 그래프가 아닙니다. 왜냐하면 예를 들어 A와 B는 같은 색으로 칠해져야 하는데, 이들은 직접적으로 연결되어 있기 때문입니다.

응용

이분 그래프는 여러 알고리즘과 문제, 예를 들어 매칭 문제, 색칠 문제 등에서 활용됩니다.

사용 예

매칭 문제: 이분 매칭 같은 알고리즘에서 주로 사용됩니다.
작업 스케줄링: 자원이 한정되어 있는 경우, 어떤 작업을 어떤 자원으로 처리할지 결정하는 문제에서 사용될 수 있습니다.

C와 Python 비교

C 언어

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool isBipartite(int graph[][3], int V) {
    int color[V];
    for (int i = 0; i < V; ++i) color[i] = -1;
    
    color[0] = 1;
    
    // ... BFS or DFS 로 구현
    // 반환: 이분 그래프면 true, 아니면 false
    return true;
}

int main() {
    int graph[5][5] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        // ...
    };
    printf("%d", isBipartite(graph, 5));
}

Python 언어

from collections import deque

def isBipartite(graph):
    V = len(graph)
    color = [-1] * V
    color[0] = 1
    
    # ... BFS or DFS 로 구현
    # 반환: 이분 그래프면 True, 아니면 False
    
    return True

graph = [
    [0, 1, 0, 1, 0],
    [1, 0, 1, 0, 1],
    # ...
]

print(isBipartite(graph))