Attention : pour ce qui suit, je tappe au kilomètre. Si vous voyez des erreurs prévenez moi.

Exercice 3 :Chemin et circuit hamiltonien

En utilisant le fait que le problème du chemin hamiltonnien est NPcomplet, prouvez que le problème du circuit hamiltonnien est lui aussi NP-Complet.

Exercice 3 : Eléments de solutions

Circuit hamiltonnien est un problème de NP

Dire que le problème du chemin hamiltonnien est NP-complet implique que le problème du chemin hamiltonnien est NP. Donc il existe un algorithme V erifChHam de complexité polynômiale que l’on peut spécifier comme suit : Algorithme V erifChHam Données :

G = (X,E) : Un graphe ayant au moins un sommet ;

L : Une liste de sommets de G ; Résultat : rep : un boléen ; /* Spécification : Cet algorithme renvoie Vrai dans la variable rep si et seulement si L décrit un chemin hamiltonien du graphe G. C’est à dire que L est un chemin élémentaire de G passant par tous les sommets du graphe G*/

Dire que cet algorithme est polynômial signifie qu’il existe un polynôme P (x) tel que quel que soit la donnée (G,L) de notre algorithme V erifChHam le nombre d’opérations effectuées par V erifChHam(G, L, rep) est majoré par P (|G|).

Nous allons donc maintenant écrire un algorithme permettant de vérifier un circuit hamiltonnien.

Algorithme V erifCircuitHam Données :

G = (X,E) : Un graphe ayant au moins un sommet ;

L : Une liste de sommets de G ; Résultat : rep : un boléen ; /* Spécifications :

L est une liste de sommets telle que le premier élément de la liste est égal au dernier, de plus, |L| ≥ 2. Cette spécification permet d’imposer la façon dont est décrit le circuit.

Cet algorithme renvoie Vrai dans la variable rep si et seulement si L décrit un circuit hamiltonien du graphe G. C’est à dire que L est un circuit élémentaire (seul le premier élément est répété deux fois) de G passant par tous les sommets du graphe G*/ Variables :

L’ : une liste de sommets de G

x,y : sommets de G

b : boléen ; DébutCode x ← P remier(L) ; Si |L| ≤ |X|+ 1 alors

L′ ← Suite(L) ;

y ← P remier(L′) ;

V erifChHam(G, L′, b)

rep ← b ∧ ((x, y) ∈ E) ; Sinon rep ← F aux FinSi FinCode Tout d’abord il faut remarqué que si L décrit un chemin hamiltonien alors en retirant le premier élément de la liste (il est égal au dernier élément par spécification), on obtient un chemin hamiltonnien de plus si L décrit un chemin hamiltonien alors lepremier élément de la liste L est relié au second élémént de la liste L.

Donc Si L décrit un circuit hamiltonnien, alors rep sera vrai.

Réciproquement, supposons que rep soit vrai, alors L’ est un chemin hamiltonnien et le premier élément de L est relié au second élément de L. Or par spécification, le premier élément de L est égal au dernier élément de L donc le dernier élément de L’ est relier au premier élément de L’, donc L est un circuit Hamiltonnien.

Complexité : x ← P remier(L) ; Coûte 1 opération Le test s’effectue en au plus |X|+1 (< 2|G|) opérations Partie Si : On a |L| ≤ |X|+ 1 L′ ← Suite(L) ; Coûte au plus |X| opérations (représentation par un tableau) y ← P remier(L′) ; Coûte 1 opération V erifChHam(G, L′, b) Coûte au plus P (|G|) (P estun polynôme). rep ← b ∧ ((x, y) ∈ E) ;Coûte au plus |E| < |G| opérations

Chaque opération est polynômiale dans la taille de |G|. La complexité de notre algorithme est donc une somme finie de polynôme est donc un polynôme.

Transformation de chemin hamiltonnien vers circuit hammiltonnien

