Comment réussir un exercice de maths sur les graphes, matrices et algorithme de Dijkstra ?

Réponse :

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 :
     
    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é 


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.

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.






Cette question a été utile ?

Moyenne de 4 sur 5 pour 5 votes.
En poursuivant votre visite sur ce site, vous acceptez l'utilisation de traceurs pour réaliser des statistiques de vos visites. Lire la politique de confidentialité.