W roku 1962 chiński matematyk Mei-Ko Kwan zaproponował następujący problem:

Listonosz, roznosząc listy, musi przejść przez wszystkie ulice w swojej dzielnicy co najmniej jeden raz i wrócić na pocztę. Ponieważ jest człowiekiem leniwym (nie odnosi się to do pozostałych listonoszy, tylko do tego konkretnego), chciałby mieć jak najkrótszą do przejścia trasę. Znalezienie takiej trasy jest problemem, który nazwano problemem chińskiego listonosza (ang. Chinese postman problem-CPP).

W języku grafów układ ulic to graf nieskierowany (problem z grafem skierowanym może wystąpić wtedy, gdy listonosz jeździ furgonetką pocztową, a część ulic jest jednokierunkowa) z wagami – każda ulica to krawędź, której waga jest równa długości ulicy. Skrzyżowania ulic to wierzchołki grafu. Poczta jest wierzchołkiem startowym i końcowym. Naszym zadaniem jest znalezienie cyklu wychodzącego z poczty i wracającego do niej po przejściu przez wszystkie krawędzie grafu co najmniej jeden raz i o takiej własności, iż suma wag krawędzi cyklu jest najmniejszą możliwą sumą wag krawędzi wszystkich takich cykli w grafie.

Jeśli graf zawiera cykl Eulera, to rozwiązanie jest bardzo proste-cykl Eulera przechodzi przez każdą krawędź grafu dokładnie jeden raz, zatem suma wag jego krawędzi jest zawsze minimalna.

Jeśli graf nie zawiera cyklu Eulera (trudno żądać, aby architekci budowali ulice zgodnie z regułami grafów Eulera), to zadanie się komplikuje. Załóżmy, iż w grafie są tylko dwa wierzchołki o nieparzystym stopniu (wierzchołki F i K).

Aby graf zawierał cykle Eulera, wszystkie wierzchołki muszą posiadać stopnie parzyste. W celu osiągnięcia tego stanu w grafie dublujemy krawędzie wchodzące w skład ścieżki łączącej wierzchołki o nieparzystych stopniach F i K (np. ścieżka F – G – L – J – K):

→

Po tej operacji stopnie wszystkich wierzchołków grafu są parzyste. Stało się tak dlatego, ponieważ do wierzchołków F i K o nieparzystych stopniach dodaliśmy po jednej krawędzi, co spowodowało przejście stopni nieparzystych w parzyste. Do pozostałych wierzchołków ścieżki dodaliśmy po dwie krawędzie (wchodzącą i wychodzącą), a to nie zmieniło parzystości ich stopni. Graf, w którym krawędzie mogą być dublowane, nazywamy multigrafem.

Teraz multigraf spełnia warunki istnienia cyklu Eulera. W odniesieniu do pierwotnego grafu cykl Eulera przebiegnie przez zdublowane krawędzie dwukrotnie (tymi ulicami nasz listonosz będzie musiał przejść dwa razy). Cykl znajdziemy za pomocą algorytmu znajdowania cyklu Eulera w spójnym grafie nieskierowanym. Algorytm ten jest już przystosowany do multigrafów. Przygotujmy dane wejściowe. Zastąpimy etykiety literowe (bardziej czytelne dla ludzi) etykietami liczbowymi (mniej czytelne dla ludzi, ale lepsze dla komputera):

12 27 0 1 0 2 0 3 0 4 1 2 1 5 1 6 2 3 2 5 3 4 3 7 4 9 4 10 5 6 5 6 6 7 6 11 6 11 7 8 7 11 8 9 8 10 8 11 9 10 9 10 9 11 9 11

Po uruchomieniu programu i wprowadzeniu do niego przygotowanych danych, otrzymujemy wynik następujący (numerki obok krawędzi określają kolejność ich przechodzenia w wyznaczonym cyklu Eulera):

12 27 0 1 0 2 0 3 0 4 1 2 1 5 1 6 2 3 2 5 3 4 3 7 4 9 4 10 5 6 5 6 6 7 6 11 6 11 7 8 7 11 8 9 8 10 8 11 9 10 9 10 9 11 9 11 EULERIAN CYCLE : 0 4 10 9 11 9 10 8 11 6 11 7 8 9 4 3 7 6 5 6 1 5 2 3 0 2 1 0

Suma wag krawędzi wchodzących do cyklu Eulera w zmodyfikowanym grafie jest równa sumie wag wszystkich krawędzi pierwotnego grafu powiększonej o sumę wag krawędzi zdublowanych. Oczywistym jest, iż ścieżkę łączącą wierzchołki o nieparzystych stopniach należy dobrać, tak aby suma wag jej krawędzi była najmniejsza ze wszystkich możliwych ścieżek w grafie, które łączą te wierzchołki. Ścieżkę taką możemy bez problemu znaleźć przy pomocy algorytmu Dijkstry.

