이분 그래프 (Bipartite graph)

이분 그래프 (Bipartite graph)

1. 그래프란?

정점(vertice, node)과 간선(edge)으로 이루어진 자료구조를 그래프이라 한다. 트리도 그래프의 한 종류에 해당하지만, 그래프는 보다 더 유연한 방식으로 데이터 간의 관계를 표현할 수 있다.

 

2. 이분 그래프(Bipartite graph)란?

이분 그래프는 인접한 정점에 다른 색을 칠할 때, 모든 정점에 대해 2가지 색만으로 칠할 수 있는 그래프이다.

 

3. 이분 그래프 탐색 방법

1단계. 그래프를 DFS나 BFS로 탐색한다.
2단계. 색을 이웃과 다른 색으로 설정한다.
3단계. 자신과 인접한 정점의 색이 같을 경우, 이분 그래프가 될 수 없다.

 

 

---

- 24.03.18 LAB meeting -

랩 미팅 중 생소했던 개념을 정리한 글입니다.