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