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
Zdravím, měl by někdo nějaký hint jak na takovýto příklad?
Uvažujme problém, jehož instancí je orientovaný graf s vybraným vrcholem v a dále k
‘oblázků’. Můžeme v jakémkoli pořadí provádět následující elementární kroky:
• na vrchol x můžeme položit oblázek, pokud v daný okamžik leží oblázky na všech
vrcholech, z nichž vede hrana do x,
• oblázek položený na vrchol můžeme odebrat (a znovu použít později).
Otázkou je, zda existuje posloupnost kroků, při níž položíme oblázek na zadaný vrchol v.
Prokažte, že problém je v PSPACE.
Offline
↑ amissus:
V tom popisu chybí něco o tom jestli jsou na začátku v grafu umístěny nějaký oblázky...
Jestli ne, tak není co řešit
Offline