Corrigé d'examen de théorie des graphes L3 FI A UPEC 2010
Présentation du document d'examen
Ce document présente le corrigé officiel d'une épreuve de théorie des graphes destinée aux étudiants en Licence 3 (formation initiale A) à l'ESIAG et à l'UPEC. Daté de décembre 2010, le sujet propose une évaluation d'une durée de deux heures sans documents, structurée autour de cinq exercices indépendants couvrant des notions fondamentales de la modélisation et de l'algorithmique des graphes.
Le document offre non seulement les réponses finales aux différents problèmes posés, mais détaille également les étapes de raisonnement, les justifications théoriques ainsi que l'application méthodique des algorithmes requis pour chaque situation étudiée.
Thèmes abordés et exercices traités
L'épreuve aborde plusieurs concepts clés de la théorie des graphes à travers des cas pratiques et des démonstrations de cours :
- Graphes orientés et définitions fondamentales : Analyse de notions telles que les sources et les racines, avec des contre-exemples graphiques pour vérifier des implications logiques.
- Parcours de graphes non orientés : Détermination d'un graphe connexe à partir d'ordres de visite spécifiques respectant l'ordre alphabétique pour le parcours en profondeur et le parcours en largeur.
- Gestion de projets (Méthode MPM) : Modélisation d'un projet informatique comportant plusieurs sous-programmes et contraintes de préséance. Calcul des dates au plus tôt, des dates au plus tard, identification des tâches critiques, et analyse de l'impact d'une modification des ressources humaines sur la durée minimale du projet.
- Optimisation de réseaux (Algorithme de Kruskal) : Construction d'un réseau à coût minimal reliant plusieurs commutateurs tout en intégrant des contraintes politiques imposant certaines liaisons câblées spécifiques.
- Recherche de chemins optimaux (Algorithme de Dijkstra) : Résolution de problèmes de temps de vol minimaux entre différents aéroports, avec et sans prise en compte de temps d'escale obligatoires dans les nœuds intermédiaires.
Méthodes et applications algorithmiques
Chaque exercice met en œuvre des méthodes algorithmiques standard rigoureusement adaptées aux contraintes de l'énoncé. Par exemple, l'algorithme de Kruskal est modifié dès son initialisation pour tenir compte d'arêtes obligatoires prédéfinies. De même, l'algorithme de Dijkstra est appliqué séquentiellement à l'aide de tableaux d'évaluation des distances et des prédécesseurs, permettant de suivre l'évolution des plus courts chemins à chaque étape.
Pour les problèmes d'ordonnancement de projets, le document explicite clairement le calcul de la marge et l'identification de la chaîne critique, démontrant l'influence directe d'un retard ou d'une modification d'affectation de tâches sur la durée totale d'exécution.
Utilité pour la révision
Ce sujet corrigé constitue un support de travail direct pour s'entraîner aux examens universitaires d'informatique et de mathématiques appliquées. Les étudiants peuvent confronter leurs propres méthodes de résolution avec les tableaux de Dijkstra, les matrices d'adjacence ou les diagrammes d'ordonnancement fournis. La clarté des corrections permet d'identifier rapidement les erreurs méthodologiques fréquentes lors de l'application manuelle des algorithmes de graphes.
Questions fréquentes
Quel est le niveau d'études visé par ce sujet d'examen ?
Ce document s'adresse aux étudiants en troisième année de licence (L3) en formation initiale, inscrits dans les filières universitaires concernées à l'ESIAG et l'UPEC.
Quels algorithmes principaux sont manipulés dans les exercices ?
Le sujet fait principalement appel à l'algorithme de Kruskal pour les arbres couvrant de poids minimal, à l'algorithme de Dijkstra pour les plus courts chemins dans les graphes orientés à poids positifs, ainsi qu'aux méthodes d'ordonnancement de projets par graphes de potentiels (méthode MPM).
Comment les contraintes spécifiques sont-elles prises en compte dans l'algorithme de Kruskal ?
Lorsqu'une liaison est imposée par le problème, l'algorithme de Kruskal est adapté en initialisant l'ensemble des arêtes sélectionnées avec ces arêtes obligatoires, et en retirant ces dernières de la liste des arêtes triées par ordre croissant de coût.
Télécharger Corrigé d'examen de théorie des graphes L3 FI A UPEC 2010 pdf
