Algorithmique et informatique

appliqué aux graphes

Version Multimédi@ (ie. fichier Acrobat pdf)

Descriptif général

Category	Graphs Theory & OR
Professeur	Philippe Rolland
Start	09/1997
Updated	2007

Contenu du module

I. Introduction : Les problèmes combinatoires : généralités, difficultés.

II. Théorie des graphes et algorithmes de base

- 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.

III. Algorithmes d'optimisation dans les graphes valués

- 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.

TP de fin d'année

Algorithme de coloration des sommets d'un graphe simple connexe, non-orienté par DSATUR.

Utilisation d'une structure dynamique

[Environnement | Applications | SourcesGénéraux | DSATUR | Exercices ]

Langage : C ANSI.

Plateforme: CodeWarrior IDE2.0

System: MacOs 8.0, Fr

Processor : G3, PPC 604e

---

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.

Tri à Bulle & sélection
parcours.c profondeur et largeur(01/2006)
glouton.c Glouton(02/2006)

Philippe Rolland : prolland at free dot fr .1996-2007