A csúcsokon adott egy irányított gráf. Tegyük fel, hogy .
Az alábbi feladatok közül melyiket NEM lehet polinomiális időben megoldani tetszőleges gráf esetén?

Question

A    csúcsokon adott egy irányított gráf. Tegyük fel, hogy   . 
 Az alábbi feladatok közül melyiket  NEM  lehet polinomiális időben megoldani tetszőleges gráf esetén?

Answer

Keressük a leghosszabb olyan utat a gráfban, melynek mentén a csúcsok indexe monoton nő.

Answer

Keressük a legrövidebb  olyan utat a gráfban, melynek mentén az indexek legalább 3-mal csökkennek minden lépésben.

Answer

Keressük a leghosszabb olyan utat a gráfban, melyben minden csúcs indexe páros.

Answer

Keressük a legrövidebb olyan utat a gráfban, melyben minden csúcs indexe páratlan.

Crowdly

A csúcsokon adott egy irányított gráf. Tegyük fel, hogy . Az alábbi felad...

Want instant access to all verified answers on edu.vik.bme.hu?