Příklad 3.4

Máme za úkol najít Hamiltonovu kružnici a nejkratší cestu (viz obr. 3.14).

Obr. 3.14 Graf k příkladu 3.4

Délka Hamiltonovské kružnice: A – B – C – D – A = 23 jednotek.

Nejkratší délka cesty A – D – C – B – C – A = 20 jednotek.

Příklad 3.5

Máme za úkol najít Hamiltonovu kružnici pomocí rozhodovacího stromu (viz obr. 3.15).

Obr. 3.15 Síťový graf k příkladu 3.5

Řešení:

Tam, kde nelze dále pokračovat, je značka X.

Obr. 3.16 Rozhodovací strom - příklad 3.5

Pro graf na obr. 3.16 existují dvě Hamiltonovské kružnice, které se liší jen pořadím uzlů.

Hamiltonovské kružnice:

První: A – F – E – G – D – C – B – A.

Druhá: A – B –C – D – G – E – F – A.