이분 그래프란? 이분 그래프는 노드가 두 개의 그룹으로 분리되어 있는 그래프를 말한다. 인접한 정점끼 서로 다른 색으로 색칠하여 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프이다. 철수부터 색을 칠하면 인접한 정점은 철수와 반대되는 색으로 칠한다 철수와 인접한 수학은 주황색으로 칠해진다. 다시 수학과 인접한 영희를 수학과 반대되는 파란색으로 칠하고 영희와 인접한 국어를 주황색으로, 국어와 인접한 세희를 파란색으로..쭉쭉 칠하면 모든 정점을 두 가지의 각기 다른 색으로 칠할 수 있다.이러한 그래프를 이분 그래프라고 부른다. 모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다. 이분 그래프의 판별법 서로 인접한 정점이 같은 색이면 이분 그래프가 아니다!..