그림 13-1은 컷을 나타낸 것입니다. S={0, 1}이라고 한다면 V-S={2, 3, 4}가 되겠군요. 이때 이 컷을 가로지르는 에지를 횡단 에지(crossing edge)라고 하겠습니다.
그림 13-2는 횡단 에지입니다.
▲ 그림 13-2 횡단 에지
횡단 에지란 컷 사이를 횡단하는 에지들이지요. 이 횡단 에지 중 가중치가 가장 작은 에지 e는 반드시 MST의 에지가 됩니다.
컷 프로퍼티(cut property)
: 컷 cut(S, V-S)에서
에지 e = (u, v)의 가중치 weight(u, v)가 가장 작다면
(여기서 u는 S의 원소, v는 V-S의 원소)
에지 e는 E(T)의 원소
(여기서 T는 그래프 G의 MST)