Wiejski listonosz roznosi pocztę po okolicy. Każda wieś leży przy drodze albo na przecięciu dwóch lub czterech dróg, zatem można z niej wyjść w 2, 4 lub 8 kierunkach (niektóre drogi mogą prowadzić ze wsi do niej samej, a pomiędzy dwiema wsiami może być więcej niż jedna bezpośrednia droga). Budynek poczty jest w jednej ze wsi. Listonosz musi odwiedzić wszystkie wsie, a ponadto musi przejść wzdłuż wszystkich dróg (przy nich też stoją domy) i wrócić na pocztę. Za przejście każdej mili poczta płaci listonoszowi 1EUR. Ponadto mieszkańcy każdej wsi chcą, aby listonosz odwiedził ich jak najwcześniej, dlatego poczta zawarła z każdą ze wsi (wsie numerujemy liczbami ) umowę, w której określona jest pewna liczba : mianowicie, jeśli listonosz odwiedzi wieś numer jako -tą w kolejności (tzn. odwiedził wcześniej dokładnie różnych innych wsi) oraz to wieś dopłaca poczcie EUR, a jeśli to poczta karnie płaci wsi EUR. Jak wyznaczyć trasę listonosza, aby zmaksymalizować zysk (ew. zminimalizować stratę) poczty? Na wejściu mamy daną liczbę wsi , opis grafu dróg i umówione wartości ,