====== JFiZO - zadanie 09.096 ======

Pokażemy, że problem znalezienia ścieżki dwa razy gorszej od optymalnej dla problemu komiwojażera jest nie łatwiejszy od problemu cyklu Hamiltona, czyli potrafiąc go rozwiązać, potrafimy rozwiązać problem Hamiltona. Skonstruujemy redukcję wielomianową przekształcającą instancję problemu cyklu Hamiltona (dowolny graf nieskierowany) w instancję problemu komiwojażera.

  - Wczytaj nieważony graf nieskierowany.
  - Wszystkim krawędziom przypisz wagę $1$.
  - Policz krawędzie (niech ich liczba wynosi $n$).
  - Dodaj do grafu krawędzie tak, żeby stał się grafem pełnym.
  - Każdej dodanej krawędzi przypisz wagę $2n$.

Teraz, jeśli nasz algorytm znalazł rozwiązanie o długości mniejszej niż $n$, to znalazł cykl Hamiltona w oryginalnym grafie. W przeciwnym przypadku rozwiązanie zawiera co najmniej jedną dodaną krawędź, a więc jest większe niż $2n$, czyli rozwiązanie komiwojażera (optymalna ścieżka) jest większe niż $n$ -- nie mieści się w oryginalnym grafie ergo nie istnieje w nim cykl Hamiltona.