Corrigé Bac ES Maths 2019 Amérique du Nord - Graphes, matrices et algorithme de Dijkstra

Cet exercice de Spécialité maths a fait l'objet d'un sujet de bac ES 2019 en Amérique du Nord, découvre son corrigé.

Ton prof de soutien scolaire en ligne s'est penché sur l'exercice 2 Spécialité consacré aux graphes, matrices et algorithme de Dijkstra.
Point par point, il propose ce corrigé et t'aide ainsi dans tes révisions bac avec ce sujet précis.

Partie A - Graphes, matrices : énoncé 

5b3a6908248fd90921f86388d653be238bb471de

9b6b2805a81177ffc4840fd76f1260459e73a3c2

Corrigé de l'exercice partie A

  1. Le mot abab est reconnu par l’automate : chemin 1234.
    Le mot abc n’est pas reconnu par l’automate.
    Le mot abbcbb est reconnu par l’automate : chemin 121234.

  2. Matrice :
     
    sujet de bac maths 2019 sur les matrices
  3. Pour trouver le nombre de chemins de longueur 4 reliant deux sommets, il faut connaître les coefficient de la matrice M4.
    On lit dans cette matrice que M4 (1,4) = 5.
    Donc il y a 5 chemins de longueur 4 reliant les sommets 1 et 4,  et par conséquent 5 mots de 4 lettres reconnus par l’automate.
    Les 5 mots sont : abab , acbb , bbab , baab et bcbb.

 

Partie B - Algorithme de Dijkstra : énoncé 

b56a5b363fbdb248490aa6095fde736e5fe2d792

f59b2757cb702e57569671e91a9e73bdacadc36b

Corrigé de l'exercice partie B

1)
a)  Rappel de cours : Un graphe G est connexe si chaque couple de sommets est relié par une chaîne.
Donc le graphe est connexe.
Le tableau suivants donne les degrés des différents sommets :
91f05e97d553bd7901e5798fea22564c40ba40ba
Rappel de cours : Soit G un graphe connexe.
- G admet un cycle eulérien si, et seulement si, tous les sommets de G sont de degré pair.
- G admet une chaîne eulérienne distincte d’un cycle si, et seulement si, deux sommets de G exactement sont de degré impair. Dans ce cas, la chaîne est d'extrémité ces deux sommets.

Deux sommets sont de degré impair, donc d’après d’après le théorème d’Euler, il existe une chaîne eulérienne permettant de parcourir l’ensemble du réseau en empruntant chaque route une et une seule fois.

b) Le technicien doit commencer par un sommet de degré impair, soit G(renoble) ou L(yon).

2)
a) Pour déterminer le trajet le plus rapide pour aller de B vers A, on utilise l’algorithme de Dijkstra.

B

C

E

G

L

P

V

A

Sommet

0

B

180B

80B

L

260L

150L

180B

180L

E

260L

180B

230E

180L

G

260L

230E

180L

V

260L

230E

P

260L

410P

C

420C

410P

A

Le chemin le plus court est donc BLEPA avec une distance de 410 km.

 b) Si la route entre Le-Puy-en-Velay et Aurillac est fermée à la circulation, d’après l’algorithme précédent, le chemin le plus court est BLCA de longueur 420 km.

Qu'avez-vous pensé de cet exercice ?

Cliquez sur une étoile pour noter.

Note moyenne 0 / 5. Compte des notes 0

Pas de note pour le moment.

Informations abonnement
linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram