3-SAT 3-COLORING | NP COMPLETUDE

Exercice NP complétude : couverture dans les graphes

Exercice Analyse & Conception des Algorithmes Avances : 3-SAT ---- 3 COLORING

Montrer que le problème 3-SAT se réduit polynomialement au problème 3-COLORING.

Correction NP COMPLÉTUDE

  1. Démonstration :  La coloration à trois couleurs est un problème qui appartient à la classe NP.
  • Certificat : Pour chaque nœud, une couleur choisie parmi {1, 2, 3}.
  • Certifier : Vérification que pour chaque arête (u, v), la couleur du nœud u est différente de celle du nœud v.
  • Difficulté : Nous allons démontrer que le problème 3-SAT est réductible au problème de coloration à trois couleurs (3-Coloration). 3-SAT ≤P 3-Coloring

Nous débutons avec une formule 3-SAT φ qui possède n variables x1, ..., xn et m clauses C1, ..., Cm. Nous créons le graphe Gφ de telle manière que Gφ soit colorable à trois couleurs si et seulement si φ est satisfaisable.

  • Il nous faut établir une attribution de vérité pour x1, ..., xn en utilisant les couleurs pour certains nœuds de Gφ.
  • Nous créons un triangle avec les nœuds Vrai, Faux et Base.
  • Pour chaque variable xi, nous avons deux nœuds vi et  ¬vi reliés par une arête dans un triangle partageant le nœud Base.
  • Si le graphe peut être coloré à trois couleurs, soit vi soit  ¬vi doit obtenir la même couleur que Vrai. Nous interprétons ceci comme une attribution de vérité à vi.
  • Pour chaque clause Cj = (a ∨ b ∨ c), nous créons un petit graphe gadget. Le graphe gadget est relié aux nœuds correspondant à a, b, c. Cela doit implémenter la fonction OU (OR).

Propriété : Si a, b, c sont colorés Faux dans une coloration à trois couleurs, alors le nœud de sortie du gadget OR doit être coloré Faux.

Propriété : Si l'un parmi a, b, c est coloré Vrai, alors le gadget OR peut être coloré à trois couleurs de telle manière que la sortie du gadget OR soit colorée Vrai.

Nous créons un triangle avec les nœuds Vrai, Faux et Base.

  • Pour chaque variable xi, nous avons deux nœuds vi et  ¬vi reliés par une arête dans un triangle partageant le nœud Base.
  • Pour chaque clause Cj = (a ∨ b ∨ c), nous ajoutons le graphe gadget OR avec les nœuds d'entrée a, b, c et nous relions le nœud de sortie du gadget à la fois au nœud Faux et au nœud Base.

Exemple φ = (u ∨ ¬v ∨ w) ∧ (v ∨ x ∨ ¬y)

3sat 3coloring pandacodeur

 

Si φ est satisfaisable, alors cela implique que  Gφ est 3-Coloriable .

  • Si xi est attribué Vrai, nous colorons vi en Vrai et ¬vi en Faux.
  • Pour chaque clause Cj = (a ∨ b ∨ c), au moins l'un parmi a, b, c doit être coloré Vrai. Le gadget OR pour Cj peut être coloré à trois couleurs de manière à ce que la sortie soit colorée Vrai.

Si Gφ est 3-Coloriable , alors φ est satisfaisable.

  • Si vi est coloré Vrai, nous attribuons Vrai à xi, ce qui constitue une attribution de vérité valide.
  • Pour toute clause Cj = (a ∨ b ∨ c), il ne peut pas être que a, b, c soient tous colorés Faux. Si tel était le cas, la sortie du gadget OR pour Cj doit être colorée Faux, mais cette sortie est reliée à la Base et à Faux !

Si vous avez trouvé les exercices corriges sur la Complexité des Algorithmes & Structure de donnée de Mr JoëlYk intéressants et utiles, pourquoi ne pas les partager avec d'autres personnes qui pourraient également en bénéficier ? Partagez ce lien sur les réseaux sociaux ou envoyez-le à vos amis et collègues. Vous pourriez aider quelqu'un à améliorer ses compétences en programmation ou à trouver des solutions à des problèmes complexes. N'oubliez pas que la connaissance doit être partagée pour grandir. Merci pour votre soutien et votre partage !

Contact WhatsApp : +237 658395978 | Réaliser Par Joël_Yk

Aucune note. Soyez le premier à attribuer une note !

Ajouter un commentaire

Anti-spam
Sélectionnez l'image visible le moins de fois

Gestion des cookies

www.pandacodeur.com dépose des cookies pour améliorer votre expérience de navigation, mesurer l'audience du site internet, afficher des publicités personnalisées, réaliser des campagnes ciblées et personnaliser l'interface du site.