Dicut

W matematyce dicut to podział wierzchołków grafu skierowanego na dwa podzbiory, tak że każda krawędź, która ma punkt końcowy w obu podzbiorach, jest skierowana z pierwszego podzbioru do drugiego. Każdy silnie spójny składnik grafu musi być w całości zawarty w jednym z dwóch podzbiorów, więc silnie spójny graf nie ma nietrywialnych dicutów.

Drugi z dwóch podzbiorów w dicut, podzbiór wierzchołków bez krawędzi wychodzących z podzbioru, nazywany jest zamknięciem. Problem zamknięcia to algorytmiczny problem znalezienia dicut w grafie skierowanym ważonym krawędziami, którego całkowita waga jest tak duża, jak to tylko możliwe. Można go rozwiązać w czasie wielomianowym .

W grafach planarnych dicut i cykle są koncepcjami dualnymi. Graf dualny grafu skierowanego, osadzony w płaszczyźnie, to graf z wierzchołkiem dla każdej ściany danego grafu i krawędzią podwójną między dwoma wierzchołkami podwójnymi, gdy odpowiednie dwie ściany są oddzielone krawędzią. Każda podwójna krawędź przecina jedną z oryginalnych krawędzi wykresu, obróconą o 90° zgodnie z ruchem wskazówek zegara. W przypadku dicut na danym wykresie liczby podwójne krawędzi, które przecinają dicut, tworzą ukierunkowany cykl na wykresie dualnym i odwrotnie.

Dijoin można zdefiniować jako zbiór krawędzi, który przecina wszystkie dicuts ; kiedy krawędzie dijoin są skurczone, wynikiem jest silnie spójny graf. Hipoteza Woodalla , nierozwiązany problem w tej dziedzinie, mówi, że w dowolnym grafie skierowanym minimalna liczba krawędzi w dicut (minimalne zamknięcie nieważone) jest równa maksymalnej liczbie rozłącznych połączeń, które można znaleźć w grafie (pakiet dijoinów) . Ułamkowa ważona wersja hipotezy, postawiona przez Jacka Edmondsa i Ricka Gilesa, została obalona przez Alexandra Schrijvera . Z drugiej strony twierdzenie Lucchesiego – Youngera stwierdza, że ​​​​minimalny rozmiar dijoin jest równy maksymalnej liczbie rozłącznych dicutów, które można znaleźć na danym grafie.