Algorytm wstawiania najdalszego miasta

W trakcie realizacji algorytmu dopuszczamy do rozważań cykle zawierające jeden lub dwa wierzchołki.

Jeżeli C jest cyklem w grafie G i v ∈ V ( G) \ V ( C), to definiujemy odległość wierzchołka v od cyklu C:

d( v, C) := min {w( v, u) : u ∈ V ( C) }.

Dane: Pełny graf ważony ( Kn, w).

Wynik: Cykl Hamiltona H∗ zawierający wszystkie wierzchołki grafu Kn.

START

1. Wybierz wierzchołek x ∈ V ( Kn) i zbuduj cykl C złożony z tego wierzchołka; 2. Dopóki V ( Kn) \ V ( C) 6= ∅ wykonuj znajdź wierzchołek v ∈ V ( C) × ( V ( Kn) \ V ( C)), dla którego odległość d( v, C) jest największa;

dołącz wierzchołek v do cyklu C w taki sposób, aby przyrost długości cyklu był

najmniejszy, tzn. wstaw wierzchołek v do cyklu C pomiędzy takie dwa kolejne wierzchołki ui, ui+1, dla których liczba w( ui, v) + w( v, ui+1) − w( ui, ui+1) jest najmniejsza;

3. Przyjmij H∗ := C.

STOP

Twierdzenie 1. Niech ( Kn, w) będzie pełnym grafem ważonym spełniającym warunek trójkąta.

Jeżeli H jest rozwiązaniem problemu komiwojażera dla tego grafu, a H∗ jest cyklem otrzymanym za pomocą powyższego algorytmu, to

w( H∗) ¬ 2 w( H) .

1