Idée : Soit G = (X,E) un graphe ayant un chemin hamiltonnien ChH. Soit y un sommet qui n’est pas présent dans X. On crée le graphe G’=(X’,E’) de la façon suivante :

1. X’ = X ∪ {y} ;

2. E’ = E ∪ {(u,v) ∈ X’^{2} | u ≠ v et (u = y ou v = y)}.

Propriétés de la transformation

Si ChH = x_{0}, x_{1}, …, x_{k} est un chemin hamiltonient de G alors c’est un chemin de G′ puisque E ⊂ E′. De plus par construction, (x_{k}, y) ∈ E′ et (y, x_{0}) ∈ E′. Donc CiH’ = y, x_{0}, x_{1}, …, x_{k}, y est un circuit hamiltonnien de G’.

Si ciH’ =t_{0}, t_{1}, …, t_{k+1}, t_{0} est un circuit hamiltonien de G′ alors il existe un indice q tel que t_{q} = y, posons :

μ = t_{q+1}, t_{q+2}, …, t_{k+1}, t_{0}, t_{1}, …, t_{q−1}

On peut faire les remarques suivantes :

1. y n’est pas présent dans μ

2. μ est un chemin élémentaire de G′

3. μ est un chemin élémentaire de G (car chemin élémentaire de G’ ne contenant pas y).

4. μ contient |X| sommet. Donc μ est un chemin hamiltonien de G.

Il ne nous reste plus qu’à écrire formellement la transformation puis à calculer sa complexité/

Algorithme ChHam2CiHam Donnée : G = (X,E) un graphe ; Résultat : G’ = (X’,E’) un graphe ; Variable : y un sommet ; /*Spécification : Voir ci-dessus*/ DébutCode Chercher y un sommet qui n’est pas présent dans X ; X’ ← X ∪ {y} ; E’ ← E ; Pour chaque sommet x de X faire

Inserer (x,y) dans E’ ;

Inserer (y,x) dans E’ ; FinPour FinCode Complexité : Chercher y un sommet qui n’est pas présent dans X ; Coûte au plus |X| opérations (|X|^{2} si vous n’êtes pas doués) X’ ← X ∪ {y} ; Coûte au plus |X|+1 opérations(< 2|G|) E’ ← E ; Coûte au plus |G| opérations Inserer (x,y) dans E’ ; Coûte 1 opération réalisée |X| fois Inserer (y,x) dans E’ ; Coûte 1 opération réalisée |X| fois Coût de la boucle < 2|G|

le coût de notre algorithme est donc inférieur à 5|G| il est donc polynomial. De plus, compte tenu des propriété de la transformation vues plus haut,

nous povons affirmer que G possède un chemin hamiltonien si et seulement si G′ possède un circuit hamiltonnien.

Le problème est donc NP-Complet.

Exercice 4 : Problème du voyageur de commerce

Nom : Voyageur de commerce Données :

G = (X,E,V) Un graphe complet valué par des entiers

k : un entier Question : Existe-t-il un chemin hamiltonnien de poids inférieur ou égal à k ?

Prouvez que le Problème du voyageur de commerce est un problème NP-Complet.

Exercice 4 : Eléments de solution

Voyageur de commerce est dans NP

Nous allons donc écrire un algorithme permettant de vérifier un solution. On prend une opération ieme(i, L) qui renvoie le ième élément de la liste L. Cout : O(i). Le premier élément de la liste a le numéro 1. Algorithme VerifVC Données :

G=(X,E,V) : Un graphe complet valué par des entiers

k : un entier ;

L : une liste de sommets ; Résultat : rep : booléen ; /*Spécification :

L est une liste de sommets telle que le premier élément de la liste est égal au dernier, de plus, |L| ≥ 2. Cette spécification permet d’imposer la façon dont est décrit le circuit.

Cet algorithme renvoie Vrai dans la variable rep si et seulement si L décrit un circuit hamiltonien du graphe G dont le poids est inférieur ou égal à k.*/ Variable :

