Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 17. 08. 2014 23:28
vsetky cesty medzi 2 vrcholmi
Ahojte,
chcem sa opýtať či existuje nijaký algoritmus na nájdenie všetkých ciest v neorientovanom grafe. Tak aby nevznikol cyklus, teda každý vrchol v jednej ceste môže byť použitý iba raz. Ale v ďalších cestách sa môže použiť.
Ďakujem
Offline
#2 18. 08. 2014 20:45
Re: vsetky cesty medzi 2 vrcholmi
↑ p4too:
podle mě to řeší poštákův problém a nebo problém obchodního cestujícího, nejsem si ted jistý, jeden řeší že mužeš projít jeden vrchol vícekrat a druhý že jen jednou myslím. Víc bych věřil obchodnímu cestujícímu
Jsou věci, které nikdy nepochopím.
Offline
#3 19. 08. 2014 18:34
Re: vsetky cesty medzi 2 vrcholmi
↑ Dopikasan:
Ak si niesi isty, presvedc sa googlom.
Obchodny cestujuci v cistom zneni rozhoduje existenciu Hamiltonovskeho cyklu, neriesi vsetky cesty.
Kazdopadne uz len pocet takych ciest moze byt strasne velky. Samozrejme sa da pouzit trapna dynamika ktora rata pocty ciest ktore obsahuju vsetky vrcholy z mnoziny 
a koncia vo vrchole 
, ale pre 40-vrcholovy graf to uz bude behat hodiny.
Offline