Niveau: Supérieur, Licence, Bac+3
UNIVERSITE de NICE – SOPHIA ANTIPOLIS UFR SCIENCES L3 MASS P/ESD Examen de Mathematiques Appliquees 2011–2012 Examen du Mardi 13 Decembre 2011 Duree : 2h Les documents, calculatrices,... ne sont pas autorises. Sujet A : Exercice 1 : Graphes Le graphe suivant represente un reseau routier (avec des sens interdits), ou on a indique les distances en kilometres. On part du sommet 0. 1 3 5 6 72 83 7 4 2 8 4 0 0 2 3 6 3 2 2 2 5 7 1 1 1 1.1. Y a t-il un circuit dans le graphe ? Oui, par exemple le circuit 1-5-2-1. 1.2. Choisir l'algorithme approprie pour determiner le chemin le plus court qui relie 0 aux autres sommets et l'appliquer. On ne peut pas appliquer l'algorithme pour les graphes sans circuits, on utilise donc l'algo- rithme de Dijkstra. On obtient alors le tableau suivant : 1 pred 2 pred 3 pred 4 pred 5 pred 6 pred 7 pred 8 pred 0 7 0 3 0 4 0 2 5 2 5 2 11 2 3 1 6 1 4 11 4 5 8 5 9 5 6 7 1.3. Quelle est la valeur et quelle est la composition du plus court chemin pour aller de 0 a 7 ? 1
- algorithme pour les graphes sans circuits
- tas etant
- algo- rithme de dijkstra
- tas
- derniere allumette
- allumette
- akq1 ?