[PDF] Exercices corrigés sur probl`emes NP-complets

View - Download Exercices corrigés sur probl`emes NP-complets

Previous PDF

Next PDF

Exercices corrig´es sur probl`emes NP-complets

Johanne Cohen

12 septembre 2018

Table des mati`eres

1 Rappel succinct de cours 1

2 Enonc

´es des exercices 5

I) Probl`eme de d´ecisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 a) Graphe eul´erien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 b) Formulation des probl`emes de d´ecisions . . . . . . . . . . . . . . . . . 6 c) Probl`emes dans NP ou dans P . . . . . . . . . . . . . . . . . . . . . . 6 II) R´eduction polynomiale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 b) R´eduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 III) Probl`emes de logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 a) Le probl`eme2-SATest dansP. . . . . . . . . . . . . . . . . . . . . .8 b) Variante du probl`eme 3-SAT : . . . . . . . . . . . . . . . . . . . . . . . 9 c) Le probl`emeMax2SATest NP-complet. . . . . . . . . . . . . . . . .9 d) Le probl`emek-SAT NAEest NP-complet . . . . . . . . . . . . . . . .10 IV) Diff´erentes Variantes du probl`emecycle hamiltonien. . . . . . . . . . . .11 a) Le probl`emeChaine Hamiltonienest NP-complet . . . . . . . . . .11 b) Le probl`emeChaineest NP-complet . . . . . . . . . . . . . . . . . .11 c) Chevaliers de la table ronde . . . . . . . . . . . . . . . . . . . . . . . . 11 d) Le probl`emeVoyageur de Commerceest NP-complet . . . . . . .11 V) Probl`emes de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 a) Les probl`emescoloration de graphe. . . . . . . . . . . . . . . . .13 b) Le probl`eme de la clique maximum. . . . . . . . . . . . . . . . . . . . 14 c) Probl`eme duSet Cover. . . . . . . . . . . . . . . . . . . . . . . . .15 d) Le probl`emeStableest NP-complet . . . . . . . . . . . . . . . . . . .16 VI) Le probl`eme duk-centre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 a) Le probl`emeEnsemble dominantest NP-complet . . . . . . . . . .17 b) Le probl`emek-centreest NP-Complet . . . . . . . . . . . . . . . . .18 c) Le probl`emek-centreest in-approximable . . . . . . . . . . . . . . .18 VII) Probl`emes encodant les entiers . . . . . . . . . . . . . . . . . . . . . . . . . . 19 a) Le probl`emeSOMME DE SOUS-ENSEMBLEest NP-complet . . . .19 b) Le probl`emeSOMME-DES-CARRESest NP-complet . . . . . . . . .19 2

TABLE DES MATI

`ERES3

3 Corrections des exercices 21

I) Probl`eme de d´ecisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
a) Graphe eul´erien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
b) Formulation des probl`emes de d´ecisions . . . . . . . . . . . . . . . . . 22
c) Probl`emes dans NP ou dans P . . . . . . . . . . . . . . . . . . . . . . 23
II) R´eduction polynomiale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
b) R´eduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
III) Probl`emes de logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
a) Le probl`eme2-SATest dansP. . . . . . . . . . . . . . . . . . . . . .27 b) Variante du probl`eme 3-SAT : . . . . . . . . . . . . . . . . . . . . . . . 30
c) Le probl`emeMax2SATest NP-complet. . . . . . . . . . . . . . . . .31 d) Le probl`emek-SAT NAEest NP-complet . . . . . . . . . . . . . . . .33 IV) Diff´erentes Variantes du probl`emecycle hamiltonien. . . . . . . . . . . .34 a) Le probl`emeChaine Hamiltonienest NP-complet . . . . . . . . . .34 b) Le probl`emeChaineest NP-complet . . . . . . . . . . . . . . . . . .35 c) Chevaliers de la table ronde . . . . . . . . . . . . . . . . . . . . . . . . 35
d) Le probl`emeVoyageur de Commerceest NP-complet . . . . . . .36 V) Probl`emes de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
a) Les probl`emescoloration de graphe. . . . . . . . . . . . . . . . .38 b) Le probl`eme de la clique maximum. . . . . . . . . . . . . . . . . . . . 42
c) Probl`eme duSet Cover. . . . . . . . . . . . . . . . . . . . . . . . .43 d) Le probl`emeStableest NP-complet . . . . . . . . . . . . . . . . . . .45 VI) Le probl`eme duk-centre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47 a) Le probl`emeEnsemble dominantest NP-complet . . . . . . . . . .47 b) Le probl`emek-centreest NP-Complet . . . . . . . . . . . . . . . . .48 c) Le probl`emek-centreest in-approximable . . . . . . . . . . . . . . .49 VII) Probl`emes encodant les entiers . . . . . . . . . . . . . . . . . . . . . . . . . . 51
a) Le probl`emeSOMME DE SOUS-ENSEMBLEest NP-complet . . . .51 b) Le probl`emeSOMME-DES-CARRESest NP-complet . . . . . . . . .52

4TABLE DES MATI`ERES