Jeśli graf zawiera więcej niż dwa wierzchołki o nieparzystych stopniach, problem staje się trudny obliczeniowo. W takim przypadku za pomocą algorytmu Dijkstry musimy wyznaczyć najkrótsze ścieżki pomiędzy wszystkimi tymi wierzchołkami. Istnieje twierdzenie, które mówi, iż liczba wierzchołków o nieparzystych stopniach w grafie spójnym jest zawsze liczbą parzystą. Skoro tak, to wierzchołki możemy połączyć w pary za pomocą znalezionych ścieżek. Problem leży w tym, aby suma wag użytych do połączeń ścieżek była jak najmniejsza. Powód jest prosty – ścieżki te będą dublowane w grafie, aby uzyskać parzyste stopnie wierzchołków. Suma wag ich krawędzi doda się do sumy wag wszystkich krawędzi w grafie. Skoro szukamy najkrótszej trasy, to dublowane ścieżki powinny być najkrótsze z możliwych.

Rozważmy problem kombinatorycznie.

Dwa wierzchołki można połączyć tylko na jeden sposób:

A – B

Cztery wierzchołki mogą już być połączone na 3 różne sposoby:

Do wyniku tego dochodzimy następująco: pierwszy wierzchołek A może być skojarzony z dowolnym z trzech pozostałych B, C i D. Mamy zatem 3 możliwości:

A – B, A – C i A – D.

Po wybraniu pierwszej pary, pozostałe dwa wierzchołki można połączyć tylko na jeden sposób, zatem w sumie dostajemy trzy kombinacje par:

{A – B, C – D} {A – C, B – D} {A – D, B –  C}

Sześć wierzchołków (pięć nie może wystąpić, gdyż liczba wierzchołków o nieparzystych stopniach jest zawsze parzysta) można połączyć na 15 różnych sposobów:

Do wyniku tego dochodzimy następująco: pierwszy wierzchołek A można skojarzyć z dowolnym z pięciu pozostałych wierzchołków B, C, D, E lub F. Otrzymujemy pięć możliwości utworzenia pierwszej pary:

A – B, A – C, A – D, A – E i A – F.

Po wyborze pierwszej pary pozostają zawsze 4 nieskojarzone wierzchołki, a te można skojarzyć w pary na trzy różne sposoby. Zatem dla każdej z pierwszych par mamy trzy kombinacje pozostałych dwóch par. W wyniku otrzymujemy 5 × 3 = 15 różnych skojarzeń.

Kontynuując to rozumowanie dalej, wyliczamy, iż dla 8 wierzchołków pierwszą parę można wybrać na 7 sposobów, a pozostałe trzy pary na 15 sposobów. Zatem liczba możliwych skojarzeń wynosi 7 × 15 = 105.

Dla 10 wierzchołków otrzymamy:
9 × 105 = 945.

Dla 12 wierzchołków otrzymamy:
11 × 945 = 10395

Dla 14 wierzchołków otrzymamy:
13 × 10395 = 135135

Dla k wierzchołków liczba skojarzeń wierzchołków w pary jest równa:
S = (k-1) × (k-3) × (k-5) × … × 7 × 5 × 3 × 1

Jest to iloczyn kolejnych liczb nieparzystych mniejszych niż k:

Sytuacja jest niekorzystna obliczeniowo, ponieważ iloczyn ten szybko rośnie i, na przykład, dla k = 20 otrzymujemy około 655 milionów kombinacji. Zatem jeśli podejdziemy do problemu metodą brutalną, to czas obliczeń dla dużych grafów może wynieść nawet stulecia.

Problem znajdowania skojarzeń par wierzchołków o minimalnych wagach krawędzi rozwiązuje algorytm Edmondsa pracujący w klasie złożoności O(n³). Jednakże jest on bardzo skomplikowany i wymaga dobrej znajomości teorii grafów oraz programowania liniowego. Dla prostszych przypadków (k < 20) można zaryzykować podejście kombinatoryczne.

Algorytm ogólny dla problemu chińskiego listonosza

K01: Sprawdź, czy graf jest spójny.
     Jeśli nie jest, 
     to zakończ algorytm z odpowiednim komunikatem
K02: Wyszukaj w grafie wszystkie wierzchołki
     o nieparzystych stopniach
K03: Jeśli liczba tych wierzchołków jest równa 0, 
     to idź do kroku K07
K04: Wyznacz za pomocą algorytmu Dijkstry
     najkrótsze ścieżki łączące ze sobą wszystkie
     znalezione wierzchołki o nieparzystych stopniach.
K05: Wyszukaj skojarzenie tych wierzchołków
     w pary o najmniejszej sumie wag krawędzi
K06: Krawędzie wchodzące w skład wyznaczonych
     ścieżek skojarzenia zdubluj w grafie wejściowym
K07: Wyznacz w grafie cykl Eulera i wyprowadź wynik
K08: Zakończ

Podany algorytm jest jedynie szkicem rozwiązania. Aby go efektywnie zaimplementować, należy rozwiązać kilka problemów. Oto niektóre z nich.

• jak zapamiętać znalezione wierzchołki o nieparzystych stopniach
• jak wyznaczyć wszystkie ścieżki łączące znalezione wierzchołki o nieparzystych stopniach
• jak zapamiętać ścieżki łączące te wierzchołki
• jak wyszukać skojarzenie o minimalnej sumie wag
• jak zdublować krawędzie