Table des matières

Algorithmes pour graphes non orientés

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.

Recherche d'un cycle

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

Cet algorithme ne fonctionne que dans un graphe non orienté.

Avant de tenter la programmation, testez avec ce graphe


Variante pour graphe orienté

  1. Créer une copie du graphe et travailler sur la copie,
  2. Tant qu'il existe un sommet dont le degré sortant est 0, supprimer ce sommet
  3. Si après cela, il reste des sommets, alors il n'y a plus que des sommets de degré sortant d'au moins 1 et donc il y a au moins un cycle. Donc renvoyer True.
    Sinon, renvoyer False.

On peut faire la même chose en ne travaillant que sur la matrice d'adjacence :

  1. Créer la matrice d'adjacence du graphe
  2. Tant que l'on peut trouver une ligne ne contenant que des 0,
    supprimer cette ligne et la colonne correspondante.
  3. Si après cela, la matrice n'est pas vide, renvoyer True, sinon renvoyer False.

Connexité

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.

Coloration

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.

Le terme “coloration” n'est qu'une image. On n'a pas besoin de colorier les sommets. L'important est de définir des classes de sommets, des familles. Sur une feuille de papier, une manière commode de le faire serait de colorier avec des feutres, d'où le nom. Cela rappelle d'ailleurs le fameux problème consistant à colorier une carte de sorte que deux pays voisins n'aient pas la même couleur.

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}

Ce n'est pas la seule solution possible, ce n'est qu'un exemple. 3 étiquettes ont suffi pour ce graphe, donc tout autre solution ne devrait pas avoir plus de 3 étiquettes.

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.


Ce problème est un problème de compatibilité. On trouve ce problème dans de nombreux cas :

  • réalisation d'un emploi du temps de lycée,
  • organiser les fréquences d'un réseau d'antennes GSM,
  • résoudre un Sudoku
  • …

On appelle nombre chromatique le nombre minimal de couleur permettant de colorer un graphe. L'algorithme précédent ne garantit pas que l'on trouve une coloration minimale. En général, tout ce qu'on peut faire, c'est trouver un argument permettant de préciser une valeur minimale de ce nombre. Par exemple, dans le graphe ci-dessus, D-E-O forme un sous-graphe complet. D, E et O ont forcément des couleurs différentes. On doit donc utiliser au moins 3 couleurs pour ce graphe. Si on arrive à trouver une coloration en 3 couleurs, c'est une coloration minimale et le nombre chromatique est 3. Mais si je ne trouve qu'une coloration en 4 couleurs, je ne peux rien conclure, à moins de trouver une preuve qu'on ne peut pas faire mieux que 4.