그럼 크루스칼 알고리즘과 프림 알고리즘이 모두 기반으로 하는 탐욕 선택 특성인 컷 프로퍼티(cut property)를 알아보겠습니다. 사고를 조금 단순화하고자 한 가지 가정을 하겠습니다. 모든 에지 가중치가 서로 다르다는 가정을 하죠. 이는 우리가 구하는 최소 비용 신장 트리가 유일하다는 의미입니다. 컷(cut)은 그래프의 모든 정점 집합 V(G)를 공집합이 아닌 두 집합으로 나눈 것입니다. 그 한 집합을 S⊆V라고 하면 다른 한 집합은 V-S가 될 것입니다.

그림을 볼까요?

▲ 그림 13-1 컷