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, Probabilités, Suites
Spécialité
Amérique du Nord
Juin
2016
Bac
.icon_annales.png
Un groupe de presse édite un magazine qu'il propose en abonnement.
graphe probabiliste | algorithme | suite
Tle ES
Mathématiques
Algorithmique, Fonctions, Suites
Spécifique
Antilles-Guyane
Juin
2016
Bac
.icon_annales.png
On donne un tableau de variation d'une fonction f définie sur l'intervalle [-1 ; 3].
fonction | variation | équation | suite | algorithme
Tle ES
Mathématiques
Algorithmique, Matrices, Suites
Spécifique
Liban
Mai
2016
Bac
.icon_annales.png
L'entreprise PiscinePlus, implantée dans le sud de la France, propose des contrats annuels d'entretien aux propriétaires de piscines privées.
piscines | contrats | algorithme | variables | suite
Tle ES
Mathématiques
Algorithmique, Suites
Spécialité
Liban
Mai
2016
Bac
.icon_annales.png
L'entreprise PiscinePlus, implantée dans le sud de la France, propose des contrats annuels d'entretien aux propriétaires de piscines privées.
piscines | contrats | graphe probabiliste | probabilités | algorithme
Tle ES
Mathématiques
Algorithmique, Suites
Spécifique
Polynésie
Juin
2016
Bac
.icon_annales.png
Une entreprise s'intéresse au nombre d'écrans 3D qu'elle a vendus depuis 2010.
écrans 3D | suite arithmético-géométrique | relation de récurrence | inéquation | algorithme