[Programming] 이분 그래프, Bipartite Graphs

이분 그래프, Bipartite Graphs

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

 

# 이분 그래프, Bipartite Graphs

한국에서는 이분 그래프라고 불리는 Bipartite Graphs에 대해서 알아보도록 하겠다.

Bipartite Graphs의 단어 자체에서도 알 수 있듯이 이분되어 있는 즉 2가지 특성으로 나뉘어 있는 그래프를 의미한다. Bipartite Graphs를 이해함으로써 분류 및 정렬에 대한 알고리즘 활용이 가능하기 때문에 알고리즘의 기본적인 그래프 특징 중에 하나라고 볼 수 있다. Bipartite Graphs에 대해서 정의할 때 어렵게 생각할 필요가 없다. 그래프 자체가 이분, 즉 2가지 특성으로 나뉘어 구분이 되어야 하기 때문에 이를 정의해주면 된다.

Bipartite Graphs에 대해서 설명할때, 두 가지 색상을 각 노드(Node)들에게 칠하고 노드에 연결된 에지(Edge)들은 서로 다른 색깔의 노드와 연결된다고 하면 된다. 이것이 Bipartite Graphs의 간단한 정의 끝이다.

위와 같은 다소 허접해보이는 내용이 definition이 될 수 있는 이유는 실제로 해보면 해당 그래프가 Bipartite Graphs인지 바로 확인이 가능하기 때문이다. 아래 예제를 살펴보자.

 

 

위의 예제 그림을 살펴보면 파란색 노드와 주황색 노드가 있다. 각 노드들은 자기 자신과 다른 색깔의 노드들과 연결되어 있는 것을 확인할 수 있다. 이것이 대표적인 이분 그래프인 셈이다.

 

 

그렇다면 위의 그래프는 이분 그래프인가?라고 했을 때 정답은 No이다. 맨 오른쪽 상단에 주황색 노드가 다른 주황색 노드와 연결되어 있는 것을 알 수 있다. Bipartite Graphs에서는 각 노드가 다른 색깔의 노드와 연결된 상태를 의미하기 때문에 해당 그래프는 Bipartite Graphs, 즉 이분 그래프가 성립되지 않는다.

 

 

해당 그래프 역시 Bipartite Graphs가 성립되지 않는 걸 알 수 있다. 주황색 노드가 다른 주황색 노드와 연결되고 있다는 점에서 Bipartite Graphs에 해당하지 않는 것이다. 

 

 

위의 예제도 역시 Bipartite Graphs가 성립되지 않는다. 여기서 중요한 점은 3개가 만나는 노드에는 어떠한 색을 칠해도 Bipartite Graphs가 성립되지 않는다는 것이다. odd cycle 즉 홀수로 연결되는 cycle 형태는 Bipartite Graphs가 성립될 수가 없다. 왜냐하면 주황색을 칠하든 파란색을 칠하든 또 다른 노드 하나랑은 색이 중복되기 때문에 이분 그래프가 되지 않는 것이다.

 

 

해당 그래프도 역시 cycle 형태의 그래프인 걸 알 수 있다. 다만 even cycle, 즉 짝수로 이루어진 cycle이기 때문에 Bipartite Graphs가 성립하는 걸 확인할 수 있다. 이처럼 Bipartite Graphs는 cycle에서도 성립이 되지만 even cycle일 때만 성립되는 걸 알 수가 있다.

---

 

# In conclusion, 3줄 요약

1. Bipartite Graphs는 두가지 색상을 넣어 비교하는 이분 그래프이다.

2. Bipartite Graphs는 tree나 even cycle일 때 성립된다.

3. Bipartite Graphs를 기반으로 분류 및 정렬 알고리즘을 이해할 수 있다.

---