Réduction 3sat et clique

Question

Bonjour à tous, c'est ma première question de tous les temps et je m'excuse si je demande de la mauvaise manière, ce qui fait fermer ce message ou supprimé. J'apprends des réductions et mon professeur nous a demandé d'écrire un article sur les réductions (3SAT)

Lors de la réduction du problème de la clique au 3SAT, je comprends que nous faisons des clauses et que chaque clause contient 3 littéraux (d'où 3SAT), mais mon problème vient lors du choix des littéraux et pourquoi ils les choisissent. Comment savoir quels littéraux choisir? Je sais donc que dans chaque clause, j'aurai x1, x2 et x3, mais comment choisir leur ordre d'affectation? Dans une clause, j'ai (x1 ou x2 ou x3) et dans un autre j'ai (x1 ou pas x2 ou pas x3). Comment ont-ils été choisis?

De plus, il semble qu'ils ne commencent pas déjà par un graphique en tête. Et si on me donnait un graphique pour commencer, comment le convertirais-je en x1, x2, x3? Si pour la clause, j'ai 3 sommets, comment pourrais-je leur attribuer leur expression booléenne respectée? Merci beaucoup