DSC00293 (7)

Droga Hamiltona droga prosta przechodząca przez wszystkie wierzchołki grafu.    _t

Algorytm:

1.    Wyznaczenie wszystkich składowych silnej spójności grafu G.

( Algorytm Leifmana).

2.    Tworzenie grafu Hertza H(G) - wierzchołkami grafu Hertza są składowe silne) spójności, hikt występujące między składowymi silnej spójności wyznaczają hdd grafu Hertza.

3.    Wyznaczenie warstw grafu Hertza ( Graf Hertza jest digrąfem

acyklicznym w sensie dróg)    -

4.    Wyznaczenie drogi Hamiltona w grafie Hertza, gdy wszystkie warstwy są jednowierzchołkowe ( ustalenie kolejności występowania w drodze Hamiltona poszczególnych składowych silnej spójności).

5.    Dobieranie łuków pomiędzy składowymi silnej spójności umożliwiających „zszycie" dróg Hamiltona z poszczególnych składowych silnej spójności.