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

Frattini

Description

Decouvrez les TP et les cours 2009/2010 pour la classe de terminale ES.

Sujets

• Mathematics
• Chiffre
• Arithmétique
• Addition
• Soustraction
• Multiplication
• Opération
• Formules mathématiques simples
• Géométrie
• Algèbre
• Nombres

Informations

• Publié par: classe-de-terminale-es
• Publié le: 01 janvier 2009
• Nombre de lectures: 24
• Langue: Français

Extrait

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
entiernatu