Théorie des Graphes : Problèmes NP-complets

Exploration interactive de la coloration, des cycles eulériens et hamiltoniens

Introduction

La théorie des graphes nous offre des outils puissants pour modéliser et résoudre des problèmes complexes. Cet outil interactif explore trois problèmes fondamentaux :

Coloration de Graphe

Attribution de couleurs aux sommets d'un graphe de sorte que deux sommets adjacents n'aient jamais la même couleur. Un problème classique avec des applications pratiques comme l'allocation de ressources.

Cycle Eulérien

Recherche d'un cycle passant une et une seule fois par chaque arête du graphe. Ce problème, inspiré des ponts de Königsberg, est résolvable en temps polynomial.

Cycle Hamiltonien

Recherche d'un cycle passant une et une seule fois par chaque sommet du graphe. Un problème NP-complet, proche du célèbre problème du voyageur de commerce.

Points clés

Ces trois problèmes illustrent parfaitement la diversité de la complexité en théorie des graphes :

  • Le cycle eulérien est résolvable efficacement (temps polynomial)
  • La coloration et le cycle hamiltonien sont NP-complets
  • Chacun nécessite des approches et des structures de données différentes

À travers cet outil interactif, nous explorerons ces problèmes, leurs démonstrations mathématiques et leurs implications pratiques.

Définitions
Coloration de graphe
Attribution de couleurs aux sommets d'un graphe telle que deux sommets adjacents n'aient jamais la même couleur.
Nombre chromatique (χ(G))
Le nombre minimum de couleurs nécessaires pour colorier tous les sommets d'un graphe G.
Coloration propre
Une coloration où aucune paire de sommets adjacents ne partage la même couleur.
Degré d'un sommet
Le nombre d'arêtes connectées à ce sommet, ou de manière équivalente, le nombre de voisins du sommet.
Réduction polynomiale (≤ₚ)
Une transformation d'un problème A vers un problème B en temps polynomial, notée A ≤ₚ B, qui permet de résoudre A en utilisant une solution de B. Plus formellement :
A ≤ₚ B signifie qu'il existe une fonction f calculable en temps polynomial telle que :
x ∈ A ⟺ f(x) ∈ B
Exemple : Le problème SAT peut être réduit polynomialement au problème du cycle hamiltonien en transformant chaque clause en un "gadget" de graphe spécifique.
NP-complétude
Un problème P est NP-complet s'il satisfait deux conditions :
  1. P ∈ NP : Une solution peut être vérifiée en temps polynomial
  2. P est NP-difficile : Tout problème de NP peut être réduit polynomialement à P
Implications :
  • Si on trouve un algorithme polynomial pour un problème NP-complet, alors P = NP
  • Les problèmes NP-complets sont considérés comme "intrinsèquement difficiles"
  • En pratique, on utilise des heuristiques ou des algorithmes d'approximation
Algorithmes

Algorithme de Coloration

Algorithme Glouton

L'algorithme glouton pour la coloration de graphe est une approche simple mais efficace. Il parcourt les sommets dans un ordre donné et attribue à chaque sommet la plus petite couleur disponible qui n'est pas utilisée par ses voisins.

Fonction ColoreGlouton(G):
    Pour chaque sommet v dans G:
        couleurs_disponibles = {0, 1, 2, ...}
        Pour chaque voisin u de v:
            Si u est déjà coloré:
                Retirer couleur[u] de couleurs_disponibles
        couleur[v] = plus petite couleur de couleurs_disponibles
    Retourner couleur

Algorithme de Parcours Eulérien

Algorithme de Hierholzer
Fonction TrouveCycleEulerien(G, sommet_depart):
    cycle = []
    pile = [sommet_depart]
    
    Tant que pile non vide:
        sommet_courant = sommet au sommet de la pile
        Si degré(sommet_courant) > 0:
            Choisir une arête non visitée e = (sommet_courant, v)
            Supprimer l'arête e
            Empiler v sur la pile
        Sinon:
            Dépiler sommet_courant et l'ajouter au début de cycle
    
    Retourner cycle

Algorithme de Parcours Hamiltonien

Algorithme de Backtracking
Fonction TrouveCycleHamiltonien(G, sommet_depart):
    chemin = [sommet_depart]
    visites = {sommet_depart}
    
    Fonction backtrack(chemin, visites):
        Si len(chemin) == nombre_sommets:
            Si existe_arete(dernier_sommet, sommet_depart):
                Retourner chemin + [sommet_depart]
            Retourner null
            
        Pour chaque voisin v de dernier_sommet:
            Si v non dans visites:
                Ajouter v au chemin et aux visités
                resultat = backtrack(chemin, visites)
                Si resultat non null:
                    Retourner resultat
                Retirer v du chemin et des visités
        
        Retourner null
    
    Retourner backtrack(chemin, visites)
Démonstrations Mathématiques

Introduction au Problème

Le Problème du Voyageur de Commerce (TSP)

Imaginons un voyageur qui doit visiter plusieurs villes. Il veut :

  • Visiter chaque ville exactement une fois
  • Revenir à son point de départ
  • Trouver le chemin le plus court possible
Formalisation du problème

G = (V, E) représente notre carte :

  • V : l'ensemble des villes (sommets)
  • E : l'ensemble des routes entre les villes (arêtes)
