Scribd
Importer
34 vues7 pages

Projet Complexité

Le problème de coloriage de graphe consiste à attribuer des couleurs aux sommets d'un graphe de manière à ce que deux sommets adjacents n'aient pas la même couleur, avec pour objectif d'utiliser le nombre minimal de couleurs. Ce problème est NP-difficile et a plusieurs variantes, comme le coloriage des arêtes ou le coloriage équitable, et il trouve des applications dans des domaines tels que la planification et la cartographie. Divers algorithmes existent pour le résoudre, allant des méthodes exactes comme le backtracking aux approches d'approximation et aux métaheuristiques.

Transféré par

mohamed.soltane.sl
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
34 vues7 pages

Projet Complexité

Le problème de coloriage de graphe consiste à attribuer des couleurs aux sommets d'un graphe de manière à ce que deux sommets adjacents n'aient pas la même couleur, avec pour objectif d'utiliser le nombre minimal de couleurs. Ce problème est NP-difficile et a plusieurs variantes, comme le coloriage des arêtes ou le coloriage équitable, et il trouve des applications dans des domaines tels que la planification et la cartographie. Divers algorithmes existent pour le résoudre, allant des méthodes exactes comme le backtracking aux approches d'approximation et aux métaheuristiques.

Transféré par

mohamed.soltane.sl
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Problème du coloriage de graphe

Question 1 : Expliquer le problème choisi


Le problème de coloriage de graphe consiste à attribuer des couleurs aux sommets
d’un graphe de telle sorte que deux sommets adjacents (reliés par une arête) ne
partagent pas la même couleur. L’objectif est d’utiliser le nombre minimal de couleurs,
appelé nombre chromatique (noté χ). Ce problème est un défi classique en théorie des
graphes et en optimisation combinatoire, classé NP-difficile, car il n’existe pas
d’algorithme efficace (en temps polynomial) pour le résoudre exactement dans le cas
général.

Question 2 : Formulation mathématique


Question 3 : Variantes du problème
1. Coloriage des arêtes : Colorer les arêtes plutôt que les sommets, avec des
couleurs différentes pour les arêtes adjacentes.

2. Liste-coloriage : Chaque sommet doit être coloré avec une couleur choisie dans
une liste prédéfinie.

3. Coloriage équitable : Répartir les sommets de sorte que chaque couleur soit
utilisée à peu près le même nombre de fois.

4. Coloriage pondéré : Minimiser le coût total, où chaque couleur a un coût


associé.

5. Coloriage total : Colorier à la fois sommets et arêtes.

6. Coloriage contraint : Ajouter des règles spécifiques (ex : certaines couleurs


interdites pour des sommets).

Question 4 : Domaines d’applications


1. Planification : Création d’emplois du temps (cours = sommets, conflits = arêtes).

2. Allocation de registres : En compilation, éviter les conflits de registres.

3. Réseaux sans fil : Attribution de fréquences pour éviter les interférences.

4. Sudoku : Modélisé comme un coloriage 9x9 avec contraintes de voisinage.

5. Cartographie : Colorier des régions adjacentes sur une carte avec un minimum
de couleurs.

6. Synthèse de circuits : Éviter les conflits de ressources dans les circuits


logiques.

Question 5 : Exemple de résolution


Graphe : Triangle (3 sommets connectés en cycle).
Algorithme glouton (sélection de couleurs par ordre décroissant de degré) :

1. Ordonner les sommets par degré (ici, tous de degré 2).

2. Attribuer la couleur 1 au premier sommet.

3. Pour le deuxième sommet adjacent, utiliser la couleur 2.

4. Pour le troisième sommet (adjacent aux deux premiers), utiliser la couleur 3.


Résultat : 3 couleurs utilisées (optimal, car χ = 3 pour un triangle).
Question 6 : Algorithmes proposés
I. Algorithmes exacts :

o Backtracking (force brute avec élagage).

o Branch and Bound : Explore l’espace de solutions en éliminant les sous-


arbres non prometteurs.
o Programmation linéaire en nombres entiers (PLNE).

II. Algorithmes d’approximation :

o Glouton (Welsh-Powell) : Ordonne les sommets par degré décroissant et


attribue la plus petite couleur disponible.
o DSATUR : Priorise les sommets avec le plus grand "degré de saturation"
(nombre de couleurs déjà utilisées par les voisins).

o Algorithme de Lovász : 2-approximation pour les graphes bipartis.


III. Métaheuristiques :

o Recuit simulé : Explore des solutions voisines avec une probabilité


dépendante de la température.

o Algorithmes génétiques : Utilise la sélection, croisement et mutation


pour évoluer vers une solution.
o Colonie de fourmis : Inspire du comportement de recherche de chemin
optimal.

Vous aimerez peut-être aussi