Tekintsük a következő eldöntési problémát:
Adott egy csúcsú egyszerű gráf, amiről azt kell eldönteni, hogy kiszínezhetők-e a csúcsai 2026 színnel úgy, hogy azonos színű csúcsok között nem vezet él.
Mi igaz az alábbiak közül, ha feltételezzük, hogy ?

Question

Tekintsük a következő eldöntési problémát:  
 Adott egy    csúcsú egyszerű gráf, amiről azt kell eldönteni, hogy kiszínezhetők-e a csúcsai 2026 színnel úgy, hogy azonos színű csúcsok között nem vezet él. 
 Mi igaz az alábbiak közül, ha feltételezzük, hogy   ?

Answer

A probléma   -ben van, de nincsen   -ben.

Answer

A probléma   -ben és   -ben is benne van.

Answer

A probléma   -ben van és   -teljes is.

Answer

A probléma   -teljes és nincsen   -ben.

Crowdly

Tekintsük a következő eldöntési problémát: Adott egy csúcsú egyszerű gráf,...

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