BAC ES 2014 Graphes (sujet spécialité Amérique du Nord)

Maths-Es.Fr Maths-Lycee.Fr

Description

MATHS-LYCEE.FR un ensemble de ressources unique(cours, vidéos, QCM, méthodes, exercices et contrôles corrigés...)
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

Sujets

• Baccalauréat économique et social
• Graphe sommet-connexe
• BAC
• Dijkstra

Informations

• Publié par: MATHS-LYCEE.FR
• Publié le: 04 juin 2014
• Nombre de lectures: 81
• Langue: Français

Extrait

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)