이분 그래프 Bipartite Graph
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
이분 그래프는 그래프의 모든 정점을 서로 겹치지 않는 두 개의 집합 A와 B로 분할했을 때,
그래프의 모든 간선이 반드시 집합 A의 정점과 집합 B의 정점을 연결하도록 분할할 수 있는 그래프를 말한다.
쉽게 말해, 정점을 두 그룹으로 나눌 수 있고 같은 그룹의 정점끼리는 간선이 존재하지 않는 그래프이다.
특징
그래프 G가 이분 그래프인 것과 G에 홀수 길이의 사이클이 존재하지 않는 것은 동치이다.
1. G가 이분 그래프라면 G의 모든 사이클의 길이는 짝수이다.
G가 이분 그래프이므로, 모든 정점을 집합 A와 집합 B라는 두 그룹으로 나눌 수 있다.
이분 그래프의 규칙에 따라, 모든 간선은 반드시 집합 A의 정점과 집합 B의 정점을 연결한다.
만약 사이클이 집합 A의 정점에서 시작했다면 첫 번째 간선은 반드시 집합 B의 정점으로 연결되고, 두 번째 간선은 다시 집합 A의 정점으로 연결된다.
홀수 번째 간선을 따라 도착한 정점은 출발 정점과 다른 집합에 속하게 되고, 짝수 번째 간선을 따라 도착한 정점은 출발 정점과 같은 집합에 속하게 된다.
따라서 이분 그래프에서는 짝수 길이의 사이클만 존재할 수 있다.
2. G의 모든 사이클의 길이가 짝수라면 G는 이분 그래프이다.
그래프 G가 연결되었다고 가정하고 그래프의 임의의 정점 s를 선택한다.
정점 s를 기준으로, 다른 모든 정점들을 s까지의 최단 경로의 길이을 이용해 두 집합으로 나눈다.
- 집합 A: s로부터의 최단 경로 길이가 짝수인 모든 정점들
- 집합 B: s로부터의 최단 경로 길이가 홀수인 모든 정점들
이제 집합 A와 B가 이분 그래프의 조건을 만족하는지, 즉, 같은 집합에 속한 두 정점 사이에 변이 없는지를 확인한다.
- 만약 집합 A에 속한 두 정점 u와 v가 간선으로 연결되어 있다면?
- u와 v는 모두 s로부터의 최단 경로 길이가 짝수이다.
- s -> … -> u (짝수 길이)
- s -> … -> v (짝수 길이)
- u -> v (길이 1)
- s -> u -> v -> s를 이으면 사이클이 만들어진다.
- 이 사이클의 길이는 짝수 + 1 + 짝수 = 홀수이다.
- 만약 집합 B에 속한 두 정점 u와 v가 간선으로 연결되어 있다면?
- u와 v는 모두 s로부터의 최단 경로 길이가 홀수이다.
- 마찬가지로 홀수 + 1 + 홀수 = 홀수 길이의 사이클이 만들어진다.
전제는 G에 홀수 길이의 사이클이 없다는 것이었다.
같은 집합에 속한 정점들은 변으로 연결될 수 없고, 모든 변은 반드시 집합 A의 정점과 집합 B의 정점을 연결해야 한다.
G는 이분 그래프가 된다.
이분 그래프 판별하기
이분 그래프는 DFS 또는 BFS를 사용하여 판별할 수 있다.
- 처음에 탐색을 시작할 정점 s의 색상을 빨간색으로 칠한다.
- s와 인접한 정점들의 색상을 파란색으로 칠한다.
- 파란색으로 칠해진 정점들과 인접한 정점들의 색상을 빨간색으로 칠한다.
- 이 과정을 반복하여 모든 정점을 탐색한다.
- 만약 이미 색칠된 정점과 같은 색깔로 칠해야 하는 상황이 발생하면, 그래프는 이분 그래프가 아니다.