Compilation réalisée à partir d’exercices de BAC TES

Lecture 10: Dijkstra’s Shortest Path Algorithm CLRS 24 3 Outline of this Lecture Recalling the BFS solution of the shortest path problem for unweighted (di)graphs The shortest path problem for weighted digraphs Dijkstra’s algorithm Given for digraphs but easily modiﬁed to work on undirected graphs 1

Exercises 1 Minimum spanning trees and shortest paths

of Dijkstra’s algorithm, all shortest paths starting at vertex r have been found The union of these paths forms a tree, which we will call the Dijkstra tree at r a Give an example of a weighted graph, whose minimum spanning tree diﬁers from all its Dijkstra trees b Prove that a minimum spanning tree and a Dijkstra tree of G always have at

Troisième partie Graphes pondérés et algorithmedeDijkstra

Correctiondel’exercice 1:Antilles2016 Des touristes sont logés dans un hôtel H Un guide souhaite faire visiter la région à ces touristes en empruntant les routes signalées comme d’intérêt touristique parl’ofﬁce dutourisme Lestronçons deroutequ’il souhaite em-prunter sont représentés sur le graphe ci-contre

Sujet et corrigé du bac en mathématiques, série ES

En utilisant l’algorithme de Dijkstra, déterminons le trajet le moins cher pour aller de A à G: Après recours à l’algorithme de Dijkstra, nous trouvons comme trajet le moins cher pour aller de l’aéroport A à l’aéroport G: le trajet A - E - D - C - G Et ce dernier coûtera: 45 + 40 + 60 + 50 = 195 €

Compilation réalisée à partir d’exercices de BAC TES

Exercice n° 1 Un groupe d’amis organise une randonnée dans les Alpes On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer Une arête entre deux sommets coïncide avec l’existence d’un chemin entre les deux sommets 1) a) Recopier et compléter le tableau suivant :

Tes Devoir surveillé n°6 : Exercice 1

Exercice 2 Une usine produit deux types E et F de moteurs Le bénéfice B, exprimé en milliers d’euros, pour une production journalière de x moteurs E et y moteurs F est : B x y x y x y22, 0,05 0,08 0,6 0,7 On admet que la production totale est vendue et que 0 10ddx; 08ddy 1 Calculer le bénéfice réalisé avec a

Correction Term ES spé Devoir Surveillé 3

Exercice 2 Un parc de loisirs décide d’ouvrir une nouvelle attraction pour les jeunes enfants : un parcours pédestre où chaque enfant doit recueillir, sur diﬀérents lieux, des indices pour résoudre une énigme Le parcours est représenté par le graphe ci-dessous

Corrigé du baccalauréat ES–L Antilles–Guyane juin 2016

[Corrigé du baccalauréat ES–L Antilles–Guyane \ juin 2016 EXERCICE 1 5 points Commun à tous les candidats 1 L’équation f (x)=0 admet exactement 2 solutions, la première sur [−1 ; 1] et la deuxième sur

MATHS APPLIQUEES A LINFORMATIQUE - Introduction à la théorie

Enfin, à titre d'exercice, nous proposons quelques problèmes et applications Nous encourageons vivement le lecteur à essayer de les résoudre afin de prendre la matière bien en main Le lecteur qui veut aborder ce chapitre devrait avoir : - une maîtrise élémentaire d'un tableur de type Excel ou OpenOffice,

Examen de Théorie des Graphes - epiportalcom

Dans cet exercice on ne considère que des graphes simples, planaires, et non-orientés Pour un tel graphe G = (V, E), on note n = jVjle nombre de sommets, e = jEj/2 le nombre d’arêtes, et f le nombre de faces Le degré moyen d’un graphe est 1 n å v2V deg(v) 1 (2pts) Justiﬁez que 3f 2e Réponse :

Page 1/11 jgcuaz@hotmail.com

GRAPHES - EXERCICES CORRIGES

Compilation réalisée à partir d"exercices de BAC TES

Exercice n°1.

Un groupe d"amis organise une randonnée dans les Alpes. On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer. Une arête entre deux sommets coïncide avec l"existence d"un chemin entre les deux sommets.

1) a) Recopier et compléter le tableau suivant :

Sommets B C D F N T

