이분 그래프 판별법 - ibun geulaepeu panbyeolbeob

이분 그래프 : 모든 정점을 두 가지 색으로 칠하되, 모든 간선이 두 가지 색의 정점을 포함하도록 색칠할 수 있는 그래프

이분 그래프 판별:

1. 그래프를 BFS or DFS로 탐색하며, 색을 이웃과 다른 색으로 계속 칠한다.

2. 자신과 인접한 정점의 색이 자신과 같으면 이분 그래프가 아니다.

-연결 그래프일 경우, 정점 하나를 시작으로 탐색을 한 번만 마친 후, 판별할 수 있지만

비연결 그래프일 경우, 모든 정점을 탐색해 판별해야한다.

저작자표시

'컴퓨터 사이언스 > 자료구조와 알고리즘' 카테고리의 다른 글