NP-complétude du Cycle Hamiltonien et Extensions

Définitions de Base

Cycle Hamiltonien (CH): Étant donné un graphe G = (V, E), existe-t-il un cycle passant par chaque sommet exactement une fois et revenant au point de départ ?

Problème du Voyageur de Commerce (TSP): Étant donné un ensemble de villes et les distances entre chaque paire de villes, trouver le chemin le plus court qui visite chaque ville exactement une fois et revient à la ville de départ.

1. Preuve de NP‑complétude du Cycle Hamiltonien (sans contraintes)

Étape 1 : CH ∈ NP

Un certificat est un cycle passant par tous les sommets. La vérification consiste à s'assurer que chaque sommet apparaît exactement une fois, que toutes les arêtes du cycle existent dans le graphe, et que le cycle est fermé. Cette vérification peut être effectuée en temps polynomial (O(|V|)).

Étape 2 : NP‑difficulté par réduction du TSP

Soit une instance du TSP avec n villes et une matrice de distances D, où D[i,j] représente la distance entre les villes i et j.

Objectif : Construire un graphe G(TSP) tel que le TSP a une solution de coût total ≤ k si et seulement si G(TSP) possède un cycle Hamiltonien.

Construction :

Sommets : Créons un graphe G = (V, E) avec |V| = n sommets, chaque sommet correspondant à une ville du TSP.
Arêtes : Pour chaque paire de villes (i, j) avec une distance D[i,j] ≤ k (où k est un seuil donné), ajoutons une arête entre les sommets correspondants dans G.
Le graphe G ainsi construit représente toutes les connexions possibles qui respectent la contrainte de distance maximale k.

Théorème : L'instance du TSP a une solution de coût total ≤ k si et seulement si le graphe G contient un cycle hamiltonien.

Preuve :

(⇒) Si le TSP a une solution de coût ≤ k, alors cette solution visite toutes les villes exactement une fois. Par construction, toutes les arêtes de ce cycle existent dans G (puisque nous avons ajouté une arête pour chaque paire de villes avec distance ≤ k). Donc G contient un cycle hamiltonien.
(⇐) Si G contient un cycle hamiltonien, alors ce cycle passe par tous les sommets exactement une fois. Par construction, chaque arête de G correspond à une paire de villes avec distance ≤ k. Donc, le coût total du trajet correspondant dans l'instance du TSP est ≤ k.

Cette réduction est effectuée en temps polynomial (O(n²)) par rapport à la taille de l'instance du TSP.

Conclusion :

Le Cycle Hamiltonien est NP‑complet puisque (i) il est dans NP et (ii) le problème du TSP, qui est NP-difficile, se réduit en temps polynomial au CH.

2. Extension aux Contraintes Supplémentaires

2.1 Cycle Hamiltonien Pondéré (CHP)

Définition: Donné G = (V, E) muni d'une fonction de poids w : E → ℝ⁺, existe-t-il un cycle hamiltonien de poids minimal ?

CHP ∈ NP : Pour un certificat (le cycle), on vérifie en temps polynomial que la somme des poids est conforme au critère d'optimalité ou simplement que le cycle existe.

Réduction : La réduction est directe depuis le TSP : les poids des arêtes dans le CHP correspondent aux distances entre les villes dans le TSP. Par conséquent, le TSP se réduit en temps polynomial à CHP.

3. Remarques et Applications

3.1 Planification d'itinéraires pour véhicules électriques

• Les sommets représentent des villes à visiter

• Les poids sont les distances ou coûts de trajet

• Les stations de recharge sont un sous-ensemble des villes

• L'autonomie correspond à la distance maximale entre recharges

3.2 Approches de résolution

Méthodes exactes:

• Programmation par contraintes

• Branch-and-cut avec solveurs PLNE

Heuristiques:

• Algorithmes génétiques avec pénalités pour violations d'autonomie

• Recherche locale avec contraintes (2-opt modifié)

• Optimisation par colonies de fourmis avec phéromones guidant vers les stations

2.2 Cycle Hamiltonien avec Contrainte d'Autonomie (CHA)

Définition : Pour un graphe G = (V, E) muni d'un sous-ensemble R ⊆ V représentant des stations de recharge et une autonomie k ∈ ℕ, on exige que tout chemin continu de plus de k arêtes contienne au moins un sommet dans R.

CHA ∈ NP : Un certificat (le cycle) peut être vérifié en temps polynomial en contrôlant l'ordre de passage des sommets et la présence régulière d'un sommet de recharge.

Réduction : À partir d'une instance du TSP, on peut créer une instance du CHA en :

Identifiant certaines villes comme des stations de recharge (R)
Fixant une autonomie k qui représente la distance maximale pouvant être parcourue entre deux recharges

Si l'on fixe k suffisamment grand (par exemple, k ≥ n) ou si l'on définit R = V, le problème devient équivalent au Cycle Hamiltonien classique. Ainsi, le TSP se réduit en temps polynomial au CHA.

2.3 Combinaison : Cycle Hamiltonien avec Pondération et Contrainte d'Autonomie (CHPA)

Pour un problème combiné, les arguments précédents se recoupent :

En partant d'une instance du TSP, on peut définir les poids des arêtes comme les distances entre les villes.
On peut également désigner certaines villes comme des stations de recharge et définir une autonomie k représentant la distance maximale pouvant être parcourue sans recharge.
La vérification d'un certificat et la construction de la réduction se font en temps polynomial.

Ainsi, CHPA est NP‑complet.

NP-complétude du Cycle Hamiltonien et Extensions avec Contraintes