On dispose d'une classe Graph permettant de gérer un graphe. On veut le doter de méthodes supplémentaires. Votre travail est de faire les implémentations nécessaires.

On veut définir une méthode has_cycle qui renvoie True si le graphe contient un cycle.

La méthode fonctionne pour un graphe non-orienté. C'est une approche utilisant un parcours en largeur – utilisation d'une file :

1. Association d'une valeur -1, à chaque sommet
2. Création d'une file
3. Choix d'un sommet – peu importe le quel – parmi ceux dont la valeur est -1.
   On lui associe la valeur 0 et on le place dans la file
4. Tant que la file n'est pas vide, prendre le prochain sommet S dans la file et visiter chaque voisin V de S
   • si valeur associée à V >= valeur associée à S, on a trouvé un cycle, renvoyer True
   • si valeur associée à V est -1, associer à V : valeur de S + 1 et placer V dans la file
   • sinon, ne rien faire
5. Si on en arrive là, c'est que la file s'est vidée.
   S'il reste des sommets à -1, en prendre un, le mettre dans la file et reprendre en (3)
6. Si on arrive là, il n'y a pas de cycle, renvoyer False

Avant de tenter la programmation, testez avec ce graphe

On voudrait écrire une méthode connected_vertex qui pour un graphe et un sommet origine donné donne tous les sommets pouvant être atteints depuis l'origine. Exemple avec le graphe :

Depuis ce graphe g, on voudrait que g.connected_vertex('A') renvoie tous les sommets pouvant être atteint depuis 'A', soit ici ['A', 'B', 'D', 'E', 'F']. L'ordre n'a pas d'importance.

Une approche parcours en largeur est possible.

On souhaite définir une méthode color attribuant une étiquette à chaque sommet en essayant de minimiser le nombre d'étiquettes différentes et en faisant en sorte que deux sommets voisins n'aient pas la même.

Par exemple avec ce graphe :

Pour ce graphe g on souhaite que g.color() renvoie :

{'A':0, 'B':1, 'C':0, 'D':1, 'E':0, 'F':2, 'G':1, 'F':2}

Voici un algorithme

1. Trier les sommets par ordre décroissant de degré
2. Choisir le sommet de plus haut degré qui n'a pas encore de couleur
3. Choisir une nouvelle couleur *col* pour ce sommet.
4. Parcourir les sommets par ordre décroissant. Quand on en trouve un sans couleur et non adjacent à un sommet déjà colorié avec col, lui attribuer la couleur col
5. S'il reste des sommets sans couleur, recommencer en 2.

Exemple d'application : Dans un week-end de conférences, on doit organiser 15 conférences. Lors de leur inscription, chaque participant a pu choisir les conférences auxquelles ils souhaite assister. On organise l'emploi du temps des conférences après les inscriptions de façon à permettre à chacun d'assister à toutes les conférences auxquelles il s'est inscrit. Si un participant s'est inscrit aux conférences A, B, C, on comprend que ces conférences ne peuvent pas avoir lieu simultanément. Ces contraintes sont exprimées dans le graphe ci-dessous.