Partie 1: Rappel succinct de cours

Probl`eme de d´ecision.

Unprobl`eme de d´ecisionΠ = (DΠ,OUIΠ) correspond `a un ensemble d"instancesDΠ et `a un sous-ensembleOUIΠ?DΠd"instances positives.Instance du probl`eme Π. OUI

Π.NON

Π.Les classes de complexit´e.

La classePest la classe des probl`emes de d´ecision qui admettent un algorithme de complexit´e polynomiale. La classeNPest form´ee des probl`emes de d´ecision Π qui poss`edent unv´erificateur polynomial.

P ard ´efinitionP?NP.

Un v´erificateurVest un algorithme qui prend une information en plus (certificat) pour v´erifier qu"une instance est positive.

Exemple :Graphe Hamiltonien

Probl `emede d ´ecision: Donn´ees: un graphe non-orient´eG= (V,E).

Question:Ga-il un cycle hamiltonien?

Le certificat corresp ond` aune suite Sde sommets. Le v´erificateurVv´erifie queS est un cycle et qu"il transverse chaque sommet une unique fois.Vfonctionne bien en temps polynomial. -Graphe Hamiltonienest dans NP.

Comment comparer les probl`emes

SoientAetBdeux probl`emes de d´ecision.

1

2CHAPITRE 1. RAPPEL SUCCINCT DE COURS

Uner´eduction deAversBest une fonctionf:IA→IBcalculableen temps polynomial telle quew?Oui(A) si et seulement sif(w)?Oui(B). Pour cela, il suffit de concevoir un algorithme polynomial qui permet de d´ecider si l"ins-

tance deAest positive ou non en temps polynomial :Algorithme 1 :D´ecider si l"instanceIde probl`emeAest positive ou nonOutput :un bool´eenb

d ´ebutTransformer l"instanceIen une instanceI?deBen utilisantf: I ?←f(I) ; siI?est une instance positive deIalorsalorsretournez vrai fin retournez fauxfinInstance du probl`emeAfInstance du probl`emeBAlgorithmeoui non 3

Probl`eme NP-difficile

Intuitivement : il est plus difficile que tous les probl`emes dans la classe. Un probl`emeAest ditNP-completsi en plus on aA?NP. Autrement dit :Aest

Th´eor`eme de Cook-Levin

Les probl`emes SAT et 3-SAT sontNP-complet.

Fonctions bool

´eennes

Nous allons consid´erer des fonctionsbool´eennes, c"est-`a-dire de fonctions deφde{1,0}n→

{1,0}. Les v ariablesne p euventprendre que deux v aleurs,vrai (co d´epar 1) ou faux (co d´e par 0). -φest compos´ee de variables et d"op´erateurs comme n´egation (¬) la conjonction (?) la disjonction (?), l"implication→u v¬u(u?v)u?vu→v0 01001

0 11011

1 00010

1 10111

On dira que la fonctiont:U→ {0,1}satisfaitla fonctionφsi la fonctionφretourne 1 avec les valeurs deten entr´ee. Probl `eme 3- SAT Une clauseest une fonction deφde{1,0}n→ {1,0}compos´ee de variables et d"op´erateurs comme n´egation (¬) et la disjonction (?). Par exempleC(u1,u2,u3) = (u1?u2? ¬u3) est une clause. Le probl`eme3-SATest d´efini de la fa¸con suivante Donn

´ees:

un ensembleUde variables{u1,u2,...,un} et une formule logiqueφ=C1? ··· ?C?des clauses de 3 variables Question: Existe-t-il une fonctiont:U→ {0,1}telle quetsatisfaitφ? Exemple d"instance pour le 3-SATSoitIune instance du probl`eme 3-SAT -U={u1,u2,u3,u4}de variables -φ(U) = (u1? ¬u2?u3)?(¬u1? ¬u3?u4)?(u2? ¬u3? ¬u4),

4CHAPITRE 1. RAPPEL SUCCINCT DE COURS

