그래프 이론의 이중 분할 이해

그래프 이론에서 그래프의 이중 분할은 모든 모서리가 서로 다른 분할 집합의 정점을 연결하도록 정점 집합을 두 개의 분리된 집합(부분 집합이라고 함)으로 나누는 것입니다. 즉, 동일한 분할 집합의 정점 사이에는 가장자리가 없습니다.

예를 들어 4개의 정점 {a,b,c,d}가 있는 그래프를 고려하고 정점 집합을 {a,b}와 {CD}. 모든 모서리가 서로 다른 부분의 정점을 연결하기 때문에 그래프는 이분 분할됩니다. 그래프 순회, 최단 경로 찾기 및 그래프 일치와 같은 그래프 문제에 대한 알고리즘의 복잡성을 줄이는 데 이중 분할을 사용할 수 있습니다.