$NP$-complétude de cut-max

Bonjour,
je ne comprends pas la fin de la preuve.

En fait je comprends très bien la construction du graphe. Par contre je ne comprends pas en quoi une affectation valide d'une instance de NAE3SAT fournit une coupure dans le graphe. Ce graphe représente la formule et non l'affectation qui rend la formule satisfiable donc je ne vois pas trop comment c'est possible.

Ce que je veux dire c'est que le graphe représente toujours la formule. Il ne tient pas compte de l'affectation, il n'en dépend pas. En tout cas c'est comme ça qu'a été construit le graphe. Donc qu'importe l'affectation qu'on choisit, on y trouve toujours la même coupure.

Voyez-vous ce que je veux dire ?
Merci pour votre aide.

[Doublon. Continuer sur l'autre discussion. AD] http://www.les-mathematiques.net/phorum/read.php?16,1919882,1919882#msg-1919882