이분 그래프?

아래 그래프처럼 A와 B로 나눌 수 있다면 이분그래프 입니다.

• A에 포함되어 있는 정점끼리 연결된 간선 X
• B에 포함되어 있는 정점끼리 연결된 간선 X

즉, A와 B만 연결된 간선이 있어야 한다는 뜻입니다. ⇒ A(1,2,5) B(4,3,6)

그럼 어떤 그래프가 이분 그래프인지 어떻게 판단?

DFS또는 BFS로 판단할 수 있습니다.

예를 들어,

• 한 정점 1에서 시작합니다.
  • 1은 A라고 합시다.
• 1에서 4로 갑니다.
  • 4는 B라고 합시다.

이렇게 계속 반복하면 A와 B를 왔다갔다하는 것을 알 수 있죠.

만약 여기서 5에서 2을 갈 수 있다면?

2는 이미 방문한 상태, 즉, 2는 A또는 B여야 하고 5가 A이므로 2는 B여야하는데 A이므로 이분그래프가 아니라는 것을 알 수 있습니다.