Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:terminales:graphes:algos_graphes_non_orientes [2021/11/08 19:48] – goupillwiki
+++ nsi:terminales:graphes:algos_graphes_non_orientes [2023/01/05 18:25] (Version actuelle) – goupillwiki
@@ Ligne 1: / Ligne 1: @@
 ====== Algorithmes pour graphes non orientés ======
-On suppose que l'on dispose d'une classe ''Graph'' permettant de gérer un graphe. On veut le doter de méthodes supplémentaires.
+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 =====
@@ Ligne 14: / Ligne 14: @@
   - 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
+    * 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)
@@ Ligne 23: / Ligne 23: @@
 **Avant de tenter la programmation, testez avec ce graphe**
-{{ :nsi:terminales:graphe_has_cycle.svg |}}
+{{ :nsi:terminales:graphes:graphe_has_cycle.svg |}}
 <WRAP box>=== Variante pour graphe orienté ===
@@ Ligne 73: / Ligne 73: @@
   - S'il reste des sommets sans couleur, recommencer en 2.
-**Exemple d'application :** Dans un week-end de conférences, on doit organiser 20 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.
+**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 |}}