Exercices corrigés de Théorie des graphes
Ces 15 exercices accompagnent le cours de Théorie des graphes et suivent son ordre, notion par notion. Chacun se corrige dans la page, au clic : pas de compte à créer, pas de fichier à rendre, et la correction dit ce qui ne va pas plutôt que de donner une note.
Représenter un graphe3 exercices
Degrés, matrice d'adjacence et liste d'adjacence.
Le cours : Représenter un graphe en machine
Parcourir un graphe3 exercices
La file d'un parcours en largeur, et le moment où l'on marque un sommet.
Le cours : Parcourir un graphe
Plus courts chemins3 exercices
Relâcher une arête, et ce qui fait démarrer le calcul.
Le cours : Plus courts chemins
Arbres couvrants3 exercices
Kruskal arête par arête, union-trouve, et le compte des arêtes d'un arbre.
Le cours : Arbres et arbres couvrants
Graphes orientés3 exercices
Tri topologique, dates au plus tôt, marges et chemin critique.
Le cours : Graphes orientés, DAG et ordonnancement
Les notions ci-dessus sont enseignées dans le cours de Théorie des graphes, chapitre par chapitre. Les autres parcours sont dans les exercices corrigés.