G’=(X’,E’) un graphe ayant au moins un sommet ;

n,i un entier ;

x,y : sommets

b : booléen ; DébutCode X′ ← X; E′ ← E; V erifCircuitHam(G′, L, b) ; i ← 2 ; n ← 0 ; Si b alors

x ← ieme(1, L)

Pour i variant de 2 à |L| faire y ← ieme(i, L) ; i ← i + 1 ; n ← n + V (x, y) ; x ← y;

FinPour

y ← ieme(1, L) ; n ← n + V (x, y) ;

b ← (n ≤ k) FinSi rep ← b Fincode Dans la boucle n nous sert à calculer le poids du circuit. Nous avons auparavant vérifié que nous somme bien en présence d’un circuit hamiltonien par l’appel de VerifCircuitHam.

La complexité de VerifCircuitHam est polynômiale par rapport à la taille de G’ or la taille de G’ est inférieure ou égale à la taille de G. Donc, la complexité de VerifCircuitHam est polynômiale par rapport à la taille de G.

Complexité de la boucle : est majorée 2|L|^{2} < 2|G|^{2}

Les autres opérations coûte au plus |G|. La complexité de notre algorithme peut donc être majoré par une somme finie de polynôme. Elle est donc polynômiale.

Choix du problème NP-Complet

Nopus allons choisir CiruitHamiltonien de l’exercice précédent.

La Transformation

Idées : Il faut transformer un graphe quelconque en un graphe complet valué et un entier k. Soit G=(X,E) un graphe nous allons lui associé un graphe valué G’=(X’,E’,V’) de la manière suivante :

1. X’ = X

2. E’ = X × X (ensemble de tous les couples d’éléments de X)

3. V’ : Un matrice carrée indicée par X × X telle que V’(x,y) = 1 si

(x, y) ∈ E et V’(x,y) = 2 si (x, y) ∉ E; Il faut aussi un entier posons k = |X|

Remarques sur la transformations : Si Ci = x_{0}, x_{1}, … x_{u}, x_{0} est un circuit hamiltonien de G, c’est aussi un circuit hamiltonien de G′ car E ⊂ E′. De plus puisque ce circuit n’utilise que des arêtes présentes dans G leur poids dans G’ est 1. Ce circuit utilise |X| arêtes donc le poids de Ci dans G′ est exactement |X|.

Réciproquement si Ci′ = x_{0}, x_{1}, … x_{u}, x_{0} est un circuit hamiltonien de G’ alors il contient |X| sommets distincts et passe par |X| arêtes. Donc chaque arête à un poids unitaire, donc chaque arête est présente dans G. Donc, Ci′ = x_{0}, x_{1}, … x_{u}, x_{0} est un circuit hamiltonien de G.

Ecrivons l’algorithme : Algorithme CiH2VC Donnée : G = (X,E) Un graphe ; Résultat : G’ = (X’,E’,V’) un graphe complet valué (V est une matrice d’entier) ; /*Spécification : Voir ci-dessus*/ Variables : x,y : sommets DébutCode X′ → X; /*coût |X|≤|G|*/ E′ → ∅ /*coût au plus |X|^{2} ≤|G|^{2}*/ k → |X|; /*coût |X|≤|G|*/ Pour tout x dans X

Pour tout y dans X Inserer (x,y) dans E’ ; /* Coût 1, fait |X|^{2} fois*/ V (x, y) ← 2 ; /* Coût 1, fait |X|^{2} fois*/

Finpour FinPour Pour tout (x,y) dans E faire

V (x, y) ← 1 ; /* Coût 1, fait |E| fois*/ FinPour FinCode On vérifie aisément que cette transformation coûte moins que 6|G|^{2}, elle est donc polynômiale. De plus compte tenu des remarque faites auparavant, G contient un circuit hamiltonnien si et seulement si G’ contient un circuit hamiltonnien de poids k = |X|.

Le problème est donc NP-Complet.