최소 절단

그래프 이론에서, 그래프의 최소 절단 또는 최소 절단은 일부 미터법에서 최소인 절단(그래프의 정점을 두 개의 분리 하위 집합으로 나눈 파티션)이다.

최소 절단 문제의 변동은 가중 그래프, 방향 그래프, 단자 및 정점을 세 개 이상의 집합으로 분할하는 것을 고려한다.

양과 음의 가중치를 모두 허용하는 가중 최소 절단 문제는 모든 가중치에서 기호를 뒤집음으로써 가중 최대 절단 문제로 대수롭지 않게 변형될 수 있다.

터미널 노드 없음

비음중량으로 제한된 비방향 가중 그래프에서 최소 절단 문제는 Stoer-Wagner 알고리즘에 의해 다항 시간 내에 해결할 수 있다.그래프의 가중치가 없는 특수한 경우, 카거의 알고리즘은 절단을 찾기 위한 효율적인 무작위화 방법을 제공한다.이 경우 최소 절단은 그래프의 가장자리 연결과 동일하다.

단자 없는 최소 절단 문제의 일반화는 최소 k-컷으로, 가능한 한 적은 에지를 제거하여 그래프를 적어도 k개의 연결된 구성 요소로 분할하는 것을 목표로 한다.k의 고정값의 경우, 이 문제는 다항 시간 내에 해결할 수 있지만, 큰 k에 대해서는 알고리즘이 실용적이지 않다.

터미널 노드 포함

두 개의 터미널 노드가 주어질 때, 그것들은 일반적으로 소스와 싱크대라고 불린다.지시된 가중 유량 네트워크에서, 최소 절단은 선원과 싱크 정점을 분리하고 절삭의 소스 측에서 절단면의 싱크 측으로 향하는 가장자리의 총 중량을 최소화한다.최대 흐름 최소 절삭 정리에 나타난 바와 같이, 이 절삭의 무게는 주어진 네트워크에서 소스에서 싱크대로 보낼 수 있는 최대 흐름 양과 같다.

가중치가 부여된 비방향 네트워크에서는 특정 쌍의 정점을 서로 분리하고 가능한 최소 중량을 갖는 절단을 계산할 수 있다.가능한 모든 꼭지점 쌍에 대해 이 문제를 해결하는 절단 시스템은 그래프의 고모리-후 나무라고 알려진 구조로 수집될 수 있다.

단자에 대한 최소 절단 문제의 일반화는 k-단자 절단 또는 다중 단자 절단이다.$이{\displaystyle }$ 문제는 k${\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle k=3}$의 경우에도 NP-hard이다$.$^[3]

적용들

그래프 파티션 문제는 그래프를 두 개 이상의 부분으로 분할해야 하는 결합 최적화 문제군이며, 컷의 양면 크기 균형 조정과 같은 추가적인 제약조건이 있다.분할 기반 객체 분류는 영상 분할에 적용되는 최소 절삭 스펙트럼 클러스터링 표준화의 특정 사례로 볼 수 있다.

max-flow min-cut 정리 때문에 2개 노드의 최소 컷 값은 최대 flow 값과 동일하다.이 경우 maxflow 문제에 사용되는 일부 알고리즘도 이 문제를 푸는 데 사용할 수 있다.

최소 절단 횟수

정점이$$ $n{\displaystyle }$ ${\displaystyle n}$인 그래프는 최대${\displaystyle }$( ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}$ 2${\displaystyle }$)${\displaystyle }$= n${\displaystyle \frac{}{}}$( ${\displaystyle n\frac{}{}}$- ${\displaystyle \frac{1}{}}$) ${\displaystyle \frac{\mathrm{}}{}}$ ${\$개의$$ 구별되는 최소 절단을 가질 수 있다.$이{\displaystyle }$ 바운드는 n ${\displaystyle n}$ 정점의 (단순) 사이클이 ${\displaystyle \frac{\mathrm{}}{}}$ n${\displaystyle \frac{}{}}$( ${\displaystyle \frac{n}{}}$- ${\displaystyle \frac{1}{}}$) 2 ${\$개의 최소$$ 절단을 가지고 있다는 점에서 타이트하다.

참고 항목

• 최대 컷
• 정점 구분 기호, 가장자리 대신 정점에 대한 최소 절단과 유사한 개념

참조