Sujet par thèmes : Sujets de spécialité : graphes

De
Decouvrez les TP et les cours 2009/2010 pour la classe de terminale ES.
Publié le : jeudi 1 janvier 2009
Lecture(s) : 22
Source : sarmate.free.fr
Nombre de pages : 42
Voir plus Voir moins

Exercice1
SoitlegrapheGjointenannexeconstituédessommetsA,B,C,D,E,FetG.
1. Quelestsonordreetledegrédechacundesessommets?
2. Reproduiresurlacopieetcompléterletableaudesdistancesentredeuxsom-
metsdeG:
Distance A B C D E F G
A X
B X X
C X X X
D X X X X
E X X X X X
F X X X X X X
G X X X X X X X
Endéduirelediamètredecegraphe.
3. a. Donnerunsous-graphecompletd’ordre3deG.
Qu’endéduirepourlenombrechromatiquedeG?
b. ProposerunecolorationdugrapheGetendéduiresonnombrechroma-
tique.
4. DonnerlamatriceMassociéeàG(vousnuméroterezleslignesetlescolonnes
dansl’ordrealphabétique).
5. EnutilisantlamatriceM donnéeenannexe1,déduirelenombredechaînes2
delongueur2partantdeAsansyrevenir.
1Annexe1:exercice2
B
C
A F
D
G
E
 
3 1 1 0 2 1 0
 1 3 0 1 2 1 1 
 1 0 3 1 1 2 1 
 2M =0 1 1 2 1 1 1
 
 2 2 1 1 4 0 0
 
 1 1 2 1 0 3 2
0 1 1 1 0 2 2
Exercice2
I-Unmuséeestconstituéde9sallesnotéesA,B,C,D,E,F,G,HetS.
Leplandumuséeestreprésentéci-dessous:
H B C
S G E
F
D H
Ainsi, un visiteur qui se trouve dans la salle S peut atteindre directement les salles
A,BouG.S’ilsetrouvedanslasalleC,ilpeutserendredirectementdanslasalleB,
maispasdanslasalleF.
Ons’intéresseauparcoursd’unvisiteur danscemusée. Onnesepréoccupe pasde
la manière dont le visiteur accède au musée ni comment il en sort. Cette situation
peutêtremodéliséeparungraphe,lessommetsétantlesnomsdessalles,lesarêtes
représentantlesportesdecommunication.
21. Dessinerungraphemodélisantlasituationdécrite.
2. Est-ilpossibledevisiterlemusée,enempruntantchaqueporteunefoisetune
seule?
Justifierenutilisantunthéorèmeducourssurlesgraphes.
3. Pour rompre une éventuelle monotonie, le conservateur du musée souhaite
différencier chaque salle de sa ou des salles voisines (c’est-à-dire accessibles
paruneporte)parlamoquetteposéeausol.Quelestlenombreminimumde
typesdemoquettesnécessairespourrépondreàcesouhait?Justifier.
II-Onnote M lamatriceà9ligneset9colonnes associéeaugrapheprécédent,en
convenantdel’ordresuivantdessallesS,A,B,C,D,E,F,G,H.Legraphen’étantpas
orienté,commentcelasetraduit-ilsurlamatrice?
III-Ondonnelamatrice:
 
18 12 11 2 20 12 6 12 12
 12 20 3 6 11 20 5 18 5 
 11 3 16 0 19 3 8 4 12 
 2 6 0 3 1 7 1 4 1 
 4M =20 11 19 1 31 9 11 12 19
 
 12 20 3 7 9 28 9 20 9
 
 6 5 8 1 11 9 9 8 9 
 12 18 4 4 12 20 8 20 6