Remarque :3-SATest dans NP car

Certificat t:

-t=x1x2···xn? {0,1}ndonne la liste de valeurs de chaque variable.

V ´erification:

V ´erifierque trend la formuleFvraie se fait bien en un temps polynomial en la taille deF.

Comment prouver qu"un probl`eme est NP-complet

Pour prouver laNP-compl´etude d"un probl`emeA, il suffit de prouver : 1. qu"il admet un v ´erificateurp olynomial; 2.

Pourquoi?

Si Aadmet un v´erificateur polynomial, cela permet de garantir queA?NP, tout probl`emeC?NP

Une liste de probl`emes NP-complets connusSAT3-SATVC4-SAT NAECycle HamiltonienChaine Hamiltonienne3-SAT NAECliqueDominant2-partitionStableSomme de sous-ensemble

Partie 2: Enonc´es des exercices

5

6CHAPITRE 2. ENONC´ES DES EXERCICES

I)

Probl `emede d ´ecisions

a)

Graphe eul ´erien

Le grapheGesteul´eriensi il existe un cycle en empruntant exactement une fois chaque arˆete du grapheG. On rappelle qu"un graphe connexe est eul´erien si et seulement si chacun de ses sommets a un degr´e pair.

Question 1.1. Ecrire le probl`eme de d´ecision qui lui est associ´e et donner la taille de l"instance

Question 1.2. Trouver un algorithme polynomial qui d´etermine si le graphe est eul´erien. b)

F ormulationdes probl `emesde d ´ecisions

Mettre sous forme de probl`eme de d´ecision et ´evaluer la taille de leurs instances. Question 2.1. Probl`eme de savoir s"il existe un chemin entre deux sommets disjoints dans un graphe; Question 2.2. Probl`eme de connaitre la distance entre deux sommets disjoints dans un graphe; Question 2.3. Probl`eme de connaitre la longueur de la chaˆıne maximum dans un graphe pond´er´e. c)

Probl `emesdans NP ou dans P

Les probl`emes suivants sont-ils dans NP, dans P? Justifier votre r´eponse. Probl `emeP1 Donn

´ees: Un grapheG= (V,E)

Question: Existe-t-il cycle de longueur ´egale `a?|V|2 Probl `emeP2 Donn

´ees: Un grapheG= (V,E)

Question: Existe-t-il cycle de longueur ´egale `a 4? Probl `emeP3 Donn ´ees: Un grapheG= (V,E), deux sommetsuetvdistincts deGet un entierk. Question: Existe-t-il un simple chemin entreuetvde longueur inf´erieure ou ´egale `ak? Probl `emeP4 Donn

´ees: Un grapheG= (V,E), et un entierk.

Question: Existe-t-il un arbre couvrant tous les sommets deGayant moins dekfeuilles?

II). R

´EDUCTION POLYNOMIALE.7

II)

R ´eductionp olynomiale.

a)

SoientAetBdeux probl`emes de d´ecision.

Uner´eduction deAversBest une fonctionf:IA→IBcalculableen temps polynomial telle quew?Oui(A) si et seulement sif(w)?Oui(B). Question 4.3. Montrer queP=NPsi et seulement si 3-SAT?P. b)

R ´eduction

SoientA, BetQdes probl`emes de d´ecision. Supposons queAest dansP, et queBest NP-dur. Dire si les affirmations suivantes sont vraies ou fausses : 1. Si Ase r´eduit polynˆomialement `aQ, alorsQest dansP. 2. Si Qse r´eduit polynˆomialement `aA, alorsQest dansP. 3. Si Qse r´eduit polynˆomialement `aB, alorsQestNP-dur. 4. Si Bse r´eduit polynˆomialement `aQ, alorsQestNP-dur.

8CHAPITRE 2. ENONC´ES DES EXERCICES

III)

Probl `emesde logique

a)

Le probl `eme2-SA Test dans P

Nous allons consid´erer de cet exercice des fonctionsbool´eennes, c"est-`a-dire de fonctions defde{1,0}n→ {1,0}. Les v ariablesne p euventprendre qu edeux v aleurs,vrai (co d´epar 1) ou faux (co d´e par 0). La f onctionb ool´eennefest compos´ee de variables et d"op´erateurs comme n´egation (¬) la conjonction (?) la disjonction (?), l"implication→.

Voici la table de v´erit´e pour les op´erateurs bool´eens cit´es ci-dessus :u v¬u(u?v)u?vu→v0 01001

0 11011

