이분 그래프(bipartite graph), python

이분 그래프란?

 

이분 그래프란 그래프의 정점들을 2개의 집합으로 나누었을 때 각 집합 내의 정점들 간에 서로 연결된 간선이 없도록 분리할 수 있는 그래프를 말한다.

 

 

 

위 그래프에서 집합1 = [1, 3, 5], 집합 2 = [2, 4, 6]으로 분리하게 되면 

집합 1에서 1, 3, 5번 정점들 사이에 연결된 간선이 없고, 집합 2에서도 2, 4, 6 사이에 연결된 간선이 없다.

이렇게 그래프를 2개의 집합으로 분리 할 수 있으면 이분 그래프라고 한다.

 

 

여기서 집합1을 파란색, 집합 2를 빨간색으로 칠하게 되면 한 정점에서 인접한 정점들은 반대색이 됨을 알 수 있다.

 

 

 

 

 

 

 

 

 

그래프가 이분 그래프인지 판별하는 방법

 

인접한 정점들의 색이 반대가 된다는 점을 이용해서 이분 그래프인지 판별할 수 있다.

 

한 정점에서부터 시작해 색을 칠해나간다. 

인접한 정점은 반대색을 칠해준다.

위 과정을 반복해서 모든 정점을 색칠할 수 있다면 해당 그래프는 이분 그래프가 된다.

만약 인접한 정점이 같은 색으로 칠해지게 되면 이분 그래프가 아니게 된다.

 

 

 

 

 

 

이분 그래프인 경우

 

1번 정점을 파란색으로 칠한다.

1번 정점과 연결된 정점은 2번, 4번이고 빨간색으로 칠해준다.

2번에서 연결된 정점은 3번, 4번에서 연결된 정점은 5번이므로 파란색으로 칠해준다.

이러한 방법으로 모든 정점들을 색칠 했으므로 위 그래프는 이분 그래프가 된다.

 

 

 

 

 

 

이분 그래프가 아닌 경우

 

1번을 파란색으로 칠한다.

1번 정점에 인접한 2번 4번을 빨간색으로 칠한다.

4번과 인접한 5번, 2번과 인접한 3번, 6번을 파란색으로 칠한다.

위 그래프는 5번과 6번은 서로 인접해 있지만 같은 색이므로 이분 그래프가 아니다.

 

 

 

 

 

 

 

 

python 구현

 

bfs탐색을 해주면서 색을 번갈아서 칠해주면서 모든 정점을 전부 칠했다면 True, 중간에 인접한 정점이 같은 색이면 False를 반환해 주면 된다.

 

from collections import defaultdict,deque

graph = defaultdict(list)

for _ in range(e):
    u,v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

 

 

그래프 인접 리스트를 생성한다.

 

 

# 색을 칠했다면 그 정점을 방문한것이므로 방문체크도 같이 할 수 있다.
color = {}

for start in graph:
    if start not in color:
        q = deque([start])
        # 처음 색을 칠해준다(색: 0)
        color[start] = 0

        while q:
            cur = q.popleft()

            for next in graph[cur]:
            	# 인접한 정점의 색을 아직 칠하지 않았다면
                if next not in color:
                	# 색을 반대색(0이면 1, 1이면 0)으로 칠해준다.
                    color[next] = 1-color[cur]
                    q.append(next)
                # 인접한 정점의 색이 같다면 이분 그래프가 아니다.
                elif color[next] == color[cur]:
                    return False

# 모든 정점을 전부 칠했다면 이분 그래프이다.                    
return True

 

bfs탐색을 하며 인접한 정점들을 반대색으로 칠해준다.

그래프의 모든 정점을 칠했다면 이분 그래프이고, 탐색 도중 인접한 노드의 색이 같으면 이분 그래프가 아니게 된다.

 

 

 

 

 

 

 

이분 그래프로 해결할 수 있는 문제

 

[백준] 1707 이분 그래프

[백준] 1707 이분 그래프

 

[백준] 11668 파이프 청소, python

[백준] 11668 파이프 청소, python