Degré des sommets du graphe

b) Justifier que le graphe est connexe.

2) Le groupe souhaite passer par les six sommets en passant une fois et une seule par chaque chemin.

Démontrer que leur souhait est réalisable. Donner un exemple de trajet possible.

3) Le groupe souhaite associer chaque sommet à une couleur de sorte que les sommets reliés par un chemin n"ont pas la

même couleur. On note n le nombre chromatique du graphe. a) Montrer que

4 6n£ £

b) Proposer un coloriage du graphe permettant de déterminer son nombre chromatique.

4) Le groupe se trouve au sommet B et souhaite se rendre

au sommet N. Les distances en kilomètres entre chaque sommet ont été ajoutées sur le graphe. Indiquer une chaîne qui minimise la distance du trajet.

Justifier la réponse.

Exercice n°2.

Une agence de voyages organise différentes excursions dans une région du monde et propose la visite de sites

incontournables, nommés A, B, C, D, E et F.

Ces excursions sont résumées sur le graphe ci-dessous dont les sommets désignent les sites, les arêtes

représentent les routes pouvant être empruntées pour relier deux sites et le poids des arêtes désigne le temps de

transport (en heures) entre chaque site.

1) Justifier que ce graphe est connexe.

2) Un touriste désire aller du site A au site F en limitant au maximum les temps de transport.

a) En utilisant un algorithme, déterminer la plus courte chaîne reliant le sommet A au sommet F.

b) En déduire le temps de transport minimal pour aller du site A au site F.

Page 2/11 jgcuaz@hotmail.com

3) Un touriste désirant apprécier un maximum de paysages souhaite suivre un parcours empruntant toutes les routes

proposées une et une seule fois. Si ce parcours existe, le décrire sans justifier ; dans le cas contraire justifier qu"un tel

parcours n"existe pas.

Exercice n°3.

Première partie : Etude d"un graphe

On considère le graphe ci-dessus.

1) a) Ce graphe est-il connexe ?

b) Déterminer le degré de chacun des sommets. On pourra donner le résultat sous forme d"un tableau c) Justifier l"existence d"une chaîne eulérienne.

2) a) Déterminer un encadrement du nombre chromatique de ce graphe.

b) Montrer que ce nombre chromatique est égal à 3

Deuxième partie : Visite d"n musée

Voici le plan d"un musée : les parties grisées matérialisent les portes et les visiteurs partent de l"accueil, visitent le musée

et doivent terminer leur visite à la boutique.

1) Représenter la situation à l"aide d"un graphe en précisant ce que représentent arêtes et sommets.

2) a) Pourquoi est-il possible de trouver un circuit où les visiteurs passent une fois et une seule par toutes les portes ?

b) Donner un exemple d"un tel circuit.

3) Comment colorier les salles y compris l"accueil et la boutique, en utilisant un minimum de couleurs, pour que 2 salles

qui communiquent par une porte aient des couleurs différentes ?

Exercice n°4.

Une grande ville a créé un jardin pédagogique sur le thème de l"écologie, jardin qui doit être visité par la suite par la

majorité des classes de cette ville. Ce jardin comporte six zones distinctes correspondant aux thèmes : A. Eau B. Economie d"énergie C. Plantations et cultures locales D. Développement durable E. Biotechnologies F. Contes d"ici (et d"ailleurs) Ces zones sont reliées par des passages (portes) où sont proposées des questionnaires. Le jardin et les portes sont représentés par le graphe ci-dessous (chaque porte et donc chaque questionnaire est représenté par une arête)

Question préliminaire : Si un visiteur répond à tous les questionnaires, à combien de questionnaires aura-t-il répondu ?

Partie A :

1) Donner la matrice G associée à ce graphe

2) Le graphe est-il complet ? Est-il connexe ? Justifier

3) Peut-on parcourir le jardin en répondant à tous les questionnaires et sans repasser deux fois devant le même

questionnaire : a) En commençant la visite par n"importe quelle zone ?

b) En commençant la visite par la zone C (plantations et cultures) ? Dans ce cas, si la réponse est positive, quelle sera la

dernière zone visité.quotesdbs_dbs7.pdfusesText_5

[PDF] Compilation réalisée à partir d’exercices de BAC TES