[PDF] 3–Coloration dun graphe Démonstration. Étape 1 : 3Col ?

View - Download 3–Coloration dun graphe

Previous PDF

Next PDF

Agrégation 2018/2019

3-Coloration d"un graphe

(rédigé par David Xu)

Leçons :915;925 ;928

Références :CORMEN-LEISERSON-RIVEST-STEIN,Introduction à l"algorithmique(p.1014) [?]

Prérequis :-la NP-complétude de3Sat(

entrée :une formule'en3-Cnf(calcul propositionnel) sortie :oui si'est satisfiable, non sinon

Introduction :On va montrer dans ce développement que le problème de 3 coloration d"une graphe est

NP-complet. Pour cela, on va réduire le problème3Satà3Col. C"est une des arêtes du graphe

en app endice sur les problèmes NP-complets. Définition 1.On dit qu"une grapheG= (S;A)est3coloriable s"il existe une application c:S! f1;2;3g telle que, pour tout(u;v)2A,c(u)6=c(v).Théorème 1.Le problème de3coloration de graphe 3Col( entrée :un grapheG= (S;A)non orienté sortie :oui siGest3coloriable, non sinon estNP-complet.Démonstration.

Étape 1 :3Col2NP

Ce problème est bien dansNPcar on peut vérifier en temps polynomial (en le nombre d"arêtes du graphe) qu"une coloration d"un graphe vérifie bien les propriétés voulues.

Étape 2 :3ColestNP-dur

Pour montrer cela, on va définir une réduction à partir du problème3Satqui estNP-dur (et mêmeNP-complet).13Sat

3Coloui

nontraductiontr(')' 1

. On utilise le théorème de Cook et la transformation de Tseitin pour avoir laNP-complétude deCnfSatpuis

on peut réduire le nombre de littéraux dans chaque clause en ajoutant des nouvelles variables et des nouvelles

clausesENS Rennes - Université de Rennes 1 1 Pierre Le Barbenchon

Agrégation 2018/2019

Soit donc'une formule du calcul propositionnel en3-Cnfpossédantmclauses, '=m^ j=1C j:Notonsp1;:::;pnles variables propositionnelles qui apparaissent dans'. On va construire un graphetr(')qui repose sur le squeletteG0suivant :G 0=vf r p 1:p1p 2:p2p n:pn... On peut remarquer que dans une coloration de ce graphe, la couleur d"une variable proposi- tionnellepsera toujours différente de celle de:pet qu"un littéral aura toujours la couleur dev ou defmais pas celle der.

Puis, pour chaque clauseC= (C_C_

C)de', on va "connecter" le gadget suivant àG0

pour former le grapheG:G C= C C Cx Cy Cz Cs Ct Cv Ainsi le grapheG=tr(')possède3+2n+5msommets. La réductiontr(')est donc calculable en temps polynomial enm, le nombre de clauses de(carn63m). Pour montrer quetrdéfinit bien une réduction de3Satà3Col, nous utiliserons les deux lemmes suivants :Lemme 1. On peut compléter toute coloration partielle d"un gadgetGCoù les sommetsC,C et Csont de la couleur defouvet où l"un d"eux est de la couleur deven une coloration licite deGC.Démonstration.Il suffit de traiter tous les cas, il y en a231 = 7.Lemme 2. Dans toute coloration d"un gadget de la formeGC, l"un des sommetsC,Cou Ca la couleur dev.Démonstration.

Par l"absurde, supposons queC,Cet

Cont tous la couleur def(on rappelle

qu"ils ont soit la couleur dev, soit celle def). CommeCetCont la couleur def, les sommetsENS Rennes - Université de Rennes 1 2 Pierre Le Barbenchon

Agrégation 2018/2019

x CetyCont les couleurs derouvet leur couleur est différente car ils sont liés par une arête. zCa donc nécessairement la couleur def. De même, commezCet

Cont la couleur def, on en

déduit queva la couleur def. Contradiction.Proposition 1. Pour toute formule'en3-Cnf,'est satisfiable si et seulement sitr(')est

3coloriable.Démonstration.Soit'une formule en3-Cnf.=)

Soitune valuation qui satisfait',j='. On fixe des couleurs différentes pour les sommetsv,fetrdetr('),c(v),c(f)etc(r), et on colorie les sommets associés aux variables propositionnelles de'de la façon suivante : pour touti2 f1;:::;ng,c(pi) =( c(v)si(pi) = 1 c(f)sinonetc(:pi) =( c(v)si(pi) = 0 c(f)sinon.

Commej='=Vm

j=1Cj, on a8j2 f1;:::;mgj=Cj= (Cj_Cj_

Cj), donc dans chacun

des gadgetsGC, l"un des sommetsC,Cou Cest de la couleur dev. Donc d"après le lemme 1, on peut compléter les colorations partielles desGCen une coloration detr('). Donctr(')est

3coloriable.(=Soitcune3coloration detr('). On définit une valuationpar :

pour touti2 f1;:::;ng,(pi) =(

1sic(pi) =c(v)

0sinon.

D"après le lemme 2, dans chaque gadgetGC, l"un des sommetsC,Cou

Ca la couleur dev,

donc pour toutj2 f1;:::;mgj=Cj, doncj='. La formule'est satisfiable.Ce qui prouve que3ColestNP-dur et doncNP-complet.Remarques :

On a supposé que les instances de3Satsont des formules ayant exactement3littéraux par

clauses, mais si considère que les clauses ont au plus3littéraux, alors on construit les gadgets

G

Cen mettant desfà la place de

CsiC=C_CouCet

CsiC=C.Astuces de l"agrégatif :

Pendant le développement, je ne donnais pas de nom aux sommets intérieurs deGCet pour prouver le lemme2, je notais les couleurs des sommets sur le dessin deGCdirectement. Parfois, on parle de coloration propre pour désigner une coloration telle que deux sommets

qui sont adjacents sont de couleurs différentes.ENS Rennes - Université de Rennes 1 3 Pierre Le Barbenchon

quotesdbs_dbs23.pdfusesText_29

[PDF] 5: La coloration de Gram - BiOutils

[PDF] 5: La coloration de Gram - BiOutils

[PDF] 5: La coloration de Gram - BiOutils

[PDF] COLORATION AU BLEU DE METHYLENE COLORATION DE GRAM

[PDF] Une nouvelle méthode simple et rapide de coloration différentielle

[PDF] COLORATION AU BLEU DE METHYLENE COLORATION DE GRAM

[PDF] Coloriages magiques

[PDF] Coloriages magiques avec les lettres 5-7 ans

[PDF] Coloriages magiques avec les lettres 5-7 ans

[PDF] Images correspondant ? coloriage petit loup imprimer filetype:pdf

[PDF] Faut-il dépister le cancer colo-rectal chez la personne âgée?

[PDF] Quand faut-il faire une coloscopie de contrôle après une - HAS

[PDF] Dépistage et prévention du cancer colorectal - HAS

[PDF] Quel rythme de surveillance après une coloscopie - Hepatowebcom

[PDF] Réglement de la Banque d 'Algérie 2016 - Douanes Algériennes