Grafové problémy (obsah)

Nejkratší cesta Problém nejkratší cesty je NP-úplná grafová úloha, jejímž cílem je nalézt v zadaném grafu nejkratší cestu mezi uzly a . Rozhodovací varianta úlohy pak odpovídá na otázku, zda-li v daném grafu existuje mezi body a cesta délky maximálně . Problém nejdelší cesty Velmi podobným problémem je úloha nalezení nejdelší cesty, jejímž cílem je nalézt mezi body a cestu nejvyšší délky. V...

Problém obchodního cestujícího (Travelling salesman problem) je úloha kombinatorické optimalizace, jejíž cílem je nalézt v zadaném ohodnoceném úplném grafu kružnici takovou, že prochází všemi vrcholy a zároveň je její cena minimální. Jinými slovy se jedná o nalezení nejkratší hamiltonovské kružnice v ohodnoceném grafu. Motivace V dané zemi existuje mnoho měst, mezi všemi městy je postavené silnice. Cílem obchodního cestujícího je objet všechna ...

Sedm mostů města Královce Město Královec (Königsberg, Kaliningrad) se rozprostírá na březích a ostrovech řeky Pregely. Mezi jednotlivými břehy a ostrovy vede sedm mostů (viz obrázek). Obyvatele města zajímalo, zda-li mohou při svých promenádách projít všechny mosty takovým způsobem, že se dostanou opět do původního místa, aniž by jednu spojnici přešli dvakrát. Parafrází na tento problém jsou všechny ...