„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
|||
| 217. sor: | 217. sor: | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
Legyen az eldöntési probléma neve A<br> | |||
G ∈ A akkor, ha G∈3SZÍN vagy G∈H<br> | |||
Adjunk 3SZÍN < A Karp redukciót, ekkor mivel a 3SZÍN probléma NP-teljes az A is NP-teljes lesz.<br><br> | |||
G' legyen az a gráf, amelyet úgy kapunk, hogy G-t kiegészítünk egy 3 csúcsból álló körrel. Mivel G'-ben biztosan nincs Hamilton-út ( Nem összefüggő ), ezért G' ∈ A akkor és csakis akkor, ha G ∈ 3SZÍN | |||
}} | }} | ||
[[Kategória:Infoalap]] | [[Kategória:Infoalap]] | ||