Conforme au programme
Centres étrangers
Juin
2016
Bac
Spécialité
Tle ES
Mathématiques
Graphe, complétude, convexité, chaîne eulérienne, algorithme de Dijkstra, matrice
Algorithmique
Matrices
.icon_annales.png Une compagnie aérienne utilise huit aéroports que l'on nomme A, B, C, D, E, F, G, et H.

Sujet 4Graphe, complétude, convexité, chaîne eulérienne, algorithme de Dijkstra, matrice45 min

Centres étrangers, juin 2016

ES – Enseignement de spécialité

Algorithmique

Matrices

Exercice

5 pts

Une compagnie aérienne utilise huit aéroports que l’on nomme A, B, C, D, E, F, G et H. Entre certains de ces aéroports, la compagnie propose des vols dans les deux sens. Cette situation est représentée par le graphe Γ ci-dessous, dans lequel :

 les sommets représentent les aéroports,

 les arêtes représentent les liaisons assurées dans les deux sens par la compagnie.

img1

Partie A

1a. Déterminer, en justifiant, si le graphe Γ est complet. 0,5 pt

b. Déterminer, en justifiant, si le graphe Γ est convexe. 0,5 pt

2 Déterminer, en justifiant, si le graphe Γ admet une chaîne eulérienne. Si oui, donner une telle chaîne. 0,75 pt

3 Donner la matrice d’adjacence M du graphe Γ en respectant l’ordre alphabétique des sommets du graphe. 0,75 pt

4 Pour la suite de l’exercice, on donne les matrices suivantes :

M 2 =( 3 1 2 2 1 1 0 1 1 4 1 2 2 0 2 0 2 1 3 1 1 2 0 1 2 2 1 4 1 1 1 1 1 2 1 1 3 0 1 0 1 0 2 1 0 2 0 1 0 2 0 1 1 0 3 0 1 0 1 1 0 1 0 2 ) et M 3 =( 4 8 3 7 6 1 4 1 8 4 8 8 3 6 1 4 3 8 2 7 4 1 6 1 7 8 7 6 7 3 3 2 6 3 4 7 2 3 1 4 1 6 1 3 3 0 5 0 4 1 6 3 1 5 0 4 1 4 1 2 4 0 4 0 ).

Un voyageur souhaite aller de l’aéroport B à l’aéroport H.

a. Déterminer le nombre minimal de vols qu’il doit prendre. Justifier les réponses à l’aide des matrices données ci-dessus. 0,75 pt

b. Donner tous les trajets possibles empruntant trois vols successifs. 0,75 pt

Partie B

Les arêtes sont maintenant pondérées par le coût de chaque vol, exprimé en euros. Un voyageur partant de l’aéroport A doit se rendre à l’aéroport G.

En utilisant l’algorithme de Dijkstra, déterminer le trajet le moins cher. 1 pt

img2

Voir le corrigé

Cet article est réservé aux abonnés
ou aux acheteurs de livres ABC du Bac

Pour approfondir le thème...

Tle ES
Mathématiques
Algorithmique, Matrices, Suites
Spécialité
Inde
Avril
2016
Bac
.icon_annales.png
Représenter la situation par un graphe probabiliste de sommets A et B.
achat | probabilités | étude statistique | graphe probabiliste | matrice de transition
Tle ES
Mathématiques
Algorithmique, Fonctions, Intégration, Probabilités
Spécifique
Nouvelle-Calédonie
Mars
2016
Bac
.icon_annales.png
La proportion de gauchers dans la population française est de 13 %.
gauchers | proportion | fluctuation asymptotique | fonction | fréquence
Tle ES
Mathématiques
Algorithmique, Arithmétique, Matrices
Spécialité
Polynésie
Septembre
2015
Bac
.icon_annales.png
L'objectif affiché par la municipalité est de réduire de moitié la présence des automobiles dans la zone ZTL, dans les deux ans à venir.
pollution | taxe | automobiles | proportion | graphe probabiliste
Tle ES
Mathématiques
Algorithmique, Suites
Spécifique
France métropolitaine
Juin
2016
Bac
.icon_annales.png
Un loueur de voitures dispose au 1er mars 2015 d'un total de 10 000 voitures pour l'Europe.
suite | algorithme | inéquation
Tle ES
Mathématiques
Algorithmique, Suites
Spécifique
Amérique du Nord
Juin
2016
Bac
.icon_annales.png
Une société propose un service d'abonnement pour jeux vidéo sur téléphone mobile.
algorithme | suite | inéquation