Iutreims mathematiques appliquees 2eme annee 2005 info mathematiques appliquees 2eme annee informatique semestre 2

INFO 2AIUT de Reims-Chalons-CharlevilleMATHEMATIQUES ApPLIQUEESDuree de l'epreuve : 2 heures.Aucun document autorise. L'usage de la calculatrice est interdit.1 Theorie des graphesExercice 1.1. Questions de cours1. A quoi correspondent le degre interieur et le degre exterieur d 'un sommet ?2. Qu'est-ce qu'une valuation pour un graphe oriente?3. Quel est l'algorithme le plus efficace pour la recherche de chemins de poids minimal?4. Quel est le plus efficace pour la de chemins de poids maximal?5. Quelle est l'orthographe exacte de Dijsktra ? Djikstra ? ou Dijkstra ? ou bien Dijktsra ?-Exercice 1.2. Soit G = (X, U) un graphe oriente defini a partir d'un ensemble de sommetsX et d'un ensemble d'arcs U.X = {a, b, c, d, e, J, g, h, i,j}U = {(a, b), (b, d), (c, a), (c, d), (c, g), (d, a), (e, c), (f, e), (g, f), (h, g), (h, i), (h, j), (i,j), (j, h)}1. Justifiez que le graphe G = (X, U) n'est pas Jortement connexe.2. Determinez l 'ensemble des composantes fortement connexes maximales (cJcm). (Remarqueles etapes de l'algorithme +- doivent apparaftre sur votre copie).Exercice 1.3. Circuits dans un graphe orienteUn circuit dans un graphe oriente est un chemin (succession d'arcs adjacents) dont le debut(l'extremite initiale du premier arc) coincide avec la fin (l'extremite finale du dernier arc).En vous inspirant des algorithmes vus en cours et en TD, proposez deux methodes differentespour detecter la presence de circuits dans un graphe oriente. Il n'est pas ...