12 5 12 1 19 9 9 6 17
1. Combieny-a-t-ildecheminsquien4étapes,partentdeDetreviennentàD?
2. Combien y-a-t-ildechemins quien 4étapes, partentdeSetreviennent àC?
Lesciter.
3. Est-iltoujourspossibledejoindreen4étapesdeuxsallesquelconques? Justi-
fier.
Exercice3
DanslavilledeGRAPHE,ons’intéresseauxprincipalesruespermettantderelier
différents lieux ouverts au public, à savoir la mairie (M), le centre commercial (C),
labibliothèque (B),lapiscine(P)etlelycée(L).Chacundeceslieuxestdésignépar
soninitiale.Letableauci-dessousdonnelesruesexistantentreceslieux.
B C L M P
B X X X
C X X X
L X X
M X X X X
P X X
1. Dessinerungraphereprésentantcettesituation.
2. Montrer qu’il est possible de trouver un trajet empruntant une fois et une
seuletouteslesruesdeceplan.Justifier.Proposerunteltrajet.
Est-il possible d’avoir un trajet partant et arrivant du même lieu et passant
unefoisetuneseulepartouteslesrues?
3D
3. Dimitri habite dans cette ville; le
9
graphe ci-contre donne le nouveau
B
plan du quartier avec les sens de cir- 5
culationdanslesdifférentesruesetle 3 1110
tempsdeparcoursentrelesdifférents
C5lieux. P
44 9
L
10M
Dimitri désire prendresa voiture pour se rendrede son domicile noté D jus-
qu’àlapiscine.
Proposer un trajet le plus court possible lui permettant de se rendre de son
domicileàlapiscine.
Laréponseproposéedevraêtrejustifiéeparunalgorithme.
Exercice4
Unlivreur d’unesociétédeventeàdomiciledoit,danssonaprès-midi,charger
soncamionàl’entrepôt notéA,livrer cinqclients quenousnoteronsB,C,D,EetF,
puisretourneràl’entrepôt.Leréseauroutier,tenantcomptedessensdecirculation,
etlestempsdepar-cours(enminutes)sontindiquéssurlegrapheGsuivant:
B
A
32
3
6
9F4
9 6
3 6E
4
2 C
D 2
1. DonnerlamatriceMassociéeaugrapheG.
Onutiliseralemodèlesuivant:
A B C D E F
A
B
C
D
E
F
62. OndonnelamatriceM :
 
8 6 6 3 4 6
 19 11 12 9 6 16 
 
36 28 23 22 18 34 6M = 
37 24 25 17 15 31
 
 15 12 9 10 8 15
28 22 19 15 15 26
4Ons’intéresseauxcheminspartantdel’entrepôtAetseterminantenA.
a. Combienexiste-t-ildecheminsdelongueur6reliantAàA?
b. Citerceschemins.
c. Parmiceuxquipassentpartouslessommetsdugraphe,lequelminimise
letempsdeparcours?
d. Quelleconséquencepeuttirerlelivreurdudernierrésultat?
3. Audépartdesatournée,lelivreurachoisidesuivrel’itinéraireleplusrapide.
Malheureusement, leclientCn’estpasprésentaupassagedulivreuretcelui-
ci décide de terminer sa livraison par ce client. Indiquer quel est le chemin
le plus rapide pour revenir à l’entrepôt A àpartir deC. La réponse devra être
justifiée.
Exercice5
Un concert de solidarité est organisé dans une grande salle de spectacle. À ce
concertsontconviésseptartistesderenomméeinternationaleLutherAllunison(A),
John Biaise (B), Phil Colline (C), Bob Ditlâne (D), Jimi Endisque (E), Robert Fripe
(F) et Rory Garaguerre (G). Les différents musiciens invités refusant de jouer avec
certainsautres,l’organisateurduconcertdoitprévoirplusieurspartiesdespectacle.
Les arêtes du grapheΓ ci-dessous indiquent quels sont les musiciens qui refusent
dejouerentreeux.
B
AC
G
D
E F
GrapheΓ
1. Déterminer la matrice associée au graphe Γ (les sommets deΓ étant classés
dansl’ordrealphabétique).
′2. Quelleestlanaturedusous-graphedeΓ constituédessommetsA,E,FetG?
Quepeut-onendéduirepourlenombrechromatiqueχ(Γ)dugrapheΓ?
3. QuelestlesommetdeplushautdegrédeΓ?
Endéduireunencadrementdeχ(Γ).
4. Après avoir classé l’ensemble des sommets deΓ par ordre de degré décrois-
sant,colorierlegrapheΓfigurantenannexe.
5. Combiendepartiesl’organisateurduconcertdoit-ilprévoir?
Proposerunerépartitiondesmusicienspourchacunedecesparties.
5Exercice6
Unegrandesurfaceestconçuedetelle façonquesixsecteurs(alimentation, hi-
fi, etc.) notés A, B, C, D, E, F sont reliés par des allées selon le graphe ci-dessous.
D C
E A B F
1. a. Recopieretcompléterletableausuivant:
Secteur A B C D E F
Degré
b. LegrapheG estconnexe.Pourquoi?
2. Un visiteur désire parcourir l’ensemble des allées en ne passant par celles-ci
qu’uneseulefois.
a. Démontrerquesonsouhaitestréalisable.
b. Donnerunexempled’untelparcours.
3. Le directeur désire associer chaque secteur à une couleur de sorte que deux
secteurs(sommets)neportentpaslamêmecouleur.
a. Démontrerquelenombrechromatiquen dugraphevérifien>4.
b. Expliquerpourquoin65.
c. Proposeruncoloriagedugraphepermettantdedéterminersonnombre
chromatique.
4. Une famille se trouve dans le secteur E et doit se rendre dans le secteur F.
Cela étant, les parents connaissent suffisamment les allées pour savoir que,
pourchacuned’elles,lesenfantsnerésistantpas,illeurfaudradébourserune
somme(eneuros)préciséedanslegrapheci-dessous.
D 40 C
1010 10
40 7020
E 30 A 40 B 20 F
(AB=40;AC=10;AD=10;AE=30;BC=20;BF=20;CD=40;CE=40;DE=
10;DF=70)
Indiquerunechaînequiminimiseladépensedecettefamille.
Exercice7
Un théâtre propose deux types d’abonnements pour une année : un abonne-
ment A donnant droit à six spectacles ou un abonnement B donnant droit à trois
spectacles.
6Onconsidèreungroupede2500personnesquis’abonnenttouslesans.n étantun
entiernaturel,onnote:
a laprobabilitéqu’unepersonneaitchoisiunabonnementAl’annéen;n
b laprobabilitéqu’unepersonneaitchoisiunabonnementBl’annéen;n
P lamatrice[a b ]traduisantl’étatprobabilisteàl’annéen.n n n
Tous les ans 85% des personnes qui ont choisi l’abonnement A et 55 % des per-
sonnes qui ont choisi l’abonnement B conservent ce type d’abonnement l’année
suivante.Lesautrespersonneschangentd’abonnement.
1. On suppose que, l’année zéro, 1500 personnes ont choisi l’abonnement A et
1000l’abonnementB.Déterminerl’étatinitialP =[a b ].0 0 0
2. a. Tracerungrapheprobabilistetraduisantlesdonnéesdel’énoncé.
b. DéterminerlamatricedetransitionMdecegraphe.
c. Endéduirelenombred’abonnéspour chaquetyped’abonnement l’an-
néeun.
3. Soit P=[x y]l’état stable,où x et y sont deuxnombresréels positifs tels que
x+y=1.
Justifierquex et y vérifientl’équation x=0,85x+0,45y.
Déterminerx et y.
Endéduirelalimitedelasuite(a )quandn tendversplusl’infini.n
Interpréterlerésultatprécédententermedenombred’abonnementsdetype
A.
Exercice8
LespartiesAetBsontindépendantes.
PartieA
OnconsidèrelegrapheG ci-dessous:1
B
C
AF
DE
1. Justifierlesaffirmationssuivantes:
A .LegrapheG admetaumoinsunechaîneeulérienne.1 1
A .LachaîneDABCFBEFAEn’estpasunechaîneeulériennedeG .2 1
2. Déterminerunsous-graphecompletdeG ,ayantleplusgrandordrepossible.1
Endéduireunminorantdunombrechromatiqueγdecegraphe.
3. Déterminerunmajorantdecenombrechromatique.(Onjustifieralaréponse).
4. EnproposantunecolorationdugrapheG ,déterminersonnombrechroma-1
tique.
PartieB
Soit la matrice M d’un graphe orienté G dont les sommets A, B, C, D et E sont2
prisdansl’ordrealphabétique.
7   
0 1 1 1 0 6 6 4 5 3
   1 0 1 0 1 5 6 5 3 6   
