Théorie des graphes : Examen final theorie des graphes m2 info 2019
Télécharger PDFFACULTÉ DES SCIENCES EXACTES ET SCIENCES DE LA NATURE ET DE LA VIE DÉPARTEMENT DES MATHÉMATIQUES ET DE L'INFORMATIQUE 2
éME ANNÉE LICENCE EN 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 pts) : 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 arrê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 pts) : On donne le graphe suivant : 1) Déterminer le flot maximum 2) En déduire la coupe minimale.
Exercice 03(6 pts) : Un expert en multimédias, veut 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 ce délai ? BONNE CHANCE Mr. Merouani H.