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 NP-
complet, 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 erif ChHam de complexité polynômiale que l'on peut spéci er comme suit :
Algorithme V erif ChHam
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éci cation : Cet algorithme renvoie Vrai dans la variable rep si et seule-
ment 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 signi e qu'il existe un polynôme
P (x) tel que quel que soit la donnée (G,L) de notre algorithme V erif ChHam
le nombre d'opérations eectuées par V erif ChHam(G, L, rep) est majoré
par P (|G|).
Nous allons donc maintenant écrire un algorithme permettant de véri er
un circuit hamiltonnien.
Algorithme V erif CircuitHam
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éci cations :
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éci cation permet d'imposer la façon
dont est décrit le circuit.
1
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
L0 ← Suite(L) ;
y ← P remier(L0 ) ;
V erif ChHam(G, L0 , 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éci cation), 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 ha-
miltonnien et le premier élément de L est relié au second élément de L. Or
par spéci cation, 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'eectue en au plus |X|+1 (< 2|G|) opérations
Partie Si : On a |L| ≤ |X|+ 1 L0 ← Suite(L) ; Coûte au plus |X| opérations
(représentation par un tableau)
y ← P remier(L0 ) ; Coûte 1 opération
V erif ChHam(G, L0 , 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 nie de polynôme est donc un
polynôme.
2
Transformation de chemin hamiltonnien vers circuit ham-
miltonnien
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 6= v et (u = y ou v = y)}.
Propriétés de la transformation
Si ChH = x0 , x1 , . . . , xk est un chemin hamiltonient de G alors c'est un
chemin de G0 puisque E ⊂ E 0 . De plus par construction, (xk , y) ∈ E 0 et
(y, x0 ) ∈ E 0 . Donc CiH' = y, x0 , x1 , . . . , xk , y est un circuit hamiltonnien de
G'.
Si ciH' =t0 , t1 , . . . , tk+1 , t0 est un circuit hamiltonien de G0 alors il existe
un indice q tel que tq = y , posons :
µ = tq+1 , tq+2 , . . . , tk+1 , t0 , t1 , . . . , tq−1
On peut faire les remarques suivantes :
1. y n'est pas présent dans µ
2. µ est un chemin élémentaire de G0
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éci cation : 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' ;
3
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 a rmer que G possède un chemin hamiltonien si et seulement
si G0 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éri er 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éci cation :
4
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éci cation 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 0 ← X ; E0 ← E ;
V erif CircuitHam(G0 , 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 aupa-
ravant véri é 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 algo-
rithme peut donc être majoré par une somme nie de polynôme. Elle est
donc polynômiale.
Choix du problème NP-Complet
Nopus allons choisir CiruitHamiltonien de l'exercice précédent.
5
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) 6∈ E ;
Il faut aussi un entier posons k = |X|
Remarques sur la transformations : Si Ci = x0 , x1 , . . . xu , x0 est un circuit
hamiltonien de G, c'est aussi un circuit hamiltonien de G0 car E ⊂ E 0 . 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 G0 est
exactement |X|.
Réciproquement si Ci0 = x0 , x1 , . . . xu , x0 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,
Ci0 = x0 , x1 , . . . xu , x0 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'en-
tier) ;
/*Spéci cation : Voir ci-dessus*/
Variables : x,y : sommets
DébutCode
X 0 → X ; /*coût |X|≤|G|*/
E 0 → ∅ /*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
6
On véri e 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.