Conditions d'un cycle hamiltonien
  1. ∀i ∈ [1,n-1], (vᵢ, vᵢ₊₁) ∈ E
    → Il doit exister une route entre chaque paire de villes consécutives
  2. (vₙ, v₁) ∈ E
    → Il doit exister une route pour revenir au point de départ
  3. ∀i,j ∈ [1,n], i ≠ j ⟹ vᵢ ≠ vⱼ
    → Chaque ville ne doit être visitée qu'une seule fois

Explosion Combinatoire

Nombre de solutions possibles

Pour un graphe de n sommets :

  • Nombre de chemins possibles = (n-1)!
  • Avec 5 villes : 4! = 24 chemins possibles
  • Avec 10 villes : 9! = 362.880 chemins possibles
  • Avec 20 villes : 19! = 121.645.100.408.832.000 chemins possibles
Temps de calcul en pratique

Avec un ordinateur effectuant 1 milliard d'opérations par seconde :

  • 10 villes : environ 3.6 microsecondes
    → Plus rapide qu'un battement de cils
  • 20 villes : environ 77 ans
    → Plus qu'une vie humaine
  • 30 villes : environ 8.4 × 10¹⁵ années
    → Plus que l'âge de l'univers (13.8 × 10⁹ années)

Classes de Complexité

Définitions fondamentales
  • P : Problèmes résolvables en temps polynomial
    Exemple : Tri d'un tableau en O(n log n)
  • NP : Problèmes dont une solution peut être vérifiée en temps polynomial
    Exemple : Vérifier si un chemin est hamiltonien en O(n)
  • NP-complet : Problèmes les plus difficiles de NP
    Si on résout l'un d'eux en polynomial, on les résout tous
Diagramme des classes de complexité P et NP

Diagramme illustrant les relations entre les classes de complexité P et NP

Réduction Polynomiale

Principe de réduction

Pour prouver qu'un problème A est NP-complet :

  1. Montrer que A est dans NP
  2. Réduire un problème NP-complet connu B vers A

Notation : B ≤ₚ A (B se réduit polynomialement à A)

Exemple avec le cycle hamiltonien

Réduction du problème SAT vers le cycle hamiltonien :

Gadget Variable (x₁) x₁ = vrai x₁ = faux Gadget Clause (x₁ ∨ x₂ ∨ x₃) C₁ Connexions aux littéraux Graphe Final Cycle hamiltonien possible Légende : Chemin vrai Chemin faux Connexion clause-variable

Preuve de NP-complétude du Cycle Hamiltonien

1. Appartenance à NP

Un cycle hamiltonien peut être vérifié en temps polynomial :

  • Vérifier que chaque sommet apparaît une fois : O(n)
  • Vérifier que les arêtes existent : O(n)
  • Vérifier que c'est un cycle : O(n)
2. Réduction de 3-SAT vers Cycle Hamiltonien

Construction du graphe G à partir d'une formule 3-SAT :

  1. Pour chaque variable x_i :
    Créer un sous-graphe de sélection avec deux chemins
  2. Pour chaque clause (l_i ∨ l_j ∨ l_k) :
    Créer un sommet de clause connecté aux littéraux
  3. Ajouter des arêtes de connexion entre les gadgets
Équivalence

⟹ Si la formule est satisfiable, il existe un cycle hamiltonien
⟸ Si un cycle hamiltonien existe, la formule est satisfiable

Implications Pratiques

Conséquences de la NP-complétude
  • Pas d'algorithme polynomial connu
  • Si P ≠ NP (conjecture), pas de solution efficace possible
  • Nécessité d'utiliser des heuristiques
Complexité en pratique

Pour n villes :

  • Algorithme exact : O(n!)
  • Plus proche voisin : O(n²)
  • 2-approximation : O(n²log n)
Conclusion

La NP-complétude du problème du cycle hamiltonien n'est pas qu'une curiosité théorique. Elle explique pourquoi :

  • Les solutions exactes sont impraticables pour de grandes instances
  • Les algorithmes approximatifs sont nécessaires en pratique
  • La recherche continue pour améliorer les heuristiques
Outil Interactif
Nœuds: 0 Arêtes: 0 Couleurs: 0
Étapes d'exécution

Cliquez sur "Colorier le graphe" pour voir les étapes d'exécution.

Résultat

Aucune opération effectuée.

Implémentation Python

Voici l'implémentation optimisée de l'algorithme glouton en Python :

def greedy_coloring(graph):
    """
    Implémentation optimisée de l'algorithme glouton pour la coloration de graphe.
    
    Args:
        graph: Un objet NetworkX Graph
        
    Returns:
        Un dictionnaire avec les nœuds comme clés et leurs couleurs comme valeurs
    """
    # Initialisation du dictionnaire de couleurs
    colors = {}
    
    # Trier les nœuds par degré décroissant (heuristique)
    nodes = sorted(graph.nodes(), key=lambda x: graph.degree(x), reverse=True)
    
    for node in nodes:
        # Ensemble des couleurs déjà utilisées par les voisins
        neighbor_colors = {colors.get(neighbor) for neighbor in graph.neighbors(node) 
                          if neighbor in colors}
        
        # Trouver la première couleur disponible
        color = 0
        while color in neighbor_colors:
            color += 1
            
        # Assigner cette couleur au nœud
        colors[node] = color
    
    return colors
Applications

La coloration de graphe trouve de nombreuses applications pratiques :

Planification

Attribution d'horaires, de salles, ou de fréquences pour éviter les conflits.

Réseaux

Attribution de fréquences dans les réseaux sans fil, répartition des canaux WiFi.

Compilation

Allocation de registres dans les compilateurs pour optimiser l'utilisation des ressources.