Twierdzenie Lucchesiego-Youngera

W matematyce grafów skierowanych twierdzenie Lucchesiego -Youngera jest związkiem między dicutami a dijoinami . Został opublikowany przez Cláudio L. Lucchesi i Daniela H. Youngera w 1978 r. Ich dowód rozwiązał przypuszczenie, które zostało postawione mniej więcej dziesięć lat wcześniej przez Youngera oraz w niepublikowanej pracy Neila Robertsona , motywowanej dualnością w grafach planarnych między dijoinami a zestawy łuków sprzężenia zwrotnego .

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 zbiór dicuts jest rozłączny, każdy dicut musi mieć co najmniej jedną krawędź z każdego z dicutów i musi mieć rozmiar co najmniej równy rozmiarowi zbioru. Dlatego maksymalna liczba rozłącznych dicut na dowolnym wykresie musi być mniejsza lub równa minimalnemu rozmiarowi dicut. Twierdzenie Lucchesi-Younger stwierdza, że ​​ta relacja jest zawsze równością. Minimalny rozmiar dijoina jest równy maksymalnej liczbie rozłącznych dicutów, które można znaleźć w danym grafie.