Cięcia (teoria wykres) - Cut (graph theory)

W teorii wykres , A cięcia jest przegroda z wierzchołków grafu na dwie rozłączne podzbiory . Każdy cięty wyznacza wycięcie zestaw , zestaw krawędzi, które mają jeden koniec w każdej podgrupie partycji. Krawędzie te są uważane przekroczyć cięcia. W połączonym wykresie , każdy cut-zestaw określa unikalny krój, aw niektórych przypadkach cięcia są identyfikowane z ich ciętych zestawów raczej niż z ich partycji wierzchołek.

W sieci przepływu An S-T cięcia jest cięty, który wymaga źródła oraz umywalkę znajdować się w różnych podgrup, a jego graniczna ustawić tylko składa się, począwszy od krawędzi po stronie źródłowej na stronie zlewie. Pojemność o S-t cięcia jest definiowana jako suma wydajności każdej z krawędzi w wycięciu zestawu .

Definicja

Cięcia jest partycja z wykresu na dwa podzbiory, S i T . Cięcia ustawiony na cięcie jest zestaw krawędzi, które mają jeden koniec w S , a drugi koniec w T . Jeśli s i t są określone wierzchołków grafu G , wówczas s - t cięcia jest cięcia, w którym y należy do zbioru S i T należy do zbioru T . ${\ Displaystyle C = (S, T)}$ ${\ V} displaystyle$ ${\ Displaystyle G = (V, E)}$ ${\ Displaystyle C = (S, T)}$ ${\ Displaystyle \ {(u, v), \ w e \ mid u \ in S, V \ W t \}}$

W nieważonej nieukierunkowane wykresie wielkość lub ciężar z Cut liczba krawędzi przecinających cięcia. W ważonej wykresie The wartość lub masa jest określona przez sumę mas krawędziach przebiegających cięcia.

Więź jest cut-zestaw, który nie posiada żadnego innego odcięcia ustawiony jako właściwego podzbioru.

minimalne cięcie

Minimalna cięcie.

Redukcja jest minimalna , jeśli wielkość lub ciężar cięcia nie jest większa niż wielkość innego cięcia. Na rysunku po prawej stronie przedstawia minimalną cięcia: rozmiar Takie cięcia 2, i nie ma wykrój wielkości 1, ponieważ wykres jest bezmostkowego .

Max-min Przepływ skrawania twierdzenie wynika, że maksymalny przepływ sieć , a suma wag cięcia krawędzi każdego minimalnego cięcia, który oddziela się od źródła i umywalki są równe. Istnieje wielomianowe czasie sposoby rozwiązania MIN cięcia problem, zwłaszcza z algorytmu Edmonds-Karp .

maksymalne cięcie

Maksymalnie cięcie.

Redukcja jest maksymalna , gdy wielkość cięcia jest nie mniejszy niż rozmiar jakiegokolwiek innego cięcia. Na ilustracji po prawej stronie pokazuje maksymalną cięcia: rozmiar cięcia wynosi 5, a nie cięcia wielkości 6, lub | E | (liczba krawędzi), ponieważ przebieg nie jest dwudzielna (jest to dziwne, cykl ).

Ogólnie rzecz biorąc, znalezienie maksymalne cięcie jest obliczeniowo trudne. Problem max-cut jest jednym z 21 NP-zupełny problemów Karp jest . Problem max-cut jest również APX-twarde , co oznacza, że nie istnieje wielomianowy schemat aproksymacji dla niego chyba P = NP. Jednak może być zbliżona do zasięgu stałym stosunku aproksymacji z wykorzystaniem programowania półokreśloną .

Zauważ, że min-max-cięcia i cięcia są nie podwójne problemy w liniowego programowania sensie, choć dostaje od jednego problemu na inny poprzez zmianę min do max w funkcji celu . Problem max przepływu jest podwójna na min cięte problemu.

Sparsest cięcie

Sparsest problemu cięcie jest bipartition wierzchołki tak, aby zminimalizować współczynnik liczby całej krawędzi cięcia podzielonej przez liczbę wierzchołków w dolnej połowie ścianki działowej. Ta funkcja celu faworyzuje rozwiązania, które są rzadkie (kilka obie krawędzie przecinające Cut) oraz zrównoważony (blisko bisekcji). Problem jest znany jako NP-trudne, a najbardziej znany algorytm aproksymacji jest przybliżenie powodu Arora, Rao & Vazirani (2009) . ${\ Displaystyle O ({\ sqrt {\ log n}})}$

przestrzeń cut

Rodzina wszystkich zestawów ciętego nieukierunkowane wykresie jest znane jako miejsca cięcia wykresu. Tworzy przestrzeń wektorową, w stosunku do dwóch elementów skończonych dziedzinie arytmetyki modulo dwa, z symetrycznym różnicy dwóch zestawów wyciętych jako operacja dodawania wektora i jest prostopadła dopełniacza w przestrzeni cyklu . Jeżeli krawędzie wykresu podano dodatnich wag minimalny ciężar podstawy przestrzeni cięcia może być opisana za pomocą drzewa na sam wierzchołek ustawiona jako wykresu, zwany drzewa Gomory-hu . Każda krawędź tego drzewa jest związany wiązaniem w oryginalnym wykresu, a minimalna nacięcie między dwoma węzłami s i t jest minimalną przyczepność masy między te związane ze ścieżką od S do ţ w drzewie.

Languages

In other projects