이분그래프는 정점을 빨간색과 파란색이 칠해진 2그룹으로 나눌 수 있으면서 각 그룹의 정점끼리는 간선으로 이루어지지 않은 경우를 의미한다. 즉, 모든 간선은 빨간색과 파란색 정점을 가지는 그래프이다.
이분 그래프 판별 방법
1) DFS/BFS를 이용하여 그래프 내 모든 정점을 2종류(RED/BLUE)의 집합으로 설정한다.
2) 이 때 DFS/BFS를 진행하다가 인접한 정점이 자신과 동일한 종류의 집합이면 이분 그래프가 아니다. 모두 서로다른 종류의 집합이라면 이분 그래프이다.
cf. 연결 그래프와 비연결 그래프 모두 고려해야한다.
java