3   OndonneM= 1 1 0 0 1 et M = 5 7 4 3 6 .   
   0 1 0 0 1 3 5 3 3 3
1 1 0 1 0 6 6 3 3 5
1. ConstruirelegrapheG .2
2. Déterminerlenombredechaînesdelongueur3reliantBàD.Lescitertoutes.
Exercice9
Ons’intéresseauxperformancesréaliséespardesétudiantscourantle200mètres
dans les compétitions universitaires. Lors d’une compétition, le score d’un(e) étu-
diant(e)estsonmeilleur temps ensecondesobtenuaux200 m.Uneenquête aper-
mis d’établir le comportement général suivant, qu’on supposera valable pour les
fillesetlesgarçonsdanstoutelasuite:
• Lors dela première compétition, lescore d’un(e) étudiant(e) est toujours su-
périeurouégalà25secondes.
• Si, lors de la n-ième compétition, l’étudiant(e) a réalisé un score strictement
inférieurà25secondes,laprobabilitéqu’il(elle)réaliseencoreunscorestrictement
2
inférieurà25secondeslorsdelan+1-ièmecompétitionestde .
5
• Si, lors de la n-ième compétition, l’étudiant(e) a réalisé un score supérieur
ou égalà25 secondes, laprobabilité qu’il (elle) réalise encoreun scorestrictement
1
inférieurà25secondesest .
5
On représente les données précédentes par un graphe probabiliste G à deux
états.
OnnoteAtoutscorestrictementinférieurà25secondesetBtoutscoresupérieur
ouégalà25secondes.
On note a la probabilité d’obtenir un score A lors de la compétition n et b lan n
probabilitéd’obtenirunscoreBlorsdelacompétitionn.
L’état probabiliste lors de la compétition n est donc représenté par la matrice
ligne(a b ).n n
1. ReprésenterGetdonnersamatrice.
2. Jamalia,jeuneétudiante,seprésenteàsapremièrecompétitionuniversitaire.
a. Calculer laprobabilitéqu’elleréaliseunscorestrictement inférieur à25
secondesaux200mètreslorsdecettecompétition.
b. Calculer laprobabilitéqu’elleréaliseunscorestrictement inférieur à25
secondesaux200mètreslorsdesatroisièmecompétition.
3. Déterminerl’étatstabledugrapheG.
4. Julienadéjàdenombreusescompétitionsuniversitairesdanslesjambes.
Montrerque,poursaprochainecompétition,ilaenvironunechancesurquatre
deréaliserunscorestrictementinférieurà25secondesaux200mètres.
Exercice10
Unjardinierpossèdeunterrainbienensoleilléavecunepartieplusombragée.
Ildécided’yorganiserdesparcellesoùilplantera8variétésdelégumes:
del’ail(A),descourges(Co)deschoux(Ch),despoireaux(Px),despois(Po),des
pommesdeterre(Pt),desradis(R)etdestomates(T).
Il consulte un almanach où figurent des incompatibilités de plantes, données par
lesdeuxtableaux:
8Expositions incompatibles de
plantes
Associationsincompatiblesde
Plantes d’ombre Plantes de plein
plantesdansunemêmeparcelle
partielle soleil
pois ail,poireaux
pommesde courges,radiset
choux
terre tomates
pois tomates
tomates,ail
radis courges
choux poireauxetcourges
courges tomates
Parexemple :lespoissontincom-
Par exemple : les pois sont in-
patiblesavecl’ailetlespoireaux
compatiblesavecleschoux,lesto-
matesetlescourges
Pourtenircomptedecesincompatibilités lejardinierdécidedemodéliser lasi-
tuation sous la forme d’un graphe de huit sommets, chaque sommet représentant
unlégume.
1. Sur lafeuille annexe :compléter legraphe mettant enévidence les incompa-
tibilitésd’expositionoulesassociationsincompatiblesindiquéesdanslesdeux
tableauxci-dessus.
2. Calculer lasomme desdegrésdessommets dugraphe,endéduirelenombre
desesarêtes.
3. Rechercherunsous-graphecompletd’ordre4,qu’endéduit-onpourlenombre
chromatiquedugraphe?
4. Donner le nombre chromatique du graphe et l’interpréter en nombre mini-
mumdeparcellesquelejardinierdevracréer.
5. Donnerunerépartitiondesplantesparparcelledefaçonàcequechaquepar-
celle contienne exactement deux types de plantes et que le nombre de par-
cellessoitminimum.
6. Donner une répartition des plantes de façon à ce qu’une parcelle contienne
troisplantesetquelenombredeparcellessoitminimum.
Px A
TPo
Pt Co
R
Ch
Exercice11
Le graphe ci-dessous indique, sans respecter d’échelle, les parcours possibles
entrelesseptbâtimentsd’uneentrepriseimportante.
9B C
A D
G E
F
Unagentdesécuritéeffectuerégulièrementdesrondesdesurveillance.Sestemps
deparcoursenminutesentredeuxbâtimentssontlessuivants:
AB:16minutesAG:12minutes;BC:8minutes;BE:12minutes;BG:8minutes;
CD : 7 minutes; CE : 4 minutes; CG : 10 minutes; DE : 2 minutes; EF : 8 minutes;
EG:15minutes;FG:8minutes.
Surchaquearête,lestempsdeparcourssontindépendantsdusensdeparcours.
1. Enjustifiantlaréponse,montrerqu’ilestpossiblequel’agentdesécuritépasse
unefoisetuneseulepartouslescheminsdecetteusine.Donnerunexemple
detrajet.
2. L’agentdesécuritépeut-il reveniràsonpointdedépartaprèsavoir parcouru
unefoisetuneseuletousleschemins?Justifierlaréponse.
3. Touslesmatins,l’agentdesécuritépartdubâtimentAetserendaubâtiment
D.
Enutilisantunalgorithmequel’onexplicitera,déterminerlecheminqu’ildoit
suivre pour que son temps de parcours soit le plus court possible, et donner
cetempsdeparcours.
Exercice12
PartieA
OnnoteGlegraphereprésentéci-dessous et M samatriceobtenueenprenant
3lessommetsdansl’ordrealphabétique.LamatriceM estégalementdonnée.
10

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.