[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

quotesdbs_dbs45.pdfusesText_45

[PDF] algorithme de ford plus long chemin PDF Cours,Exercices ,Examens

[PDF] Algorithme de héron Terminale Mathématiques

[PDF] Algorithme de mathématiques 2nde Mathématiques

[PDF] Algorithme de maths 1ère Mathématiques

[PDF] Algorithme de maths 2nde Mathématiques

[PDF] Algorithme de mesure d'angle 1ère Mathématiques

[PDF] Algorithme de niveau Seconde 2nde Mathématiques

[PDF] algorithme de parcours en largeur PDF Cours,Exercices ,Examens

[PDF] algorithme de parcours en profondeur en c PDF Cours,Exercices ,Examens

[PDF] ALGORITHME DE PILE OU FACE svp essayer de me faire comprendre cette algorithme 2nde Mathématiques

[PDF] Algorithme de Pythagore 2nde Mathématiques

[PDF] ALGORITHME DE PYTHAGORE ( TI-84 plus ) 2nde Mathématiques

[PDF] algorithme de recherche dextremum 2nde Mathématiques

[PDF] algorithme de recherche dans un tableau PDF Cours,Exercices ,Examens

[PDF] algorithme de recherche dichotomique PDF Cours,Exercices ,Examens