GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== 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 :

  - Association d'une valeur ''-1'', à chaque sommet
  - Création d'une file
  - 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
  - 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 
  - 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)
  - Si on arrive là, il n'y a pas de cycle, renvoyer ''False''

<WRAP important>Cet algorithme ne fonctionne que dans un graphe non orienté.</WRAP>

**Avant de tenter la programmation, testez avec ce graphe**

{{ :nsi:terminales:graphes:graphe_has_cycle.svg |}}

<WRAP box>=== Variante pour graphe orienté ===
  - Créer une copie du graphe et travailler sur la copie,
  - Tant qu'il existe un sommet dont le degré sortant est 0, supprimer ce sommet
  - 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 :
  - Créer la matrice d'adjacence du graphe
  - Tant que l'on peut trouver une ligne ne contenant que des 0,\\ supprimer cette ligne et la colonne correspondante.
  - Si après cela, la matrice n'est pas vide, renvoyer ''True'', sinon renvoyer ''False''.
</WRAP>

===== 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 :

{{ :nsi:terminales:graphes:graphe_is_connexe.svg |}}

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.

<WRAP tip>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.</WRAP>

Par exemple avec ce graphe :

{{ :nsi:terminales:graphes:graphe_is_connexe.svg |}}


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}%%''

<WRAP tip>
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.
</WRAP>

Voici un algorithme

  - Trier les sommets par ordre décroissant de degré
  - Choisir le sommet de plus haut degré qui n'a pas encore de couleur
  - Choisir une nouvelle couleur *col* pour ce sommet.
  - 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//
  - 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.

{{ :nsi:terminales:graphes:coloration.svg |}}

<WRAP tip>
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
  * ...
</WRAP>

<WRAP info>
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.
</WRAP>