18 oct 2002 · De même, on a choisi de parler de graphes probabilistes l`a o`u les probabilistes parlent de Solution de l'exercice 11 : Corrigé dans le texte
Previous PDF | Next PDF |
[PDF] GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
1 Représenter la situation par un graphe probabiliste de sommets A et B 2 Écrire la matrice de transition M de ce graphe en prenant les sommets
[PDF] Corrigé Exercice 3 Centres Étrangers Bac ES - Freemaths
On a donc P0 = (0,65 0,35) 1 a Dessiner le graphe probabiliste (G) de sommets A et B b Écrire la matrice de transition M associée
[PDF] Exercices : graphes probabilistes - Normale Sup
Exercices : graphes probabilistes Exercice 1 (Nouvelle-Calédonie, Novembre 2006, 5 points) Une association sportive propose à ses adhérents de pratiquer
[PDF] CORRIGÉ DEVOIR SURVEILLÉ N° 5 TERMINALE ES spé
CORRIGÉ DEVOIR SURVEILLÉ N° 5 TERMINALE ES spé EXERCICE 1 : Dans le 1 a) Le graphe probabiliste de sommets A et B décrivant la situation :
[PDF] Baccalauréat ES spécialité Index des exercices avec des graphes
Dans toute la suite de l'exercice, n désigne un entier naturel non nul Représenter la situation par un graphe probabiliste de sommets A et B en bout de piste en A et doit se rendre le plus rapidement possible au terminal situé au point T
[PDF] graphes
1 4 corrigés exercices 2 graphe connexe, trajet Eulérien et algorithme d'Euler 19 2 1 activités 5 graphe probabiliste, matrice de transition, état stable 47 5 1 activités La classe de Terminale d'Arthur est en voyage sco- laire en
[PDF] PDF 2 - Maths Bordeaux
C Exercices 25 D Corrigés des exercices Extrait du programme de spécialité de Terminale ES BO hs n°4 du 30 d'un graphe probabiliste à 2 ou 3 sommets
[PDF] Exercice 1 : Graphe probabiliste, matrices 10 point(s) A B 0,5 0,5 0,2
Terminale ES spécialité : ds graphes corrigé Exercice 1 : Graphe probabiliste, matrices 10 point(s) A B 0,5 0,5 0,2 0,8 1 a) Le graphe probabiliste ci-dessus
[PDF] Graphes Pour la Terminale ES
18 oct 2002 · De même, on a choisi de parler de graphes probabilistes l`a o`u les probabilistes parlent de Solution de l'exercice 11 : Corrigé dans le texte
[PDF] Mathémathiques au Lycée - Perpendiculaires - Free
Mathématiques en Terminale ES 1 3 Exercices Corrigé du devoir maison n° 2 : Suites 52 7 Graphes 10 2 Cas général : graphes probabilistes à p états
[PDF] graphisme grande section ? imprimer
[PDF] graphisme maternelle eduscol
[PDF] graphisme maternelle pdf
[PDF] graphisme petite section pdf
[PDF] graphomotricité maternelle
[PDF] graphothérapie exercices gratuits
[PDF] gratification stage élève avocat 2017
[PDF] gravitacion y tercera ley de kepler
[PDF] gravitation et poids 3ème controle
[PDF] gray's anatomie pour les étudiants 2ème édition pdf
[PDF] gray's anatomie pour les étudiants 3ème édition pdf
[PDF] gray's anatomie pour les étudiants download
[PDF] gray's anatomy pour les étudiants
[PDF] gre ets
Graphes
PourlaT erminaleES
GroupeIREMde Luminy
PierreArnoux
FernandDidier
CatherineDufoss"e
NicolasLichiardopo l
ChristianMauduit
DominiqueProudhon
ChristianeRambaud
g6oc tobrewwTabledesmati` eres
Introductionv
gD" eÞnitionsdebaseg g7gQu elquesprobl`emes7777 77777777777777 777 777 777 777 777 777 g g7D" eÞnitionsetr"esultats77777 77777 777777777777777 777 777 777 7◆ g77Sous Dgraphes7777777777 777 777 77 777 777 777 777 777 777 S g77SGraphes orient" es7777777777777777777 777 777 77 777 777 76 g7◆Que lquesexercicessu ppl"ementaires777777777777777 7777777777777( g73Com pl"ementspourlesenseignants7777777 77777 777777777 7777777gg g737gUn peu determinologie77777 777777 77777 777 777 777 777 77gg g737D" emonstrationduth"eor`emedÕEuler777777 777777 777777777777gg g737◆Chaine seul"erie nnesdanslesgraphesorient"es777777777777 777777 g g7373Uneapp licationamu sante)legrap hedesmots777777777 777 777 77g◆ g737SGraphes hamiltonien s7777777777777777777 777 777 777 777 g◆ g7378Graphes planaires7 777777777777 777 777 777 77 777 777 777 g3 g7SSolution desexercices77 777 77777777 777 777 777 777 777 777 777 7g87gQue lquesprobl`emes77777 77777777777777 777 777 777 777 777 77 w
7R" ecapitulation)lesd"eÞnitionsetr"esu ltats77 777777 777777777777 7777
7◆Que lquesexercicessuppl "ementaires777777777777777 7777777777777◆
73Comp l"ementspourlesenseignants7777777 777777 777777777 777777S
737gQue lquesapplicationsdesprobl`emesde comptage77 777 7777777777S
737DÕau tresmatricesenth "eoriede sgraphes7 77777777777777 7777778
7SSolution desexercices77 777 77777777 777 777 777 777 777 777 777 76
◆Probl` emesdecoloriage◆w ◆7gQu elquesprobl`emes7777 77777777777777 777 777 777 777 777 777 ◆w ◆7R" ecapitulation)lesd"eÞnitionsetr"esultats 77 777777 777777777777 7777◆3 ◆7◆Que lquesexercicessuppl "ementaires777777777777777 7777777777777◆& ◆73Comp l"ementspourlesenseignants7777777 777777 777777777 777777◆6 ◆737gNomb redestabilit"e77 777777 77777777777 777 777 777 777 7◆6 ii ◆737Major ationsdunombrechromatique 777 77777777 777777777777 ◆( ◆737◆Leth "eor `emedes3couleurs7777777777 777777777 777 7777773w ◆7SSolution desexercices77 777 77777777 777 777 777 777 777 777 777 73w3Probl `emesdepluscourtchemin33
37gUnp robl`e me77777777777777 77 777 777 777 777 777 777 777 77 733
37R" ecapitulation)lesd"eÞnitionsetr"esu ltats77 777777 777777777777 77773S
37◆Que lquesexercicesadditionne ls777777777777777777 77777777777738
373Comp l"ementspourlesenseignants7777777 777777 777777777 7777773&
3737gCet algorithmeestDile?cace?7 77 777 777 777 777 777 777 777 77 36
3737Cet algorithmeestDilcorrect? 777777 77777 777 777 777 777 777 736
3737◆Que lquesautresprobl`emes7 77777777 777777777777777777 73(
37SSol utiondesexercices7 777 777777777 777 77 777 777 777 777 777 773(
SGraphes" etiquet" esSg
S7gQue lquesexemples777777 77777777777 777 777 777 777 777 777 77 Sg S7g7gLej eud ulabyrinthe777 777777 77777777777777 777 777 777 Sg S7g7Und igicode7 777777777 777 77 777 777 777 777 777 777 777 7S S7g7◆Reconn aissancedemod`eles77777777 77777 777777777777 777 S◆ S7R" ecapitulation)lesd"eÞnitionsetr"esu ltats77 777777 77777777777 77777S3 S7◆Que lquesexercicessu ppl"ementaires77777777777777 77777777777777SS S73Comp l"ementspourlesenseignants7777777 777777 777777777 777777S6 S737gTerminol ogie77777777 777 777 77 777 777 777 777 777 777 77S6 S737Historique 77777 777 777 777 777 777 777 77 777 777 777 777 7S( S737◆Express ionsr"eguli`ereset langagesrationnels7777777777777777777 8g S7373Aut omatesd"eterministeset nond"eterministes777777777777 777 7778 S737SQu elques"el"ementsde lapreuveduth"eor`emedeKleene7777777 777 778◆ S7378Uner "ecr "eationmath"ematique)lessuitesautomatiques777 7777777778& S737&Un peu debourbakisme7777 777777 77777777 777 777 777 777 86 S7376Unehi "erarc hiedelangages777777777777 777 77777 777 777 77&w S737(Uneautr eg" en"eralisation )lesautomatesavecsortie77777777777777 &w S737gwQue lquesutilisationsdesautomates777777 77777 777 777 777 777 &g S7SSol utionsdesexercices 777777777 77777777777 777 777 777 777 777 &8Graphespr obabilistes&S
87gQue lquesexercices77 777777777777777777777 77 777 777 777 777 &S
87R" ecapitulation)lesd"eÞnitionsetr"esultats 77 777777 777777777777 77776w
877gG" en"eralit"es)graphesprobabilistes`ap"etats777 777 777 777 777 777 76w
877Uncas particulier) lesgraph esprobabilistes `a "etats77 777777777 776
877◆Casg "en" eral)"evolutionversun"etat stable7 777777777777777 77776S
87◆Qu elquesexercicesadditionn els77777777777777777 77777777777776S
873Comp l"ementspourlesenseignants77777777 77777 777777777 7777776&
8737gTerminol ogie77777777 777 777 77 777 777 777 777 777 777 776&
8737Ret oursurlecasdedeux" etats)v aleurspr opres ⇢vecteurspr opre s77777776&
8737◆Leth "e or`emedePerronDFrobenius777777 777 777777777777777766
87373Application auxmatric esstochast iques77777777777 77777777777(g
iii87SSolution desexercices77 777 77777777 777 777 777 777 777 777 777 7(◆
ivIntroduction
Cetextepr "ese ntelapartieÒgraphesÓdelÕoptiondemath"ematiqu esdeterminaleES7 Lebutdecette desgraphes ⇢maisdemontre rcommentlÕ utilisationj udicieusedÕungraphepeut rendrecertains probl`emesconcretsaccessibles`aun raisonneme ntmath"ematique7 IlnÕest doncpasque stion⇢commecela estb ienpr"ecis"edansle programme⇢defai reuncours formel;cepartiDpris sereß `etedan slepr"esent texte7Chaquechapitr ed"ebutedonc parquelques probl`emesdontlar"esolutionest facilit"e epar laconsid"erationdespropri"et"es dÕungraphe7Unedeuxi`emepartie⇢courte⇢donnelesd "eÞnitionset propri"et"esn "ecessairesp oure nseignercecours7
Unetrois i`emepartiedonnedÕautresexercicesp ossibles⇢a vecquelques explications⇢enparticulie r
EnÞn⇢unequatri`em epartiedechaqu echapitre⇢intitul"eeCompl"ementspourlesenseignants⇢
estconsacr"e e`adesconnaissancesplusapprofond iespermettant dÕavoiruncertainrec ul⇢etde comprendrelesraisonspourlesquelleson ach oisidÕin troduireces notions7Insistonssurl efait quÕellenÕestabs olumentpasn"ecessai repourlÕenseignementdelÕoption⇢ etquÕel lene faitpasdutout partie duprogramm e?Ellepeut parcontredonnerdespistespour lesTPE ⇢enmontran tnombred eth`emesÒpratiquesÓ`ap roposdesquelsonpeu td"evelop peruneth"eoriemath"ematiqueutile;elle peutaussi⇢danscertainscas⇢donnerdes id"eesdÕexercices⇢ telsque
Laterminologie a"et"ev olontairem entrestreinteaumaximum⇢pou rnepassurchargerles"el`evesOilsÕ agitdÕuneoptionde3H? 7Enparticulier⇢n ousavonsc hoisi decommence rparlesgraphes non
orient"es⇢plussimplesaud"epart⇢etdÕi ntroduire quandla situation ledemandelesgraphesorient"es⇢
Nousreviendrons surcepointdan slesc hapitre sconcern"es7 signaleraux" el` eveslevocabulairecourammentutilis"edansce sdom aines⇢maisseullevoc abulaire donn"edansleprogrammeest exigible aubaccalau r"eat7 Letextea "et "er "edig"eentremarsetoctobr ewwparlegroupedelÕIREMdÕAixDMarseille⇢ `aLuminy7
v viChapitreg
D"eÞnitionsdebase
g7gQuelques probl`emesCommenüconsparunprobl `emer"ecr "eat if)
ExercicegUneliguedef ootbal lcon tientgSclubs7Pourdesraisonsdetemps⇢ond"ecideque chaqueclubne jouera quelamoiti "edesmatchspossibles7Comment or ganiserletournoi ?Oon pourracommencerpar" etudierlecasde&clubs7 AvecgSclubs⇢iles tassez di?cilede d"emarrerletrav ailsurceprobl`eme ⇢`a causedelataill e desdonn "ees7Avec&clubs⇢onestrapide mentamen"e`au ndessin o`uchaqueclub estr epr"esen t"epar unpoin t⇢eto`uonreliepar untraitdeuxclubs quidisputentu nmatc h7Uneb onnei d"ee estalors decompterl enom bredetraits⇢ cÕestD`aDdirelenombre dematch squiseront jou"es;commechaque traitadeuxex tr"em it"e s⇢cÕestaussilamoiti"edunombredeparticipations)sichacun des&clubs joue◆matchs ⇢ily agparticipations⇢dont g degSc lubs ⇢sichaqueclubjouelamoiti"ed esmatchs possibles⇢soit&⇢ildoi tyavoir gS?& matchs)lÕorganisationdÕuntelt ournoinÕestpas possib le⇢pourdepures raisonsarithm"etiques7On voit que⇢
quÕellesjouenttoutesun nombreimpairdematchs7 LÕid"eeessentielleestdere pr"esenterlasituat ionparunde ssin particulier⇢ungraphe)de spointsreli"espardestraits7Dan scedes sin⇢l asituationg"eom"e triquenÕest pasimportan te⇢cequicompte
ExerciceCommenttracer Ssegmentssurunefeuille⇢detellem ani` erequechaque segmenten coupeexactement◆au tres? SilÕon pense`arepr" esenterchaque segmentpar unpoint⇢et`arelierpointss ilessegmentscorrespondantssecoupent⇢onvoit⇢exacte ment commepourlÕexercicepr "e c"eden t⇢quelÕexercice
propos"eestimpossible7 Remarquonsquenousavon sobtenu unr"esu ltatquinÕ"etaitnulle ment"evide nt)pourmon trerquÕunprobl`eme estpossible⇢ilsu?tdÕene xhibe runesolution;ilesteng"en" eralbienplu sdi?cile
ded" emontrerquÕunprobl`emeestimpossi ble⇢etcelane peutsefairesansunraisonneme nt7 Continuonsparleprobl`e mesuivant⇢ quiest unclassique)propos"eeng&◆8parLe onhartEuler⇢cÕestleprem ierprobl `emedelath"eoriedesgrap hes7IlestaujourdÕhuipar faitement r"e solu⇢mais
g lesh abitantsdeKoenigsbergOaujourdÕh uiKali ningrad⇢villerusseenclav"ee entrelaPologneetlaLituanienevoy aientpas commentfaire7
Exercice◆Probl`emedespontsdeK¬onigsberg) AuXVII Iesi`ecle⇢la villede Koenisbergcomprenait
Figureg7g)Lesp ontsdeKoeni gsbe rg
Leshabitantssouhaitaientfair eunepromenade passantune etuneseulefoissur chaque pont7Ysontils arriv" es?
grapheobtientDon ?Commentinterpr`eteDon alorslacond itionsurlapromenade?Nousre viendrons plusloinsu rceprobl` eme7 ensim pliÞantlarepr"esentation⇢onpeut ainsitrou verplusrapidementlasolutionOouenvoirpasdÕorien tation7PourdÕautres⇢ilest indispensabledÕavoir uneorientationsurlegraphe )leplan
sensdecirculationsera bienplusapp r"eci"e delÕautomobilist e7Uneautreutilisationc lassiquedes avantdÕ"eleverlesm urs7Onpeutrepr"esenterle projetp arungraphedontlessomm etssontle s correspondanteposs`edeuneorientationn aturelle7 Unequestionimp ortantee stcelleduchoixdugrap heassoci" e`aunesituati ondonn "eeOilpeutdanslÕexercice⇢ce nÕestpastoujou rs"evid ent )danslamod"elisation propos "ee⇢lessegmentss ont
g7D"eÞnit ionsetr"esultatsNousallons formaliserle snotionsquipr"ec`edent7
D"eÞnitiongUngrapheGOnonorient "eestconstitu"edÕunen sembleS={s g ⇢s ⇢777⇢s n }depoint s appel"essommets⇢etdÕu nensem bleA={a g ⇢a ⇢777⇢a m i sont associ"esdeux"el"ementsdeS⇢app el"essesextr"emit"es⇢etquenousn oterons [s j ⇢s k i 7 uneboucle7 Unepremi `eremani`eredÕ"evalu erlacomplicationdÕungrapheestde compterlenombredeses sommets;lesmath"ematiciens ontdonn"e`ac enombreunnomparticulierOquelÕonretrouve dans dÕautresdomaines⇢parexem pleenth"eoriedesgroupes) D"eÞnitionLÕordredÕungrapheestle nombredeses sommets7 g ⇢s ]⇢ondit queles sommetss g ets sont g ets sontdit sadjacents7Lorsqu es g =s ⇢ondi tqueaestune boucle7 sansboucl e7leprobl `emedespontsdeKoe nigsberg7Cepe ndant⇢latr`es grandemajorit" edesprobl`emesquenous
doncpasutile dÕintroduire cetteterminologiee ncours7Exempleg) Consid"eronslegrapheG
g dÕordre3d"eÞnip ar)SoitS={s
g ⇢s ⇢s ⇢s 3 associ"es[s g ⇢s g ]⇢[s g ⇢s ]⇢[s g ⇢s ]⇢[s g ⇢s ]⇢[s ⇢s ]7Unerepr "esen tationpossibledecegrapheest) s 3 s s g s a d e c bFigureg7)Legraph eG
gLepoin ts
3 extr"emit"es⇢[s g ⇢s g ets sontadjacents⇢ain siques g ets Ungraphe nÕestriend ÕautrequÕundessin form"edepoints jointspardestraits⇢et ilestplu s facilederepr "ese ntercedessin⇢quededonnerlesen semblesSetA⇢etles extr" emit" esdechaque g ets parun traitrelian tlespointsre pr"esentan ts g ets7Ilfau tbie nremarquerquÕil yaplusieurs
d"eÞnirunsommetOCommeonlev erra ciDdessous⇢ilnÕestpastou joursp ossible derepr" esenterungraphesurunefe uillesans quÕily aitdecroisement7Ledes sindoitdon cclairement iden tiÞerl es
sommets7 Exemple) Onare pr" esent"edansledessinquisuituncertainnombrede graphes7Iles tfacile devoir queG etG ⇢dÕun epart⇢G 3 etG S G 8 etG 6 8 etG