그래프 분할

그래프 분할(graph partitioning) 문제는 수학에서 그래프를 여러 부분으로 나눌 때, 가능한 한 적게 연결되도록 나누는 문제이다. 이때 각 부분의 크기는 똑같아야 한다. 이 문제에는 다양한 변형이 있는데, 변마다 가중치를 주어서 가중치의 합이 가장 적게 되는 분할을 찾는 경우, 각 부분의 꼭짓점 수가 일정한 범위 안에서 차이나는 경우도 허용하는 경우 등이 있다. 그래프를 두 부분으로 나누는 문제를 특별히 그래프 이등분(graph bisection) 문제라고 한다.

그래프 분할 문제는 조합 최적화 문제 중에서 어려운 문제로, NP-완전에 속한다. 따라서 그래프 분할 문제의 최적해를 직접 구하기는 힘들고, 근사해를 구하기 위한 방법이 여럿 개발되어 있다. 대표적인 방법으로 커니핸-린 알고리즘과 FM 알고리즘이 있다.