BAC ES 2014 Graphes (sujet spécialité Amérique du Nord)
4
pages
Français
Documents
2014
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
4
pages
Français
Documents
2014
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Quelque soit votre niveau vous trouverez des ressources adaptées pour progresser.
Ex 4 spécialité BAC ES 2014 Amérique du Nord
-graphe connexe, graphe complet
-chaîne eulérienne, cycle eulérien
-matrice d'un graphe
-algorithme de Dijkstra
MATHS-LYCEE.FR
TESeCg´pihae1tr1:e-excrciceroireBACetsdR´sivesnoie´psjus-
ExtraitBACES2014Ame´riqueduNORD
MATHS-LYCEE.FR`lveseeduolrsee´lyc´eeserpsecruos
MATHS-ES.FR´mreECASteABsejurdduNoiqueEELAoc:SET-NIMRmpcoetl`ecrronti
2014avecaide,rappelsdecoursetcorrectiond´etaille´e
EXERCICE 11-1-3
tempsestim´e:20-30mn
Lorsd’unecampagne´electorale,unhommepolitiquedoiteffectuerunetourne´edanslesvillesA,B,C,
D,E,F,GetH,enutilisantler´eseauautoroutier.
LegrapheGci-dessous,repre´sentelesdiffe´rentesvillesdelatourne´eetlestron¸consd’autoroutereliant
cesvilles(unevilleestrepr´esent´eeparunsommet,untron¸cond’autorouteparuneareˆte):
Partie A
1.´eDrmterenijne,itsutnafise:thpGegears,li
a) complet.
☛Solution:
Les sommets A et C par exemple ne sont pas adjacents
donctouslessommetsnesontpasadjacentsdeux`adeux
donc le graphe G n’est pas complet.
b) connexe.
☛Solution:
LachaıˆneA-B-C-E-D-H-G-Fpassepartouslessommetsdugraphe
donc le graphe G est connexe.
Chapitre 11:/14aPegACeBsdetuj-s´espsnoisive´R
Maths en Terminale ES
(soutien et perfectionnement)
MATHS-LYCEE.FR
TESe´girrcocecierex-
Chapitre 11:RCedABejste-sussp´sion´evi
2.uttoqahcraps,elliveuJ)suablsi’oedanrgerisefiit’uqrselisoptantaumoinsunefoialotru´neeneapss
enempruntantunefoisetuneseulechaquetronc¸ond’autoroute.
☛Solution:
De´terminers’ilestpossibled’organiserlatourn´eeenpassantenempruntantunefoisetune
seulechaquetronc¸ond’autoroute,c’est`adirechacunedesareˆtesrevient`acherchers’ilexisteune
chaˆıneeule´rienneouuncycleeul´erien.
Le graphe G est connexe.
LessommetsAetFsontdedegre´2.
LessommetsBetDsontdedegre´3.
LessommetsE,C,GetHsontdedegr´e4.
LegrapheGestdoncconnexeetadmetexactementdeuxsommetsdedegre´simpairs
doncilexisteunechaıˆneeule´rienne(d’extr´emite´sBetD)surlegrapheG
donc un tel parcours est possible.
b) Citerun trajet de ce type.
☛Solution:
Leparcourscherch´eapourextre´mite´slesdeuxsommetsBetDdedegr´esimpairs.
B-A-D-E-B-C-E-G-C-H-G-F-H-D
Remarque
Onpeutve´rifierqueleparcoursestcoh´erentsaveclenombred’arˆetes.
Lasommedesdegre´sest26doncilya13areˆtesautotal.
Ilsuffitdoncdecompterlenombrede-dansleparcourspropose´...
3.On appelleMlamatirec’ddaajeccnaeeei´ocssheapgraumossel(Gate´stemisdantprordrnsl’ae-l
phabe´tique).
a)De´terminerlamatriceM.
☛Solution:
Chapitre 11:4/2egaPCABedste´Rsp´e-sujevisions
Maths en Terminale ES
(soutien et perfectionnement)
MATHS-LYCEE.FR
TESceciirroe-crexeg´
Chapitre 11:pse´s-juvesioisnR´etsdeBAC
Remarque
Onpeutcontrˆolerquelasommedescoefficientsest´egalea`lasommedesdegr´essoit26.
3
b) Ondonne la matriceM:
D´eterminer,enjustifiant,lenombredecheminsdelongueur3reliantE`aH.Pre´ciserceschemins.
☛Solution:
Lenombredecheminsdelongueur3reliantEa`Hcorrespondaucoefficientdelalignedu
sommet E (ligne 5) et de la colonne correspondant au sommet H (ligne 8)
Ilyadonc4cheminsdelongueur3reliantE`aH.
Il s’agit des chemins E-B-C-H, E-C-G-H, E-G-C-H et E-G-F-H.
Chapitre 11:4/3eRe´ivisnoss´pe-sujetsdeBACPag
Maths en Terminale ES
(soutien et perfectionnement)
MATHS-LYCEE.FR
TES-exicreocecgirre´
Chapitre 11:detsjesue´-ep´RssisvoinCAB
Partie B
Descontraintesd’organisationobligentcethommepolitique`aserendredanslavilleFapr`eslavilleA.
LegrapheGestcomple´te´ci-dessousparleslongueursenkilome`tredechaquetronc¸ond’autoroute.
De´terminer,enutilisantlalgorithmedeDijkstra,letrajetautoroutierlepluscourtpourallerdeAa`F.
Pre´ciserlalongueurenkilome`tredecetrajet.
☛Solution:
LetrajetlepluscourtpourallerdeAa`Ffait1600km.
Ce trajet est le suivant : A-B-E-G-F.
Chapitre 11:ssno-e´pe´Risivage4BACPtsdesuje4/
Maths en Terminale ES
(soutien et perfectionnement)
