Ahoj,
takže já nejsem poctivý student, na cvičení nechodím, a když jsem se to pokusil najít, tak to nikde není pořádně napsané. Takže zhruba na co jsem přišel (termín kratší je vzhledem k metrice, lehčí/těžší k váhové funkci):
Je dobré vědět, že každá hamiltonovská kružnice je alespoň tak těžká, jako minimální kostra (vynecháním libovolné hrany z HK mám kostru, tím jsem si ale mohl pouze odlehčit).
je graf, který vznikne z kostry přidáním zkratek (dál kdykoliv mluvím o zkratce, tak myslím takovouto hranu), které překročí nanejvýš 3 hrany.
Také by mělo být jednoduché ubastlit nějaký algoritmus, který ti najde v
HK -- podobně jako u normální redukce TSP, prostě procházíš strom a když narazíš na navštívený vrchol, tak ho přeskočíš, jenom je potřeba být trošku opatrnější, protože nemůžeš skákat neomezeně daleko. Podle mě stačí nějaký hloupý algoritmus, který jde DFS a vždy jeden vrchol vynechá, když se vrací tak jde po těch vynechaných vrcholech a skoky délky 3 si nechá na případ, když je někde nějaká blbá kombinace liché/sudé cesty (asi by to šlo zformulovat lépe, ale hlavní je myšlenka).
Teď nám jenom stačí ukázat, že není ta HK moc špatná. To je ale jednoduché. Kdybychom šli pouze po kostře, tak je všechno OK. Ale my jsme brali zkratky -- každou teoreticky až přes 3 hrany. Kdyby váha zkratky byla nanejvýš 3-krát větší než váha cesty, jsme v suchu (chyba se nesčítá přes všechny zkratky, je to maximum!). Kdyby ale byla váha ostře větší než 3-krát, tak délka cesty je nanejvýš délka zkratky (ostře) a neplatí trojúhelníková nerovnost (vyplatilo by se jít po třech hranách namísto jedné...). Tedy jsme si každou zkratkou pohoršili nanejvýš 3-krát a celkové to samé (opakuji, že chyba se nekumuluje, je to maximumové váhová funkce). Hurá.
(Protože všechny poznámky co mám jsou zmatené, nečitelné, nebo obojí, tak nedávám žádnou záruku. Pevně ale věřím tomu, že to funguje. Navíc asi existuje jednodušší algoritmus na nalezení HK (snáz dokazatelný), ale v jednu v noci to po mě nikdo nemůže chtít
)
Zdar odpoledne na zápočtové písemce