Pourquoi la réduction du 3SAT à l'EI est-elle un travail?

Question

Je lisais sur la réduction de 3SAT (entrée: formule) à Ensemble indépendant (entrée (graphique, k)) afin de prouver que ce dernier est dans NP-complete. La réduction que j'ai vue suivre les prochaines étapes:

1. Pour chaque clause à l'entrée, créez un nœud pour chaque variable qu'il contient au cas où il n'existe pas encore. Ensuite, créez un $ k_3 $ avec ces nœuds.
2. Créez un bord entre un nœud et sa négation.

Un exemple que j'ai trouvé:

Tout en prouvant que cette réduction est correcte, ils disent:

$ Rightarrow $) Si la formule est satisfaisante, il y a au moins un vrai littéral dans chaque clause. Soit S un ensemble de un tel vrai littéral de chaque clause. | S | = k et pas deux nœuds en s sont connectés par un bord.

Je ne comprends pas pourquoi cela fonctionne. Je veux dire, $ k $ est corrigé à ce stade (à partir de l'entrée) donc si $ k = 3 $ je peux prendre $ s = {x_1, x_3, x_4 } $. Si $ k = 2 $ je peux prendre $ s = {x_2, x_4 } $ mais si $ k = 1 $ je ne peux pas.

Pourriez-vous m'expliquer pourquoi cela fonctionne ou si je ne comprends rien correctement? Merci.