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é 

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 :
    
   
   
3. Pour trouver le nombre de chemins de longueur 4 reliant deux sommets, il faut connaître les coefficient de la matrice M⁴.
   On lit dans cette matrice que M⁴ _(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é 

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 :

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.

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.