<<<< Obsah >>>>

Hamiltonovské cesty a kružnice

· Hamiltonovská cesta v grafu G je cesta, která obsahuje každý uzel grafu G právě jednou.

· Hamiltonovská kružnice (cyklus) v grafu G je kružnice (cyklus), která prochází každým uzlem grafu, u které je počáteční a koncový uzel totožný [Demel, J., 1982].

Typy úloh:

1. Najít Hamiltonovskou kružnici (cyklus) - (úloha obchodního cestujícího).
2. Najít Hamiltonovskou cestu (mezi libovolnými dvěma uzly).
3. Najít Hamiltonovskou cestu, jejíž krajní uzel je fixován.
4. Najít Hamiltonovskou cestu, jejíž oba krajní uzly jsou fixovány.

Pro řešení těchto typů úloh neexistuje žádný efektivní algoritmus.

Rozhodovací strom

· Používá se pro jednoduché úlohy.

· V každém uzlu rozhodujeme, kam jít dál, ale nesmíme se vrátit do uzlu, ve kterém jsme byli.

Zde jsou příklady na procvičení probrané látky. Hamiltnovy cesty a kružnice.

<<<< Nahoru >>>>