Interro 1 — Graphes

MPI, année scolaire 2022-2023 — durée 45 min.

Question 1.

1. Rappeler ce que calcule l'algorithme de Kruskal avec le maximum de précision.
2. Rappeler l'algorithme de Kruskal.
3. Prouver que l'algorithme de Kruskal est correct.
4. Détailler le calcul de la complexité de cet algorithme.

Question 2.

1. Rappeler ce que calcule l'algorithme de Kosaraju avec le maximum de précision.
2. Rappeler l'algorithme de Kosaraju avec précision.
3. Prouver que l'algorithme de Kosaraju est correct.
4. Détailler le calcul de la complexité de Kosaraju.

Question 3. Rappeler ce qu'est un graphe bipartite.

Question 4. Rappeler ce qu'est un couplage dans un graphe, non nécessairement bipartite.