Course: Graphes (UGA), Topic: Cheminements

Topic outline

General

Cheminements
Chaîne
Connexité
Parcours de graphes / accessibilité
Graphes eulériens
- Compétences
  1. Techniques de preuve
  Connaître les trois étapes d'une preuve algorithmique (exécution, terminaison, validité du résultat)
  Avoir compris les preuves algorithmiques du cours
  Appliquer le schéma de preuve algorithmique sur des problèmes simples
  Avoir compris les preuves par contre exemple minimal/maximal du cours
  Avoir compris les certificats du cours (accessibilité, distance)
  2. Propriétés
  Montrer que l'existence d'un chemin entre deux sommets est une relation d'équivalence
  Connaitre la propriété sur le nombre minimal d'arêtes d'un graphe connexe
  Connaître et démontrer le théorème de Euler (caractérisation des graphes eulériens)
  3. Parcours
  Décrire / Reconnaitre un parcours en profondeur ou en largeur d'un graphe
  Ecrire l'algorithme pour faire un parcours en largeur et en profondeur d'un graphe
  
  Vocabulaire : chaîne, extrémités, simple, élémentaire, longueur, graphe connexe, composante connexe, co-cycle, parcours en largeur, BFS, parcours en profondeur, DFS, st-coupe, cycle, cycle eulérien, chaîne eulérienne, graphe eulérien, cycle hamiltonien, graphe hamiltonien
- Transparents cheminement File
  
  View
- Transparents graphes Eulériens - Hamiltoniens File
  
  View
- One idea, one story: meet the 1962 Procter and Gamble challenge ! Page
  
  View
- One idea, one story: when the salesman started its travel Page
  
  View
- One Idea, one story : L'algorithme de Fleury pour trouver un cycle Eulérien URL
- Feuille d'exercices cheminement File
  
  View
- Test Chaînes, Cycles et Connexité Quiz
  
  View Receive a grade Receive a passing grade
- Test Cheminement complet Quiz
  
  View Receive a grade Receive a passing grade
- Parcours d'un graphe - Java Virtual programming lab
  
  Receive a grade

Topic outline

General

Cheminements

Compétences