Problem z chińskim listonoszem

W teorii grafów , gałęzi matematyki i informatyki , problem trasy Guana , problem chińskiego listonosza , problem trasy listonosza lub problem kontroli trasy polega na znalezieniu najkrótszej zamkniętej ścieżki lub obwodu, który odwiedza każdą krawędź (połączonego) nieskierowanego wykresu . Gdy wykres ma obwód Eulera (zamknięty spacer, który obejmuje raz każdą krawędź), obwód ten jest rozwiązaniem optymalnym. W przeciwnym razie problem optymalizacji polega na znalezieniu najmniejszej liczby krawędzi grafu do zduplikowania (lub podzbioru krawędzi o minimalnej możliwej wadze całkowitej), tak aby wynikowy multigraf miał obwód Eulera. Można go rozwiązać w czasie wielomianowym .

Problem ten był pierwotnie badany przez chińskiego matematyka Kwana Mei-Ko w 1960 r., którego chiński artykuł został przetłumaczony na język angielski w 1962 r. Oryginalna nazwa „problem chińskiego listonosza” została ukuta na jego cześć; różne źródła przypisują monetę Alanowi J. Goldmanowi lub Jackowi Edmondsowi , obaj byli wówczas w US National Bureau of Standards .

Uogólnienie polega na wybraniu dowolnego zbioru T o jednakowo wielu wierzchołkach, które mają być połączone zbiorem krawędzi w grafie, którego wierzchołki nieparzystego stopnia są dokładnie wierzchołkami T . Taki zestaw nazywamy T -join. Ten problem, problem łączenia T , można również rozwiązać w czasie wielomianowym, stosując to samo podejście, które rozwiązuje problem listonosza.

Rozwiązanie nieskierowane i T -złączenia

Problem inspekcji trasy nieukierunkowanej można rozwiązać w czasie wielomianowym za pomocą algorytmu opartego na koncepcji połączenia T. Niech T będzie zbiorem wierzchołków grafu. Zbiór krawędzi J nazywamy T -join , jeśli zbiór wierzchołków, które mają nieparzystą liczbę incydentnych krawędzi w J , jest dokładnie zbiorem T. Połączenie typu T istnieje zawsze, gdy każdy spójny element grafu zawiera parzystą liczbę wierzchołków w T . Problem połączenia T polega na znalezieniu połączenia T z minimalną możliwą liczbą krawędzi lub minimalną możliwą całkowitą wagą.

Dla dowolnego T najmniejsze połączenie T (jeśli istnieje) koniecznie składa się z ${\ displaystyle {\ tfrac {1} {2}} | T |}$ ścieżki, które łączą wierzchołki T parami. Ścieżki będą takie, aby całkowita długość lub łączna waga wszystkich z nich była jak najmniejsza. W optymalnym rozwiązaniu żadne dwie z tych ścieżek nie będą miały wspólnej krawędzi, ale mogą mieć wspólne wierzchołki. Minimalne T można uzyskać, konstruując pełny graf na wierzchołkach T , z krawędziami reprezentującymi najkrótsze ścieżki w danym grafie wejściowym, a następnie znajdując idealne dopasowanie minimalnej wagi w tym pełnym grafie. Krawędzie tego dopasowania reprezentują ścieżki w oryginalnym grafie, których suma tworzy pożądane łączenie typu T. Zarówno skonstruowanie pełnego wykresu, jak i znalezienie w nim dopasowania można wykonać w krokach obliczeniowych O( n ³ ).

W przypadku problemu inspekcji trasy T należy wybrać jako zbiór wszystkich wierzchołków nieparzystych stopni. Z założeń problemu wynika, że cały graf jest spójny (w przeciwnym razie żadna trasa nie istnieje), a zgodnie z lematem o uzgadnianiu ma on parzystą liczbę nieparzystych wierzchołków, więc zawsze istnieje połączenie typu T. Podwojenie krawędzi T -join powoduje, że dany graf staje się multigrafem Eulera (graf spójny, w którym każdy wierzchołek ma parzysty stopień), z którego wynika, że ma trasę Eulera , trasę, która odwiedza każdą krawędź multigrafu dokładnie raz. Ta trasa będzie optymalnym rozwiązaniem problemu inspekcji tras.

Rozwiązanie ukierunkowane

Na grafie skierowanym obowiązują te same ogólne idee, ale należy zastosować różne techniki. Jeśli skierowany graf jest eulerowski, wystarczy znaleźć cykl Eulera. Jeśli tak nie jest, należy znaleźć T , co w tym przypadku pociąga za sobą znalezienie ścieżek od wierzchołków o stopniu większym od ich stopnia zewnętrznego do wierzchołków o stopniu zewnętrznym większym od ich stopnia zewnętrznego , tak aby tworzyły stopień wejściowy każdego wierzchołka równy jego stopniowi zewnętrznemu. Można to rozwiązać jako przykład problemu przepływu przy minimalnych kosztach, w którym istnieje jedna jednostka podaży na każdą jednostkę nadwyżki stopnia wejściowego i jedna jednostka zapotrzebowania na każdą jednostkę nadwyżki stopnia wyjściowego. Jako taka jest rozwiązywalna w czasie O(| V | ² | E |). Rozwiązanie istnieje wtedy i tylko wtedy, gdy dany graf jest silnie spójny .

Aplikacje

Różne problemy kombinatoryczne zostały zredukowane do problemu chińskiego listonosza, w tym znalezienie maksymalnego cięcia w grafie planarnym i obwodu o minimalnej średniej długości w grafie nieskierowanym.

Warianty

Zbadano kilka wariantów problemu chińskiego listonosza i wykazano, że są one NP-zupełne .

Problem wietrznego listonosza jest wariantem problemu inspekcji trasy, w którym dane wejściowe są grafem nieskierowanym, ale gdzie każda krawędź może mieć inny koszt przejścia w jednym kierunku niż przejścia w drugim kierunku. W przeciwieństwie do rozwiązań dla grafów skierowanych i nieskierowanych jest NP-zupełny .
Problem mieszanego chińskiego listonosza : w przypadku tego problemu niektóre krawędzie mogą być skierowane i dlatego można je odwiedzać tylko z jednego kierunku. Kiedy problem wymaga minimalnego przejścia digrafu (lub multidigrafu), jest znany jako „problem New York Street Sweeper”.
Problem k -chińskiego listonosza: znajdź k cykli, z których wszystkie zaczynają się w wyznaczonym miejscu, tak aby każda krawędź przechodziła przez co najmniej jeden cykl. Celem jest minimalizacja kosztów najdroższego cyklu.
„Problem wiejskiego listonosza”: rozwiąż problem z niepotrzebnymi krawędziami.

Zobacz też

Linki zewnętrzne

Weisstein, Eric W. , „Problem chińskiego listonosza” , MathWorld
Media związane z problemem inspekcji tras w Wikimedia Commons