[알고리즘] 이분 그래프
이분 그래프란?
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프를 말한다.
즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결된 그래프를 이분 그래프라고 한다. (여기서 중요한 점은 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 해야 한다. 이는 간선이 존재하지 않음을 의미한다.)
이분 그래프의 특징
- 이분 그래프인지 확인하기 위해서 bfs, dfs 같은 그래프 탐색 방법을 이용할 수 있다.
- 특히, bfs를 이용할 경우에는 같은 레벨의 정점끼리는 같은 색으로 칠해진다.
- 연결 요소의 개수를 구하는 방법과 유사하다.
- 모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다.
이분 그래프인지 확인하는 방법
서로 인접한 정점이 같은 색으로 칠해진다면 이분 그래프가 아니다.
- 그래프 탐색(bfs, dfs)를 이용해 정점을 방문할 때마다 두 가지 색 중 다른 색을 칠한다.
- 다음 정점을 방문하면서 자신과 인접한 정점(간선으로 연결된 정점)은 자신과 다른 색으로 칠한다.
- 탐색을 진행할 때, 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다.
- bfs의 경우, 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 이는 이분 그래프가 아니다.
- 모든 정점을 방문했는데, 위의 경우가 없다면 이분 그래프이다.
주의해야 할 점은 연결 그래프와 비연결 그래프 모두 고려해야 한다는 것이다. 그래프가 비연결 그래프인 경우에는 모든 정점에 대해서 확인하는 작업이 필요하다.
이분 그래프와 관련된 문제는 아래 링크를 통해 확인해보자.
1707