32. bipartite graph detection [12 1주차]

32. Bipartite Graph Detection [12-1주차]

2024년 1월 14일 일요일

오후 4:49

<Bipartite Graph Detection>

노드들을 두 집합으로 나눈다.

이때, 노드가 한 집합 내부에서는 간선으로 직접 연결되지 않고, 서로 다른 집합에 있는 노드끼리만 연결되도록 해야 한다. 이런 규칙을 만족하도록 노드들을 두 집합으로 나눌 수 있는 그래프를 Bipartite Graph라고 한다.

간선이 하나도 없는 경우도 Bipartite라 한다.

<DFS를 이용한 Bipartite Graph Detection 풀이>

먼저 DFS트리를 구한다.

그래프가 Bipartite 라고 가정하고, 노드 집합 A와 B로 Bipartite 규칙을 만족하도록 나누어진다고 하자. 루트 노드가 A에 속한다고 하면, 루트 노드는 모든 아래 층의 노드와 연결되어 있으므로, 아래 층의 노드는 모두 B에 속해야 한다. 마찬가지 이유로 깊이 2의 노드들은 모두 A에 속해야 하고, 깊이 3의 노드들은 모두 B에 속해야 한다. 이렇게 층마다 A에 속하는 노드, B에 속하는 노드가 번갈아 나타난다.

다음으로 back edge들을 조사하여, back edge중 A의 노드끼리 연결하거나 B의 노드끼리 연결하는 것이 하나라도 있는지 확인한다. 그런 back edge가 하나도 없어야만 Bipartite 그래프이다.