[PDF] Graphes Pour la Terminale ES 18 oct. 2002 Graphes. Pour

View - Download Graphes Pour la Terminale ES

Previous PDF

Next PDF

Graphes

PourlaT erminaleES

GroupeIREMde Luminy

PierreArnoux

FernandDidier

CatherineDufoss"e

NicolasLichiardopo l

ChristianMauduit

DominiqueProudhon

ChristianeRambaud

g6oc tobreww

Tabledesmati` 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 7g8

7gQue 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 73w

3Probl `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

iii

87SSolution desexercices77 777 77777777 777 777 777 777 777 777 777 7(◆

iv

Introduction

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Õungraphe7Une

deuxi`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 perune

th"eoriemath"ematiqueutile;elle peutaussi⇢danscertainscas⇢donnerdes id"eesdÕexercices⇢ telsque

Laterminologie a"et"ev olontairem entrestreinteaumaximum⇢pou rnepassurchargerles"el`eves

OilsÕ 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⇢ `a

Luminy7

v vi

Chapitreg

D"eÞnitionsdebase

g7gQuelques probl`emes

Commenüconsparunprobl `emer"ecr "eat if)

ExercicegUneliguedef ootbal lcon tientgSclubs7Pourdesraisonsdetemps⇢ond"ecideque chaqueclubne jouera quelamoiti "edesmatchspossibles7Comment or ganiserletournoi ?Oon pourracommencerpar" etudierlecasde&clubs7 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 spoints

reli"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 ilessegments

correspondantssecoupent⇢onvoit⇢exacte ment commepourlÕexercicepr "e c"eden t⇢quelÕexercice

propos"eestimpossible7 Remarquonsquenousavon sobtenu unr"esu ltatquinÕ"etaitnulle ment"evide nt)pourmon trer

quÕ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 entrelaPologneetla

Lituanienevoy aientpas commentfaire7

Exercice◆Probl`emedespontsdeK¬onigsberg) AuXVII Iesi`ecle⇢la villede Koenisbergcomprenait

Figureg7g)Lesp ontsdeKoeni gsbe rg

Leshabitantssouhaitaientfair eunepromenade passantune etuneseulefoissur chaque pont7

Ysontils arriv" es?

grapheobtientDon ?Commentinterpr`eteDon alorslacond itionsurlapromenade?Nousre viendrons plusloinsu rceprobl` eme7 ensim pliÞantlarepr"esentation⇢onpeut ainsitrou verplusrapidementlasolutionOouenvoir

pasdÕ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 "eeOilpeut

danslÕexercice⇢ce nÕestpastoujou rs"evid ent )danslamod"elisation propos "ee⇢lessegmentss ont

g7D"eÞnit ionsetr"esultats

Nousallons formaliserle snotionsquipr"ec`edent7

D"eÞnitiongUngrapheGOnonorient "eestconstitu"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 e7

leprobl `emedespontsdeKoe nigsberg7Cepe ndant⇢latr`es grandemajorit" edesprobl`emesquenous

doncpasutile dÕintroduire cetteterminologiee ncours7

Exempleg) 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 b

Figureg7)Legraph eG

g

Lepoin 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 ets

7Ilfau tbie nremarquerquÕil yaplusieurs

d"eÞnirunsommetOCommeonlev erra ciDdessous⇢ilnÕestpastou joursp ossible derepr" esenterun

graphesurunefe uillesans quÕily aitdecroisement7Ledes 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

Unefaü condeleprouverestlasui vante )dans G

8 etG ⇢si lÕonÞxeunsomme t⇢il yaexacte ment sommetsquineluisont pasadjacen ts;maisdansG 8

OcommedansG

6 G G G G G G G G G G G G G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ G o o o o o o o o o o O O O O O O O O O O G 3 j j j j j j j j j j j j j j j j j D D D D D D D D D D D D D D D D D 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 G Squotesdbs_dbs1.pdfusesText_1

[PDF] exercices html5

[PDF] exercices identités remarquables 3eme pdf

[PDF] exercices identités remarquables brevet

[PDF] exercices identités remarquables développement

[PDF] exercices immunologie

[PDF] exercices immunologie licence

[PDF] exercices immunologie pdf

[PDF] exercices initiation boxe francaise

[PDF] exercices internat pharmacie

[PDF] exercices ions et ph 3ème

[PDF] exercices java corrigés pdf

[PDF] exercices lentille 1s

[PDF] exercices libreoffice writer

[PDF] exercices limites de suites terminale s

[PDF] exercices logique mathématique seconde