Parcours de graphes⚓︎
Intentions⚓︎
Introduction
Beaucoup de problèmes sur les graphes nécessitent que l’on parcourt de façon systématique les arêtes/arcs du graphe afin d’en visiter les sommets pour mettre en évidence plusieurs caractéristiques structurelles (sommets accessibles depuis un sommet particulier, chemins, connexité, etc.).
Dans ce chapitre, nous nous intéressons aux deux principales stratégies élémentaires d’exploration : le parcours en largeur et le parcours en profondeur.
Déroulé
On propose le déroulé suivant :
- un point de cours interactif présentant le parcours en largeur ;
- des exercices d'entraînement (sur papier et sur notebook) pour manipuler le parcours en largeur ;
- un point de cours interactif présentant le parcours en profondeur ;
- des exercices d'entraînement (sur papier et sur notebook) pour manipuler le parcours en profondeur.
Cours⚓︎
Cours (avec les deux parcours)
Exercices (avec les deux parcours)
Pour les exercice 2 et 4, on utilisera l'une des deux méthodes ci-dessous :
- Accès via Capytale : dans la zone
Titrede la bibliothèque de Capytale, taper les phrases ci-dessous :
NSI Terminale Partie 3 Chapitre 3 Parcours graphes largeur
NSI Terminale Partie 3 Chapitre 3 Parcours graphes profondeur
- Accès sans Capytale : télécharger les notebooks dans la rubrique Ressources ci-dessous