[PDF] TD n°2 - Terminale ES Spé Les Graphes Graphes pondérés et

View - Download TD n°2 - Terminale ES Spé Les Graphes Graphes pondérés et

Previous PDF

Next PDF

TDn° 2-Terminal eES Spé-LesGraphes

TDn °2-Termin ale ESSpé

LesGraph es

Lesexer cicesidentifiésparlesymbole(c)sontintégralementcorrigésenfindeTD,pourlesautres,unlienve rslapageducorrigé

estprop osésurlesitewww.math9 3.com.

Troisièmepartie

Graphespondérésetal gorithmedeDijkstra

Exercice1.Antillesjuin2 016(c )

Destour istessontlogésdansunhôtelH .

Ungu idesouhaitefair evisiterlarégionàcestou ristesen empruntantlesroutessignalées commed 'intérêttouris- tiqueparl'o fficedutouri sme. Lestron çonsderoutequ'ilsouhaite emprun tersontre- présentéssurlegrapheci-con tre. Lelo ngdechaquear êtefigu reladistanceen kilomètres desdiffé rentstronçons. B G H C D E F 12 9 21
3 9 13 20 8 7 5 11 1.

1.a. Legu idepeut-ilempru ntertouslestronçonsd erouteenpassantunee tuneseule foissu rchacund' eux,enpartantde

l'hôteletenyrevenan t?Just ifierl aré ponse.

1.b. Legu idepeut-ilempru ntertouslestronçonsd erouteenpassantunee tuneseule foissu rchacund' eux,enpartantde

l'hôtelmaissansforc émentyreven ir?Justifierl aréponse.

2.Unmu séeestsituéenE. Détermin erlepluscourtch eminme nantdel'hôtelHaumuséeE.Justifierlaréponse.

Exercice2.Asie2016-partie3( c)

Onor ienteetonpondèrele graphe Gci-dessuspourqu'ilreprés enteunréseau d'irrigation. ACFIK BEH DGJ 2 5 3 3 2 5 3 4 5 6 2 4 5 2 1 2 3 3 5

•LesommetAcorrespondaudépartd'eau,les ommetKaubas sind'infiltration etlesautressommetsreprésententles

stationsderégulatio n. •Lesarêtesreprésententlescanauxd'irrigationetlesflèches,lesens duruis sellement. •Lapondérationdonne,enkm,lesdistancesentrelesdifférentessta tionsduréseau. www.math93.com/M.Duffaud1/6

TDn° 2-Terminal eES Spé-LesGraphes

Exercice3.Centresétrangers2 016

Unecomp agnieaérienneutilisehuitaé roportsquel'onnommeA,B,C,D,E,F,GetH. Entrecertai nsdecesaéroports,lac ompag nieprop osedesvolsda nslesdeuxsens. Cettesituatio nestreprésentéeparlegraphe Γci-contre,danslequel: •lessomme tsreprésententlesaér oports, •lesarête sreprésententlesliaiso nsassuréesdanslesdeuxsensparla compagnie . Lesarêt essontpondéréespar lecoûtdechaq uevol,exprimé eneuro s. Unvo yageurpartantdel'aéropo rtAdoitserendreàl'aér oport G. Enutili santl'algorithme deDijkstra,déterminerletrajetle moinscher. A B C D E F G H 40
100
45
110
50
120
60
50
40
55
80
90

Réponses

Lech eminlemoinscheres tde195 e:A

45
-→E 40
-→D 60
-→C 50
-→G Voirlacor rectio ndétailléesurwww.math93.com

Exercice4.PolynésieSeptembre 2015(c)

Unr éseaudenavettesgra tuites estmisenplace

entredespa rkingssitués auxabordsdelavilleet lesprinc ipauxsitesdelaville.

Legr apheci-contreind iquelesvoiesetlestemps

desliai sons,enminutes,entrecesdiff érents sites. A B C D E F GP 55
79
68
354
9 6 4 8 5 7 10

1.Peut-onenvisagerun itinérairequirelieraitlepa rkingP àlaga reGendesservant uneet uneseulefo istouslessites?

2.Peut-onenvisagerun itinérairequiemprunteraitu neetun eseulefois touteslesvoies?

3.Détermineruntrajetdeduréemin imale pourserendredupark ingPàla ga reG .

www.math93.com/M.Duffaud2/6

TDn° 2-Terminal eES Spé-LesGraphes

Exercice5.Métropole2015(Parti e3)

Uncl ubalpinsouha iteproposeràse smembresdesrandonnéesdepl usieursjoursdanslesAlpes.Àc eteffet,hui trefuges

notésA,B, C,D,E,F ,GetHont étésélectionnés .

Leg rapheGdela partie Apermetdevisualise rle sdifférentsitinérai respo ssibles,lessommetsreprésentantlesref ugesetles

arêtesschématisant touslessentiersderandonnéebalis éslesrelia nt. Leg rapheGestcomp létéci-dessousparlalongueur enkilomètresdechacundes sentiers. A B C D E F G H 12 14 16 11 21
9 11 16 10 10 13 10 Lecl ubalpindésir eaussiproposer àsesmembresl'itiné rairel eplusc ourtreliantAà H. Déterminercetitinéraireeten préciserl alongueurenkilomètres.

Réponses

Lech eminlepluscourtes tde32k ilomètres:A

12 -→B 9 -→F 11 -→H.

Voirlacor rectio nsurwww.math93.com

Exercice6.Asie2015(Partie3)

Laco opérativeLAFRUITIEREcollectelela itde7exploitationsdemon tagne. Lasituationgéographiquees trepré sentéepar

