Bureau d'étude PEIP - IS
TP3
Le but de ce TP est de se familiariser avec la manipulation des graphes et les possibilités qu'offre cette modélisation en implémentant deux algorithmes fondamentaux : le parcours en largeur et la coloration.
Parcours en largeur
On s'intéresse à l'algorithme du parcours en largeur d'un graphe. Celui ci fonctionne de la manière suivante : on commence par explorer un nœud source, puis ses successeurs, puis les successeurs non explorés des successeurs, etc. L'algorithme de parcours en largeur permet de calculer les distances de tous les nœuds depuis un nœud source dans un graphe. Il peut aussi servir à déterminer si un graphe non orienté est connexe.
À partir d'un nœud source S, il liste d'abord les voisins de S pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une file dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés. Les nœuds déjà visités sont marqués afin d'éviter qu'un même nœud soit exploré plusieurs fois.
Résumé de l'algorithme
Étapes de l'algorithme :
- Mettre le nœud source dans la file.
- Retirer le nœud du début de la file pour le traiter.
- Mettre tous les voisins non explorés dans la file (à la fin).
- Si la file n'est pas vide reprendre à l'étape 2.
Voici le pseudo-code de cet algorithme dans une version où il construit simplement la liste des sommets atteignable depuis le sommet source :
Travail demandé
- Implémentez l'algorithme du parcours en largeur pour qu'il prenne en paramètre une matrice d'adjacence représentant un graphe ainsi qu'un sommet source et renvoie la liste des sommets atteignables depuis le sommet source dans le graphe.
- Proposez une fonction qui, en utilisant cette algorithme, renvoie True si le graphe est connexe et False sinon.
- Implémentez une variante de l'algorithme du parcours en largeur qui renvoie la distance entre le sommets source et les autres sommets du graphe.
Coloration
On s'intéresse à la coloration d'un graphe. La coloration des sommets d’un graphe consiste à affecter à tous les sommets de ce graphe une couleur de telle sorte que deux sommets adjacents ne portent pas la même couleur.
Une coloration avec k couleurs est donc une partition de l’ensemble des sommets en k stables, un stable étant définit comme un sous-ensemble S de V qui ne comprend que des sommets non adjacents deux à deux.
Algorithmique de Welsh Powell
L'algorithme de Welsh Powell est un algorithme qui permet de trouver une bonne coloration d'un graphe, c'est à dire une coloration utilisant le moins de couleurs possible, sans garantie toutefois qu'elle soit optimale (avec le nombre minimum de couleur qu'il faudrait pour colorer le graphe). L'algorithme a cependant l'avantage d'être assez simple dans son fonctionnement et de s'exécuter rapidement.
Étapes de l'algorithme :
- Classer les sommets par degrés décroissants.
- En parcourant la liste dans l’ordre ainsi créé, attribuer une couleur non encore utilisée au premier sommet non encore coloré, et attribuer cette même couleur à chaque sommet non encore coloré et non adjacent à un sommet de cette couleur.
- S’il reste des sommets non colorés dans le graphe, revenir à l’étape 2. Sinon, FIN.
Travail demandé
Mettre en oeuvre l'algorithme de Welsh Powell en utilisant des entier pour symboliser les couleurs. En prenant un graphe en paramètre (sous la forme d'une matrice d'adjacence de taille n), votre programme renverra une liste de n entier correspondant aux couleurs associées à chaque sommet.
Un petit générateur de graphes pour tester vos fonctions.