Przypuszczenie Woodalla

Nierozwiązany problem z matematyki :

Czy minimalna liczba krawędzi w dicut grafu skierowanego jest zawsze równa maksymalnej liczbie rozłącznych połączeń?

(więcej nierozwiązanych problemów z matematyki)

W matematyce grafów skierowanych hipoteza Woodalla jest nieudowodnionym związkiem między dicutami a dijoinami . Postawił je Douglas Woodall w 1976 roku.

Oświadczenie

Dicut to podział wierzchołków na dwa podzbiory w taki sposób, że wszystkie krawędzie przecinające ten podział robią to w tym samym kierunku. Dijoin to podzbiór krawędzi, który po skróceniu tworzy silnie spójny graf ; równoważnie jest to podzbiór krawędzi, który zawiera co najmniej jedną krawędź z każdego dicut.

Jeśli minimalna liczba krawędzi w dicut $nich$ na wykresie mogą znajdować się co najwyżej $musi zawierać inną krawędź od najmniejszego dicut. Przypuszczenie Woodalla stwierdza$$, że ​​w$ przypadku zawsze można znaleźć rozłączne połączenia. Oznacza to, że w każdym grafie skierowanym minimalna liczba krawędzi w dicut jest równa maksymalnej liczbie rozłącznych połączeń, które można znaleźć w grafie (pakiet dijoins).

Wyniki częściowe

Jest to wniosek folklorystyczny, że twierdzenie jest prawdziwe dla grafów skierowanych, których minimalny dicut ma dwie krawędzie. Dowolny przypadek problemu można zredukować do skierowanego grafu acyklicznego , biorąc kondensację instancji, wykres utworzony przez skurczenie każdego silnie połączonego komponentu do pojedynczego wierzchołka. Inną klasą grafów, dla których twierdzenie to zostało udowodnione, są skierowane grafy acykliczne, w których każdy wierzchołek źródłowy (wierzchołek bez krawędzi wejściowych) ma ścieżkę do każdego wierzchołka ujścia (wierzchołek bez krawędzi wychodzących).

Powiązane wyniki

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.

Linki zewnętrzne

• Feofiloff, Paulo (30 listopada 2005), przypuszczenie Woodalla na temat Packing Dijoins: ankieta (PDF)
• „Przypuszczenie Woodalla” , Open Problem Garden , 5 kwietnia 2007 r