Matematické Fórum

k4m1k4z33 · 28. 04. 2013 21:46

Zdravím, mám takovéhle zadání:

Rozhodněte, zda jsou zadané problémy P, NP nebo NPC. Je dán graf G(V,E) a dva vrcholy u,v a číslo $k \in \mathbb{N}$ . Existuje mezi těmito vrcholy cesta a) délky nejvýše k, b) právě k, c) alespoň k?

Problém c), v podstatě nejdelší cesta v grafu jsem převedl na problém hamiltonovské cesty, tedy je NPC.
Problém a), nejkratší cesta jsem převedl na nejdelší cestu, tedy rovněž NPC.

Potřeboval bych nějak nakopnout, jak s problémem b), nevím si rady...

Předem díky

JohnPeca18

Dlzku cesty myslis ako v ohodnocenem grafu, nebo jenom ako pocet hran na ceste? Pokud pocet hran na ceste tak a) je normalne P. Da sa riesit Dijkstrou alebo cimkoliv. Problem je jenom kdyz mas ohodnoceni se zapornymi hranami. I tak by mozna slo resit takhle definovany problem ale tim si ted nejsem jisty. Nevim jak si to prevedl na nejdelsi cestu ale uvedom si ze $k\in N$ a teda $k>0$ . To jenom takovy postreh.

a b) nestaci previst na hamiltonovsku cestu stejnym spusobem? zeptam se jestli je v grafu cesta delky $|V|-1$ .

k4m1k4z33 · 28. 04. 2013 22:22

Podle zadání předpokládam, že se jedná jen o počet hran na cestě, protože až další úloha se ptá na to co se stane když hrany ohodnotíme kladně a délka cesty bude součet hran a jak se změní při záporném ohodnocení.

Potom tedy a) je P řešitelný třeba Dijkstrou jak říkáš

a jak s b) c)? už mi to vůbec nemyslí :/

JohnPeca18 · 29. 04. 2013 09:09

No prevedes to na Hamiltonovsku cestu tak, ze sa pre 2 vrcholy zeptas jestli existuje mezi nimi cesta delky prave $|V|-1$ pro b) alespon $|V|-1$ pro c). V oboch pripadoch, musi takato cesta prechadzat vsemi vrcholy grafu. Takze bude hamiltonovska. Tohle muzes udelat pro vsechny dvojice vrcholu a tak dostanes algoritmus pro problem hamiltonovskej cesty coz je NPC.

k4m1k4z33 · 29. 04. 2013 10:26

Jasně, takže pro to b)

$HamiltonovskaCesta \lhd_p NejdelsiCesta$

$G(V,E) \Rightarrow G'(V', E') = G(V,E)$

cena hran $c(e') = 1$

$k = |V|-1$

a pro c) totéž akorát

$k \ge |V|-1$

je to tak? :)