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 05. 04. 2010 22:34 — Editoval adjamot (05. 04. 2010 22:44)
Obrácený problém sedmi mostů v Kralovci
Existuje OBECNÝ algoritmus, který umí určit, kolik nejméně existuje (otevřených) eulerovských tahů s původním rozmístění mostů-tedy kolik je potřeba obyvatel(návštěvníků, ...) aby všechny mosty (v původní konfiguraci) byli navštíveny právě jednou.....
nebo
kolik minimálně mostů musí být navštíveno vícekrát, aby existoval tah, který vede přes všechny mosty a ty budou navštíveny alespoň jednou bez nutnosti se vracet start procházky (takový trochu "degenerovaný otevřený eulerovský tah"-jen pro představu, nevím, jak se říká tomuto tahu)
http://cs.wikipedia.org/wiki/Sedm_most% … C3%A1lovce
EDIT: tedy výsledek by zněl takto: pokud Vás půjde minimálně x(z jiný vrcholů), pak jako skupina můžete vytvořit otevřený eulerovský tah
či pokud určitý most(y) navštívíte vícekrát, pak můžete vytvořit "degenerovaný eulerovský tah"
Smutné je, že hlupáci jsou tak sebejistí, zatímco moudří lidé jsou vždy plní pochybností.“ — Bertrand Russell
Offline
#2 22. 04. 2010 21:37
Re: Obrácený problém sedmi mostů v Kralovci
↑ adjamot:Nápověda k prvnímu. Ano, existuje obecné a řešení.
Je potřeba rozlišit, zda je graf souvislý a pokud ne, kolik vrcholů lichého stupně je v každé komponentě. Potom přidáním jednoho pomocného vrcholu a hran do všech vrcholů lichého stupně dostaneme graf, který má všechny vrcholy sudého stupně. Pozor! nemusí být souvislý a to je potřeba ohlídat. Dále se využije existence uzavřeného eulerovského tahu v každé komponentě.
U druhé varianty je řešení nejspíš obtížnější. Připomíná mi to variantu úlohy obchodního cestujícího, který má projít jen vrcholy lichého stupně. A hlavně řešení nemusí existovat, pokud původní graf není souvislý.
Offline