Algorytm wstawiania najbliższego

miasta

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

chołki.

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 v ∈ 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ź parę wierzchołków (u

0

, v

0

) ∈ V (C) × (V (K

n

) \ V (C)), dla której spełniona

jest równość w(u

0

, v

0

) = min{w(u, v) : (u, v) ∈ V (C) × (V (K

n

) \ V (C))};

dla wierzchołków u

−1

, u

1

sąsiadujących w cyklu C z wierzchołkiem u

0

wybierz

ten, dla którego liczba w(u

i

, v

0

) + w(v

0

, u

0

) − w(u

0

, u

i

), i ∈ {−1, 1} jest mniejsza

(jeżeli obie obliczone liczby są równe, wybierz dowolny z dwóch badanych wierz-

chołków); wstaw wierzchołek v

0

do cyklu C pomiędzy wybrany wierzchołek u

i

oraz

wierzchołek u

0

;

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