Adott egy G gráf, ennek két csúcsa x és y , valamint egy k egész szám. Azt akarjuk eldönteni, hogy van-e olyan, az x és y csúcsokat összekötő út, ami a két végpont között legalább k darab csúcson átmegy. (Egy út minden csúcsot legfeljebb egyszer érint.) Tekintsük ennek három változatát:
I: G irányítatlan gráf
II: G tetszőleges irányított gráf
III: G olyan irányított gráf, amiben nincs irányított kör. Melyik helyes az alábbiak közül?

Question

Adott egy  G  gráf, ennek két csúcsa  x  és  y , valamint egy  k  egész szám. Azt akarjuk eldönteni, hogy van-e olyan, az   x  és  y  csúcsokat összekötő út, ami a két végpont között legalább  k  darab csúcson átmegy. (Egy út minden csúcsot legfeljebb egyszer érint.) Tekintsük ennek három változatát:  
 I:  G  irányítatlan gráf 
 II:  G  tetszőleges irányított gráf 
 III:  G  olyan irányított gráf, amiben nincs irányított kör. Melyik helyes az alábbiak közül?

Answer

Az I változatra van polinom idejű algoritmus, de II és III NP-teljes.

Answer

A probléma mindhárom változatára ismert polinom idejű algoritmus.

Answer

Az I változat NP-teljes, de II-re és III-ra ismert polinom idejű algoritmus.

Answer

A probléma mindhárom változata NP-teljes.

Answer

Az I és II változat  NP-teljes, de III-ra ismert polinom idejű algoritmus.

Crowdly

Adott egy G gráf, ennek két csúcsa x és y , valamint egy k egész szám. Az...

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