Matematické Fórum

Dobrý den,

mam takový problém:

Banda lidí jede na výlet. Startují z New Yorku a mají v plánu navštívit dalších 6 měst v Evropě. Jako hodnost jednotlivých hran mám cenu letenek ze všech měst všude. Vznikne mi kompletní graf K7 a nyní musím najít nejkratší hamiltonovskou cestu tak, aby banda lidí navštívila všechna města za co nejlepší cenu a VRÁTILA SE ZPĚT DO NY.

hledala jsem to na internetu, ale nenašla jsem konkrétní postup, jak na to. Našla jsem něco jako že se graf překreslí na takový (docela hodně veliký) strom, podle kterého zjistíme, že graf obsahuje třeba 3 hamiltonovské cesty a pak vyberu tu nejkratší. Ale když mám graf se sedmi vrcholy a navíc je kompletní, tak nevím.

Díky moc za rady :)