legr apheci-dessous,notéG L .LacoopérativeestsituéeausommetA,lesautressommetsB,C,D, E,F,Get Hreprésen tentles différentesexploitations;lesar êtesreprésententleréseauroutierr eliantcesexplo itations.

Lesarêt essontpondéréespar lesdistance sentrelesexploitations,expriméesenkilo mètres.Lacoopérativedo itc ollecterdu

laitprovena ntdel'exploitationD;quele stleplusco urtparcourspourserendre deAàD?Justi fier. AB C D E F G H 19 6 10 13 20 7 7 6 25
15 13 5 14 12 8

Réponses

Lech eminlepluscourtes tdelon gueur31km:A

10 -→F 8 -→H 13 -→D Voirlacorr ection détailléesurwww.math93.com www.math93.com/M.Duffaud3/6

TDn° 2-Terminal eES Spé-LesGraphes

Correction

CorrectionGraphespondéréset algorithmedeDijkstra

Correctiondel'exercice1:Antilles2016

Destour istessontlogésdansunhôtelH .Unguidesouh aitefairevisite rla régionàcestouriste sen emprunt antlesroutessignaléesco mmed' intérêt touristiqueparl'officedutourisme .Lestron çonsderoutequ'ilsouha iteem- pruntersontreprése ntéssurlegra pheci-contre.Lelongdechaquearêtefi- gureladist anceen kilomètresdesdifférents tronço ns. B G H C D E F 12 9 21
3 9 13 20 8 7 5 11

1.1.a .Le guidep eut-il empruntertousl estronçonsderouteenpa ssantuneetuneseulefois surchacun d'eu x,enpar-

tantdel'hôteleten yrevenant?Justifi erlaréponse .

Rechercheruncheminquipartd' unsomm et,quipassepartou tesles arêtesuneseul efoisetquirev ientau sommetde

départ,c'estcherche runcycleeulérie ndanslegraphe.D'aprèslethéo rèmed' EULER,ungrapheconnexepossèdeuncycle

eulériensietseulem entsitousl esso mmetssontdedegr éspairs.

•LegrapheestconnexecarlachaîneBGEFCDHparexemplecontienttous lessommetsdugr aphe(n onorienté).

•Oncherchelesdegrésdessommets:

SommetsHBCDEFG

Degrés3243244

Ilya deux som metsdedegré simpairs,donciln'yapa sdec ycleeulériendansceg raphe. d'eux,enpartantd el'hôt eletenyrevenant.

1.b. Leguid epeut-ilempruntertou slestronçonsderouteenpassantuneetuneseulefoissur chacund'eux,en partant

del' hôtelmaissansforcém entyrevenir ?Justifierlaréponse.

Leg uidesouhaitepart irdel'hôteletparcouri rtouslestronçonsderoute sansforc émentreveniràl' hôtel;il s'agitalorsde

trouverunechaîneeuléri enneda nscegraphe.

D'aprèslethéorèmed' EULER,ungrapheconnexecontientunechaîneeulériennesietseulementsiexa ctementzéro ou

deuxdesesso mm etssontdede grésimpairs.C'estleca sicicarpourcegrapheconnexe,seulslessommetsHetDsontde

degrésimpairs;on peutdonctrouverunparcour sparta ntdeHetar rivantàDpassantuneetuneseule fo ispa rchaque

tronçonderoute.

Voiciuntelpar cours:

H-B-G-C-H-D-C-F-G-E-F-D

2.Un musée estsituéenE.Dét erminerle pluscourtchemi nmenantdel'hôtelH aumuséeE.Justifierlarépon se.

Onva déter minerlecheminlepluscourtrelian tHàEe nutilisantl'alg orithmedeDijkstra:

DépartBCDEFGOnga rde

H12H20H9H∞∞∞D(H)

D(9)12H 20H∞∞B(H)

17D30D

B(12)17D ∞30D25BC(D)

C(17)∞30D25B

28C24CG(C)

G(24)33G 28CF(C)

F(28)33G

31F E(F)

Leche mindelongueurmi nimale 31kmentreHetEest:H

9 -→D 8 -→C 11 -→F 3 -→E www.math93.com/M.Duffaud4/6

TDn° 2-Terminal eES Spé-LesGraphes

Correctiondel'exercice2:Asie2016

Onor ienteetonpondèrele graphe Gci-dessuspourqu'ilreprése nteunréseau d'irrigation. ACFIK BEH DGJ 2 5 3 3 2 5 3 4 5 6 2 4 5 2 1 2 3 3 5

•LesommetAcorrespondaudépartd'eau,leso mmetKaubas sind'infiltration etlesautressommetsreprésententles

stationsderégulatio n. •Lesarêtesreprésententlescanauxd'irrigationetlesflèches,lesens duruis sellement. •Lapondérationdonne,enkm,lesdistancesentrelesdifférentessta tionsduréseau.quotesdbs_dbs20.pdfusesText_26

[PDF] exercices graphes orientés tes

[PDF] exercices graphes probabilistes

[PDF] exercices graphes probabilistes tes

[PDF] exercices imparfait ce2 2eme groupe

[PDF] exercices imparfait ce2 3ème groupe

[PDF] exercices imparfait ce2 cm1

[PDF] exercices imparfait ce2 en ligne

[PDF] exercices imparfait ce2 imprimer

[PDF] exercices imparfait ce2 pdf

[PDF] exercices imparfait cm1

[PDF] exercices imparfait verbes reguliers

[PDF] exercices intervalles de confiance

[PDF] exercices intervalles de r seconde

[PDF] exercices la tension électrique 4ème

[PDF] exercices langage soutenu courant familier