1 00010

1 10111

Consid´erons une fonctiont:U→ {0,1}. On dira que la fonctiontsatisfait la fonctionf si la fonctionfretourne 1 avec les valeurs deten entr´ee. Question 6.1. Nous allons consid´erer la fonctionφ1: telle que{1,0}3→ {1,0}.

1(x,y,z) = (y? ¬z)?(¬y?z)?(y? ¬x).

Donner une fonctiont:U→ {0,1}telle quetsatisfaitφ1

Question 6.2. Que se passe-t-il pourφ2

2(x,y,z) = (y?z)?(¬y?z)?(¬z?x)?(¬z? ¬x)?

Une clause est une fonction defde{1,0}n→ {1,0}compos´ee de variables et d"op´erateurs comme n´egation (¬) et la disjonction (?). Par exempleC(u2,u3) = (u2?¬u3) est une clause.

Donnons la d´efinition du probl`eme 2-SAT

Donn´ees: un ensembleUde variables{u1,u2,...,un}et une formule logiqueφ=C1?···?C? des clauses de 2 litt´eraux Question: Existe-t-il une fonctiont:U→ {0,1}telle quetsatisfaitφ? Question 6.3. Montrer queu?v= (¬u?v)?(¬v?u). A partir d"une instance (U,φ) de 2-SAT, nous construisons un graphe orient´eGφ= (V,E) tel que un s ommetpar un litt ´eralde U un arc par implication (en transforman tc haqueclause par deux implications)

Question 6.4. Dessiner les graphesGφ1etGφ2

Question 6.5. Montrer que siGφposs`ede un chemin entreuetv, alors il poss`ede aussi un chemin entre¬vet¬u Question 6.6. Montrer qu"il existe une variableudeUtel queGφcontient un cycle entreu vers¬usi et seulement siφn"est pas satisfiable.

III). PROBL

`EMES DE LOGIQUE9 Question 6.7. Montrer que un algorithme en temps polynomial peut r´esoudre le probl`eme

2-SAT.

Rappellons la d´efinition du probl`eme : 3-SAT

Donn´ees: Un ensembleUde variables, et une formuleFsous la forme d"une conjonction de disjonction de 3 litt´eraux (variables ou leur n´egation). Formellement : une formule

F=C1?C2··· ?C?

avec C i=yi,1?yi,2?yi,3, o`u pour touti,j,yi,jest soitxk, soit¬xkpour l"un desxk, pour des variables{x1,···,xn}

Question:D´ecider siFest satisfiable : c"est-`a-dire d´ecider s"il existex1,···,xn? {0,1}tel

queFs"´evalue `a vrai pour cette valeur de ses variablesx1,···,xn. b)

V ariantedu probl `eme3-SA T:

Donn ´ee:Une form uleF?sous la forme d"une conjonction de clauses mˆeme si chaque variable apparaisseau plus soit trois foisdansFsous sa forme n´egative ou positive. R

´eponse:D ´ecidersi F?est satisfiable.

Question 7.1. Soitx1,x2...xk, Consid´erons une formuleφpar l"ensemble dekclauses (xi? ¬xi+1) pouri= 1,...k-1, et de la clause (xk? ¬x1). Montrer que une assignationφ est satisfaite si et seulement si pouri= 1,...k-1xk=x1 Question 7.2. Prouver que ce probl`eme est dans NP. Question 7.3. Prouver que ce probl`eme est NP-complet `a partir d"une r´eduction du probl`eme

3-SAT.

Question 7.4. Prouver 3-SATest NP-complet mˆeme si chaque variable apparaisseexac- tement trois foisdansFsous sa forme n´egative ou positive. Question 7.5. Prouver 3-SATest NP-complet mˆeme si chaque variable apparaissedeux foissous sa forme positive etune foissous sa forme n´egative dansF. c)

Le probl `emeMax2SATest NP-complet.

L"objectif de cet exercice est de prouver que le probl`emeMax2SATest NP-complet. Donn ´ee:Une form uleF?sous la forme d"une conjonction de clauses d"au plus 2 litt´eraux, un entierK R ´eponse:D ´eciders"il existe une assignation x1,···,xn? {0,1}telle que au moins Kclauses deF?sont satisfaites. s"´evalue `a vrai pour cette valeur de ses variables x

1,···,xn.

Question 8.1. Soit une clauseC=x?y?z. Nous construisons une formuleφCsous la forme d"une conjonction de 10 clauses en introduisant un nouveau litt´eralpC:

C=(x)?(y)?(z)?(pC)

(¬x? ¬y)?(¬y? ¬z)?(¬z? ¬x) (x? ¬pC)?(y? ¬pC)?(z? ¬pC) D´eterminer le nombre maximun de clauses satisfaites dans le cas o`u 1. la clause Cest satisfaite

