Algorytm wstawiania najdalszego miasta

W trakcie realizacji algorytmu dopuszczamy do rozważań cykle zawierające jeden lub dwa wierz-

choł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 (K

n

, w).

Wynik: Cykl Hamiltona H

∗

zawierający wszystkie wierzchołki grafu K

n

.

START

1. Wybierz wierzchołek x ∈ V (K

n

) i zbuduj cykl C złożony z tego wierzchołka;

2. Dopóki V (K

n

) \ V (C) 6= ∅ wykonuj

znajdź wierzchołek v ∈ V (C) × (V (K

n

) \ 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 u

i

, u

i+1

, dla których liczba w(u

i

, v) + w(v, u

i+1

) − w(u

i

, u

i+1

) jest

najmniejsza;

3. Przyjmij H

∗

:= C.

STOP

Twierdzenie 1. Niech (K

n

, 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

∗

) ¬ 2w(H).

1