bipartite(이분그래프) 확인하기

어떤 그래프 내에서 인접한 두 정점이 서로 다른 2개의 부류에 소속되어 있을 때 그 그래프를 이분그래프(bipartite)라고 한다. 인접한 두 정점은 같은 부류에 포함되어 있으면 안된다. 아래의 그래프에서 정점들을 빨간색과 초록색 2가지로 분류했을 때, 각 정점은 자신과 인접한 정점과 다른 색을 가지고 있으므로 이분그래프라고 할 수 있다.

아래의 그래프도 이분그래프에 속한다.

어떤 그래프가 이분그래프인지 아닌지 판별하려면, 어떤 정점 v의 부류와 v와 인접한 정점의 부류가 같은지 확인하면 된다. 위 예시의 경우, 정점 v의 색깔과 v와 인접한 정점의 색깔이 같은지 여부를 확인하면 되는 것이다.

어떤 그래프가 이분그래프인지 아닌지 확인하는 함수 bipartite()를 구현하면 아래와 같다.

def bipartite(n, adjacent_list, start, end):
    color = [-1 for _ in range(n)]
    queue = list()
    queue.append(start)
    color[start] = BLACK

    while queue:
        v = queue.pop(0)
        for adj_v in adjacent_list[v]:
            if color[adj_v] == -1:
                color[adj_v] = WHITE if color[v] == BLACK else BLACK
                queue.append(adj_v)
            else:
                if color[adj_v] == color[v]:
                    return 0

    return 1

queue를 확인하는 while문은 정점의 갯수만큼 실행되며, 각 정점에 의해 while문이 1번 실행되었을 때 for문은 그 정점이 가진 간선의 갯수만큼 실행되므로 시간복잡도는 O(|V| + |E|)이다.

이미지 출처

• https://www.geeksforgeeks.org/bipartite-graph/
• 위키백과 - 이분그래프