10CHAPITRE 2. ENONC´ES DES EXERCICES

2. la clause Cn"est pas satisfaite Question 8.2. Prouver que le probl`emeMax2SATest dans NP. Question 8.3. Montrer que le probl`eme Max2SAT est NP-complet. d)

Le probl `emek-SAT NAEest NP-complet

Consid´erez le probl`eme suivant :

k-SAT NAE Donn´ees: un ensembleU?de variables{u1,u2,...,un}et une formule logiqueL=C1?···?C?

avecCi= (yi,1?yi,2? ··· ?yi,k) o`uyi,jest ´egal soit `a l"un desukou soit `a l"un des¬uk

Question: Existe-t-il une fonctiont:U?→ {0,1}telle quetsatisfaitLet telle que les litt´eraux de chaque clause ne sont pas toutes de la mˆeme valeur? Question 9.1. Montrer que 4-SAT NAEest NP-complet sachant que 3-SATest NP-complet. Indication : Introduire une nouvelle variablezet l"ins´erer dans toutes les clauses Question 9.2. Montrer que 3-SAT NAEest NP-complet sachant que 4-SAT NAEest NP- complet. 3-SATest NP-complet.Indication : Utiliser la technique pour la transformation de

SAT en 3-SAT.

IV). DIFF

´ERENTES VARIANTES DU PROBL`EMECYCLE HAMILTONIEN11 IV) Diff ´erentesV ariantesdu probl `emecycle hamiltonien Nous allons supposer que le probl`emeCycle Hamiltonienest NP-Complet.

Cycle Hamiltonien

Donn´ees: un graphe non-orient´eG.

Question:Gcontient-il un cycle hamiltonien?

a)

Le probl `emeChaine Hamiltonienest NP-complet

Consid´erons le probl`emeChaine Hamiltoniensuivant :

Chaine Hamiltonienne

Donn´ees: un graphe non-orient´eG, deux sommetsuetvdistincts deG. Question:Gcontient-il une chaine hamiltonienne entreuetv? Question 10.1. Montrer que le probl`emeChaine Hamiltonienest dans NP. Question 10.2. Montrer que le probl`emeChaine Hamiltonienest NP-complet. Pour cela, nous allons faire la r´eduction `a partir du probl`emecycle hamiltonien. Soit I=< G= (V,E)>une instance du probl`emeCycle hamiltonien. Maintenant, nous allons transformer cette instance en une instanceI?du probl`emeChaine Hamiltoniennede la fa¸con suivante : Nous allons construire un grapheG?= (V?,E?) tel que

Soit uun sommet arbitraire deV

-V?:=V? {v}tel quevest un sommet n"appartenant pas dansV -E?:=E? {(v,?) :?est un voisin deudansG}

Continuez la preuve.

b)

Le probl `emeChaineest NP-complet

Le probl`emeChaineest le probl`eme de d´ecision suivant

Chaine

Donn´ees: un graphe non-orient´eGdensommets, deux sommetsuetvdistincts deG. Question:Gcontient-il une chaine de longueurn/2 entreuetv? Question 11.1. Montrer que le probl`emeChaineest dans NP. Question 11.2. Montrer que le probl`emeChaineest NP-complet. c)

Chev aliersde la table ronde

Etant donn´esnchevaliers, et connaissant toutes les paires de f´eroces ennemis parmi eux, est-il possible de les placer autour d"une table circulaire de telle sorte qu"aucune paire de f´eroces ennemis ne soit cˆote `a cˆote? d)

Le probl `emeVoyageur de Commerceest NP-complet

Consid´erez le probl`emeVoyageur de Commerce:

Donn´ees: Un graphe completGmuni d"une fonctiondde coˆut positif sur les arˆetes, et un entierk.

12CHAPITRE 2. ENONC´ES DES EXERCICES

Question: Existe-t-il un circuit passant au moins une fois par chaque ville et dont la somme des coˆuts des arˆetes est au plusk? Question 13.1. Montrer queVoyageur de Commerceest NP-complet mˆeme si la fonction

poids respecte l"in´egalit´e triangulaire. (C"est-`a-dire que si les arˆetes v´erifient l"in´egalit´e trian-

