Exercices corrigés — Composantes fortement connexes et couplages (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Le transposé garde les composantes, pas le quotient Exercice de TD
- Tester la forte connexité en deux parcours Exercice de TD
- Le piège de l'ordre Exercice de TD
- 2-sat : reconnaître une formule insatisfiable Exercice de TD
- Le glouton est une 2-approximation, et pas mieux Exercice de TD
- Hall et König Exercice de TD
- Problème — Kosaraju : pourquoi le second parcours ne déborde pas Exercice de TD
- Décomposer à la main Application directe du cours
- Dérouler Kosaraju Application directe du cours
- 2-sat : construire le graphe et conclure Application directe du cours
- Le recasage, pas à pas Application directe du cours
- Problème — 2-sat : du critère au modèle Application directe du cours
- Problème — Affecter des étudiants à des stages Application directe du cours
- Problème — Le théorème de König Application directe du cours
- Problème — Rendre un graphe fortement connexe Application directe du cours