Minimalne cięcie

Wykres i dwa jego przekroje. Linia przerywana w kolorze czerwonym przedstawia cięcie z trzema przecinającymi się krawędziami. Linia przerywana w kolorze zielonym reprezentuje jedno z minimalnych cięć tego wykresu, przecinające tylko dwie krawędzie.

W teorii grafów minimalne cięcie lub minimalne cięcie wykresu to cięcie ( podział wierzchołków wykresu na dwa rozłączne podzbiory), które jest minimalne w niektórych metrykach .

Odmiany problemu minimalnego cięcia uwzględniają grafy ważone, grafy skierowane, terminale i podział wierzchołków na więcej niż dwa zbiory.

Ważony problem minimalnego cięcia, uwzględniający zarówno wagi dodatnie, jak i ujemne, można w prosty sposób przekształcić w ważony problem maksymalnego cięcia , odwracając znak we wszystkich wagach.

Bez węzłów końcowych

Problem minimalnego cięcia w nieskierowanych , ważonych grafach ograniczonych do nieujemnych wag można rozwiązać w czasie wielomianowym za pomocą algorytmu Stoera-Wagnera . W szczególnym przypadku, gdy wykres jest nieważony, algorytm Kargera zapewnia skuteczną losową metodę znajdowania cięcia. W tym przypadku minimalne cięcie jest równe łączności krawędzi grafu.

Uogólnieniem problemu minimalnego cięcia bez końcówek jest minimalne k -cut , w którym celem jest podzielenie grafu na co najmniej k połączonych elementów przez usunięcie jak najmniejszej liczby krawędzi. Dla ustalonej wartości k problem ten można rozwiązać w czasie wielomianowym, chociaż algorytm nie jest praktyczny dla dużych k .

Z węzłami końcowymi

Kiedy podane są dwa węzły końcowe, są one zwykle określane jako źródło i ujście . W sieci przepływowej minimalne przecięcie oddziela wierzchołki źródła i ujścia i minimalizuje całkowitą sumę przepustowości krawędzi, które są skierowane od strony źródła wycięcia do strony ujścia wycięcia. Jak pokazano w twierdzeniu o maksymalnym przepływie i minimalnym odcięciu , waga tego odcięcia jest równa maksymalnej wielkości przepływu, który może zostać przesłany ze źródła do ujścia w danej sieci.

W ważonej, nieskierowanej sieci możliwe jest obliczenie przecięcia, które oddziela od siebie określoną parę wierzchołków i ma minimalną możliwą wagę. System cięć, który rozwiązuje ten problem dla każdej możliwej pary wierzchołków, można zebrać w strukturę znaną jako grafu Gomory-Hu .

Uogólnieniem problemu minimalnego cięcia z końcówkami jest cięcie k -końcowe lub cięcie wielozaciskowe. Ten problem jest NP-trudny , nawet dla ${\ displaystyle k = 3}$ .

Aplikacje

podziału grafów to rodzina kombinatorycznych problemów optymalizacji, w których graf ma być podzielony na dwie lub więcej części z dodatkowymi ograniczeniami, takimi jak zrównoważenie rozmiarów dwóch stron cięcia. Kategoryzację obiektów opartą na segmentacji można postrzegać jako szczególny przypadek znormalizowanego grupowania widmowego z minimalnym cięciem zastosowanego do segmentacji obrazu . Może być również używana jako ogólna grupowania , w której węzły są próbkami danych, które zakłada się, że zostały pobrane z przestrzeni metrycznej a wagi krawędzi to ich odległości. Jest to jednak często niepraktyczne ze względu na dużą złożoność obliczeniową . ${\ displaystyle k> 2}$ .

Ze względu na twierdzenie o maksymalnym przepływie i minimalnym odcięciu, minimalna wartość odcięcia 2 węzłów jest równa ich wartości maksymalnego przepływu . W takim przypadku niektóre algorytmy użyte w problemie maxflow mogą być również użyte do rozwiązania tego pytania.

Liczba minimalnych cięć

Wykres z $wierzchołkami$ może co najwyżej mieć ${\ Displaystyle {\ binom {n} {2}} = {\ Frac {n (n-1$ wyraźne minimalne cięcia. Ta granica ${\ Displaystyle {\ Frac {n (n-1)}} {2}}}$ ścisła w tym sensie, że (prosty) cykl $na$ wierzchołkach ma dokładnie minimum cięcia.

Zobacz też

• Maksymalne cięcie
• Separator wierzchołków , koncepcja analogiczna do minimalnych cięć dla wierzchołków zamiast krawędzi