이분 그래프 판별하는 알고리즘 분석

1. 문제 그래프의 정점의 집합을 둘로 분할하는데 각 집합에 속하는 정점끼리는 서로 간선이 존재하지 않도록 분할하고 싶다. 이것이 가능한지를 판별하는 프로그램을 작성해본다면? 2. DFS 알고리즘 무방향 그래프라고 가정함 어떤 정점을 방문하면서 방문한 정점에 그룹 1을 할당 인접한 정점을 순회하면서, 인접한 정점이 방문하지 않은 정점이면 그룹 -1을 할당하고 방문 하지만 인접한 정점이 이미 방문한 정점이라면, 현재 정점의 그룹(현재 그룹이 할당됨)과 이미 방문한 정점(이미 그룹이 할당됨)이 서로 같은 그룹이면 이분 그래프가 아니다 3. 예를 들어서 생각해보기 다음과 같은 그래프가 이분 그래프인지 생각해보자 임의의 정점 아무거나 하나를 선택하고 방문을 시도 방문하면서 파란색을 부여한다 현재 방문한 정점과 ..