Théorie des graphes : Examen final theorie des graphes m2 info 2019
Télécharger PDFExamen Final : Théorie des Graphes - 2ème Année Licence en Informatique
FACULTÉ DES SCIENCES EXACTES ET SCIENCES DE LA NATURE ET DE LA VIE
DÉPARTEMENT DES MATHÉMATIQUES ET DE L'INFORMATIQUE
Mardi 03 Septembre 2019
MODULE : THÉORIE DES GRAPHES
EXAMEN FINAL
Durée de l’épreuve : 01H30
Aucun document n'est autorisé.
La qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.
Exercice 01
(7 points) : Une compagnie aérienne propose des vols directs entre certaines villes, notées A, B, C, D, E, F et H. Cela conduit au graphe G suivant, dont les sommets sont les villes et les arêtes représentent les liaisons aériennes.
1)
Quel est le degré de chaque sommet ? En déduire le nombre des arêtes du graphe G. Quelle est la nature du sous-graphe formé par les sommets A, B, C et D ?
2)
Sur les cartes d’embarquement, la compagnie attribue à chaque aéroport une couleur, de sorte que deux aéroports liés par un vol direct aient des couleurs différentes.
a)
Donnez un encadrement du nombre minimal de couleurs nécessaire, en justifiant.
b)
En utilisant un algorithme approprié, déterminez ce nombre.
3)
Pourquoi est-il impossible pour un voyageur de construire un itinéraire qui utilise chaque liaison aérienne une et une seule fois ?
4)
Montrer qu’il est possible de construire un tel itinéraire en ajoutant une seule liaison qui n’existe pas déjà et que l’on précisera.
Exercice 02
(5 points) : On donne le graphe suivant.
1)
Déterminer le flot maximum.
2)
En déduire la coupe minimale.
Exercice 03
(6 points) : Un expert en multimédias souhaite installer un atelier d’informatique. Les tâches à réaliser pour son projet sont les suivantes.
1)
Tracer le diagramme potentiel étape (PERT) correspondant au projet.
2)
Indiquer sur le graphe les dates au plus tôt et les dates au plus tard pour chaque étape.
3)
Quelles sont les tâches que cet expert devra gérer avec prudence pour ne pas dépasser le délai ?
FAQ
Qu’est-ce qu’un graphe orienté et un graphe non orienté ?
Un graphe orienté est un graphe dont les arêtes ont une direction, tandis qu’un graphe non orienté est un graphe dont les arêtes n’ont pas de direction. Les exercices proposés peuvent concerner l’un ou l’autre selon le contexte.
À quoi sert le diagramme PERT dans la gestion de projet ?
Le diagramme PERT (Program Evaluation and Review Technique) permet de visualiser les différentes étapes d’un projet, leurs dépendances et les temps estimés pour chaque tâche. Il aide à identifier les tâches critiques qui peuvent retarder l’ensemble du projet.
Quelle est la différence entre une coupe et un flot dans un graphe ?
Un flot dans un graphe représente une quantité qui circule à travers les arêtes, tandis qu’une coupe est un ensemble d’arêtes qui sépare le graphe en deux parties. Le flot maximum est le flot le plus important possible dans un graphe, et la coupe minimale est la coupe avec la capacité la plus faible qui limite ce flot.