Matematické Fórum

Ahoj,mám nějaký problém s důkazem NP úplnosti vrcholového pokrytí a chtěl bych Vás poprosit o pomoc . Konstrukci rozumím,ale nerozumím důkazu,že redukce je správná. Pokud jsem to pochopil správně,tak vrcholové pokrytí by měla být množina uzlů W která je podmnožinou množiny uzlů z grafu G.Přičemž uzly z W pokryjí všechny hrany grafu,takže každá hrana obsahuje alespoň jeden uzel z W.

Pokud chápu správně redukci které je provedena tak ,že se redukuje jazyk splnitelných boolovských formulí o třech proměnných 3SAT na Vrcholové pokrytí grafu,tak by mělo platit,že pokud si ohodnotím proměnné formule jazyka 3SAT tak, aby formule byla splnitelná,pak bych měl mít pokryté všechny hrany grafu ,ale nějak mi to u daného příkladu nefunguje.

formule:

formule je splnitelná například pokud ohodnotím proměnné x2=1 a x1=0,ale nepokryjí se mi všechny hrany grafu.