Exercices corrigés de Graphes

Ces 56 exercices accompagnent le cours de 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.

Le cours de Graphes Tous les parcours

Coloration6 exercices

Les nombres chromatiques à connaître, et pourquoi une coloration ne prouve rien toute seule.

Le cours : Coloration

Familles remarquables6 exercices

Ce que l'appartenance à une famille fait gagner, et le cycle impair qui interdit la bipartition.

Le cours : Familles remarquables

Flots et couplages6 exercices

La coupe qui certifie un flot maximal, et le sommet où la conservation se perd.

Le cours : Flots et couplages

Le vocabulaire6 exercices

Sommets, arêtes, degrés, et ce que la somme des degrés ne peut pas valoir.

Le cours : Le vocabulaire des graphes

Représenter un graphe6 exercices

Degrés, matrice d'adjacence et liste d'adjacence.

Le cours : Représenter un graphe en machine

Parcourir un graphe8 exercices

La file d'un parcours en largeur, et le moment où l'on marque un sommet.

Le cours : Parcourir un graphe

Plus courts chemins6 exercices

Relâcher une arête, et ce qui fait démarrer le calcul.

Le cours : Plus courts chemins

Arbres couvrants6 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és6 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 Graphes, chapitre par chapitre. Les autres parcours sont dans les exercices corrigés.