-
Exemples
d'application de la coloration de graphes
Algorithmique et informatique
appliqué aux graphes. 1998
[ Descriptif | Contenu | TP de fin d'année ]
| Intitulé officiel: | Algorithmique et informatique |
| Nombre d'heures: | 60 heures |
| Enseignant: | Philippe Rolland |
- - Introduction : vocabulaire et concepts de base (connexité, forte connexité, mise en ordre) ; nombre cyclomatique, arbres et arborescences.
- - Représentations des graphes : matricielles (adjacence, incidence) ; listes (successeurs, prédécesseurs). Les graphes en tant qu'outils de modélisation ; exemples en informatique et en R.O.
- - Parcours des graphes en largeur ; en profondeur ; application : tri topologique d'un graphe sans circuit ; détermination des composantes connexes;
- - Fermeture transitive ; déterminations, méthode matricielle : (I+M)(n-1) algorithme de Roy-Warshall ; parcours en profondeur (cas d'un graphe sans circuit). Evaluation du nombre d'opérations ; initiation à la complexité dans ce cas polynomial.
- - Chemins optimaux dans un graphe valué : algorithmes de Ford, Dijstra. Application : ordonnancements de projets (méthodes NPM et PERT).
- - Flots maximaux dans un réseau de transport l'algorithme de Ford-Fulkerson (exemple, épreuve, complexité). Notion de graphe d'écart et reformulation de cet algorithme. Flot maximal à coût minimal : algorithme de Roy (en E.D.).
- - Programmes de transport : heuristiques et notion de "regret" ; algorithme du stepping-stone).
- - Arbres couvrants de poids extrémal : algorithmes de Kruskal, Sollin. Problèmes d'affectation : la méthode hongroise (lien avec les flots maximaux).
- - Recherches arborescentes : en profondeur d'abord (Pb des reines sur l'échiquier) ; Branch and Bound : résolution du problème du voyageur de commerce (TSP) par l'algorithme de Little.
Algorithme de coloration des sommets d'un graphe simple connexe, non-orienté par DSATUR.
Utilisation d'une structure dynamique
[Applications | SourcesGénéraux | DSATUR | Exercices ]
Exemples
d'application de la coloration de graphes
On peut modéliser le problème de la gestion d'emploi du temps par l'intermédiaire des graphes. Il existe plusieurs possibilités. Par exemple on peut le modéliser sous la forme de la coloration des arêtes d'un graphe bi-partite ou encore par la coloration des sommets d'un graphe d'incompatibilité. C'est la dernière modélisation que l'on va présenter dans la mesure où DSAT est un algorithme de coloration des sommets d'un graphe. On note que le passage entre la coloration des arêtes d'un graphe et celle des sommets de son graphe correspondant n'est pas une difficulté.
Un graphe d'incompatibilité G=(X,E) est un graphe où X désigne l'ensemble des cours à assurer et une arête (x,y) relie les cours x et y s'ils sont incompatibles, ie ne peuvent avoir lieu en même temps.
Résoudre le problème d'emploi du temps revient donc à exhiber un graphe d'incompatibilité, puis de le colorier. On établie un tableau fixant la correspondance entre les colorations et les dates/Heures; Lundi8-10= couleur1, Lundi10-12=couleur2, Lundi14-16=couleur3, etc., vendredi16-18=couleur20 (basé sur 4 crénaux horaires de 2 heures par jour). Une fois le graphe colorié on a par correspondance une affectation temporelle des cours sans conflit.
Plateforme
de programmation sur les graphes (proposition d'une structure dynamique,
convention d'écriture d'un graphe en fichier, lecture du fichier
et insertion dans la structure, libération de la mémoire,
détail de la programmation, etc.). Description de struct.h,
io.c, io.h, memory.c,
memory.h, main.c
Implémentation
de DSATUR (Idem, mais appliqué à la coloration des
sommets d'un graphe par l'algorithme de Brélaz, DSATUR).
Description de dsat.c dsat.h plus
les fichier précédent.
Exercices:
- 1. Mise en place du second critère de Brélaz; ie en cas de conflit choisir le sommet de degré max.
- 2. Modification de la sélection des sommets à colorier:
- Initialement comme DSATUR, Sélectionner le sommet de degré max
- Ensuite selectionner le sommet au voisinage le plus colorier, ie tel que son voisinage contienne le plus de sommets coloriés.
- 3. Idem mais non plus pour le premier voisinage, mais dans le second. [ critereN2.c | critereN2.h ]
- 4. Création d'un générateur de graphes aléatoires connexes, non-orientés. (Rappel dans stdlib.h, il existe int rand() qui donne un chiffre entre 0 et MAX_RAND). [ generateGraph.c | generateGraph.h ]
- 5. Modifier io.c et io.h de manière à tester plusieurs graphes dans le fichier graph.txt.
Philippe Rolland Last modification-03/02