Question 13.2. Montrer que le probl`eme du voyageur de commerce ayant une m´etrique respectant l"in´egalit´e triangulaire est dans NP-complet.

V). PROBL

`EMES DE GRAPHE13 V)

Probl `emesde graphe

a)

Les probl `emescoloration de graphe

Unecolorationd"un grapheGest une fonction associant `a tout sommetVdu grapheG un entier repr´esentant une couleur dans [1,...,|V|], telle que deux sommets adjacents n"aient pas la mˆeme couleur. Le probl`eme d"optimisation classique est de trouver une coloration avec un nombre de couleurs minimum. Question 14.1. Donner un algorithme polynomial construisant une coloration d"un arbre

T= (VT,ET) qui utilise seulement 2 couleurs.

Question 14.2. Le probl`emek-Arbre-colorationest-il NP-complet ou dans P? Probl `emek-Arbre-coloration Donn

´ees: Un arbreT= (V,E) et un entierk.

Question: Existe-t"il une fa¸con de colorier les sommets deTavec au pluskcouleurs de telle sorte qu"aucune arˆete n"ait les extr´emit´es de la mˆeme couleur?

D´efinissons le probl`emek-coloration.

Probl `emek-coloration Entr

´ee: Un grapheG= (V,E), un entierk

Question: Existe-t-il une coloration propre des sommets utilisant moins dekcou- leurs? Question 14.3. Le probl`eme 2-coloration est-il NP-complet ou dans P? Justifier votre r´eponse. A partir de maintenant, nous supposerons que le probl`eme3-colorationest NP-complet. Question 14.4. Montrer que le probl`eme4-colorationest NP-complet.

Consid´erons le grapheH:

a c b a c a c xx001 a cb Question 14.5. Montrer que ce graphe ne poss`ede pas de coloration propre du graphe utili- sant au plus 2 couleurs. Question 14.6. Montrer que dans toute coloration propre du graphe utilisant au plus 3 couleurs,a,betcont la mˆeme couleur. Soitxun entier strictement positif. Consid´erons le grapheHxsuivant : a c b a c a c xx001

Partie 3: Corrections des exercices

21

22CHAPITRE 3. CORRECTIONS DES EXERCICES

I)

Probl `emede d ´ecisions

a)

Graphe eul ´erien

Le grapheGesteul´eriensi il existe un cycle en empruntant exactement une fois chaque arˆete du grapheG. On rappelle qu"un graphe connexe est eul´erien si et seulement si chacun de ses sommets a un degr´e pair.

Question 1.1. Ecrire le probl`eme de d´ecision qui lui est associ´e et donner la taille de l"instanceCorrection

Donn

´ees: un grapheGQuestion: Existe-t-il un cycle eul´erien dansG?La taille de l"instance estO(|V|2)car il faut co derle graphe ( O(|V|2)). En effet, sile graphe est repr´esent´e par la matrice d"adjacence, alors il n´ecessiteO(|V|2) bits pourcoder un graphe. Sinon, si le graphe est repr´esent´e par liste d"adjacence alors pour coder

le graphe complet, il n´ecessiteO(|V|2log|V|) bits pour le coder ce graphe (car le graphecomplet poss`edeO(|V|2) arˆetes, et pour coder un nombre entier (´etiquette du sommet)entre 0 etn-1, il fautO(log|V|) bits).2Question 1.2. Trouver un algorithme polynomial qui d´etermine si le graphe est eul´erien.Correction

Entr

´ee: un grapheGSortie: un bool´eenb1.b←True;// O(1) op´erations2.P ourtout sommet vfaire// la boucle est ex´ecut´eeO(|V|)fois(a)Calculer le de gr´ede v;//O(|V|)op´erations au pire(b)Si le degr ´ede vest impair alorsb←False;// O(1) op´erations3.Retourner b;// O(1) op´erationsComplexit´e :O(|V|2) op´erations2

b)

F ormulationdes probl `emesde d ´ecisions

Mettre sous forme de probl`eme de d´ecision et ´evaluer la taille de leurs instances. Question 2.1. Probl`eme de savoir s"il existe un chemin entre deux sommets disjoints dans un graphe;Correction Voici le probl`eme sous forme de probl`eme de d´ecision : Donnquotesdbs_dbs35.pdfusesText_40

[PDF] développement limité fonction plusieurs variables

[PDF] recherche opérationnelle exercices corrigés gratuit

[PDF] programmation linéaire exercices corrigés simplex

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule

[PDF] multiplicateur des dépenses publiques macroéconomie