Mathématiques Graphes Annales Terminale ES mars 2007altermundus.fr/pages/downloads/Graphes_TES.pdf · Mathématiques Graphes Annales Terminale ES mars 2007 ... c/ Parmi ceux qui

Mathmatiques Graphes Annales Terminale ES mars 2007

Exercice no 1 Amrique du nord juin 2003 (5 points)Soit le graphe G joint en annexe constitu des sommets A, B, C, D, E, F et G.1/ Quel est son ordre et le degr de chacun de ses sommets ?

2/ Reproduire sur la copie et complter le tableau des distances entre deux sommets de G :

Distance A B C D E F GA XB X XC X X XD X X X XE X X X X XF X X X X X XG X X X X X X X

En dduire le diamtre de ce graphe.

3/ a/ Donner un sous-graphe complet dordre 3 de G.

Quen dduire pour le nombre chromatique de G ?

b/ Proposer une coloration du graphe G et en dduire son nombre chromatique.

4/ Donner la matrice M associe G (vous numroterez les lignes et les colonnes dans lordrealphabtique).

5/ En utilisant la matrice M2 donne en annexe 1, dduire le nombre de chanes de longueur 2 partantde A sans y revenir.

A

B

C

D

E

F

G

M2 =

3 1 1 0 2 1 01 3 0 1 2 1 11 0 3 1 1 2 10 1 1 2 1 1 12 2 1 1 4 0 01 1 2 1 0 3 20 1 1 1 0 2 2

Alain Matthes Collge Svign Page 1


Exercice no 2 Asie juin 2003 (5 points)

Dans la ville de GRAPHE, on sintresse aux principales ruespermettant de relier diffrents lieux ouverts au public, sa-voir la mairie (M), le centre commercial (C), la bibliothque(B), la piscine (P) et le lyce (L). Chacun de ces lieux estdsign par son initiale. Le tableau ci-contre donne les ruesexistant entre ces lieux.

B C L M PB X X XC X X XL X XM X X X XP X X

1/ Dessiner un graphe reprsentant cette situation.

2/ Montrer quil est possible de trouver un trajet empruntant une fois et une seule toutes les rues dece plan. Justifier. Proposer un tel trajet.

Est-il possible davoir un trajet partant et arrivant du mme lieu et passant une fois et une seulepar toutes les rues ?

3/ Dimitri habite dans cette ville ;le graphe ci-contre donne lenouveau plan du quartier avecles sens de circulation dans lesdiffrentes rues et le temps deparcours entre les diffrentslieux.

P

B

M

D

C

L

4 9 4

5

10

113

10

10

10



Exercice no 3 France juin 2003 (5 points)Un concert de solidarit est organis dans une grande salle de spectacle. ce concert sont convissept artistes de renomme internationale Luther Allunison (A), John Biaise (B), Phil Colline (C), BobDitlne (D), Jimi Endisque (E), Robert Fripe (F) et Rory Garaguerre (G).Les diffrents musiciens invits refusant de jouer avec certains autres, lorganisateur du concert doitprvoir plusieurs parties de spectacle. Les artes du graphe ci-dessous indiquent quels sont lesmusiciens qui refusent de jouer entre eux.

D

E F

G

A

B

C

1/ Dterminer la matrice associe au graphe (les sommets de tant classs dans lordre alphab-tique).

2/ Quelle est la nature du sous-graphe de constitu des sommets A, E, F et G ? Que peut-on endduire pour le nombre chromatique () du graphe ?

3/ Quel est le sommet de plus haut degr de ?

En dduire un encadrement de ().

4/ Aprs avoir class lensemble des sommets de par ordre de degr dcroissant, colorier le graphe figurant en annexe.

5/ Combien de parties lorganisateur du concert doit-il prvoir ?

Proposer une rpartition des musiciens pour chacune de ces parties.



Exercice no 4 Centres trangers juin 2003 (5 points)

Un livreur dune socit de vente domicile doit, dans son aprs-midi, charger son camion lentreptnot A, livrer cinq clients que nous noterons B, C, D, E et F, puis retourner lentrept. Le rseau routier,tenant compte des sens de circulation, et les temps de parcours (en minutes) sont indiqus sur legraphe G suivant :

F

A B

CD

E

4

4

9

2

11

3

6

2

2

33

66

1/ Donner la matrice M associe au graphe G.

On utilisera le modle suivant :A B C D E F

ABCDEF

2/ On donne la matrice M6 :

M6 =

8 6 6 3 4 619 11 12 9 6 1636 28 23 22 18 3437 24 25 17 15 3115 12 9 10 8 1528 22 19 15 15 26

On sintresse aux chemins partant de lentrept A et se terminant en A.

a/ Combien existe-t-il de chemins de longueur 6 reliant A A ?

b/ Citer ces chemins.

c/ Parmi ceux qui passent par tous les sommets du graphe, lequel minimise le temps de parcours ?

d/ Quelle consquence peut tirer le livreur du dernier rsultat ?

3/ Au dpart de sa tourne, le livreur a choisi de suivre litinraire le plus rapide. Malheureusement,le client C nest pas prsent au passage du livreur et celui-ci dcide de terminer sa livraison parce client. Indiquer quel est le chemin le plus rapide pour revenir lentrept A partir de C. Larponse devra tre justifie.



Exercice no 5 Amrique du Nord mai 2004 (5 points)Les parties A et B sont indpendantes.Partie AOn considre le graphe G1 ci-dessous :

F

B

E

C

D

A

1/ Justifier les affirmations suivantes :

A1 : le graphe G1 admet au moins une chane eulrienne .

A2 ; La chane DABCFBEFAE nest pas une chane eulrienne de G1 .

2/ Dterminer un sous-graphe complet de G1, ayant le plus grand ordre possible. En dduire unminorant du nombre chromatique de ce graphe.

3/ Dterminer un majorant de ce nombre chromatique. (On justifiera la rponse).

4/ En proposant une coloration du graphe G1, dterminer son nombre chromatique.

Partie BSoit la matrice M dun graphe orient G2 dont les sommets A, B, C, D et E sont pris dans lordrealphabtique.On donne

M =

0 1 1 1 01 0 1 0 11 1 0 0 10 1 0 0 11 1 0 1 0

et

M3 =

6 6 4 5 35 6 5 3 65 7 4 3 63 5 3 3 36 6 3 3 5

.1/ Construire le graphe G2.

2/ Dterminer le nombre de chanes de longueur 3 reliant B D. Les citer toutes.



Exercice no 6 Centres trangers juin 2004 (5 points)

Un jardinier possde un terrain bien ensoleill avec une partie plus ombrage.Il dcide dy organiser des parcelles o il plantera 8 varits de lgumes :

de lail (A), des courges (Co), des choux (Ch), des poireaux (Px), des pois (Po), des pommes de terre (Pt), des radis (R), et des tomates (T).

Il consulte un almanach o figurent des incompatibilits de plantes, donnes par les deux tableaux :

Expositions incompatibles de plantesPlantes dombre par-tielle

Plantes de plein soleil

chouxpois tomatesradis courges

Par exemple : les pois sont incompatiblesavec les choux, les tomates et les courges

Associations incompatibles deplantes dans une mme parcellepois ail, poireauxpommes de courges, radis etterre tomates

tomates, ailchoux poireaux et courgescourges tomatesPar exemple : les pois sont incompatiblesavec lail et les poireaux

Pour tenir compte de ces incompatibilits le jardinier dcide de modliser la situation sous la formedun graphe de huit sommets, chaque sommet reprsentant un lgume.

1/ Sur la feuille annexe : complter le graphe mettant en vidence les incompatibilits dexpositionou les associations incompatibles indiques dans les deux tableaux ci-dessus.

2/ Calculer la somme des degrs des sommets du graphe, en dduire le nombre de ses artes.

3/ Rechercher un sous-graphe complet dordre 4, quen dduit-on pour le nombre chromatique dugraphe ?

4/ Donner le nombre chromatique du graphe et linterprter en nombre minimum de parcelles quele jardinier devra crer.

5/ Donner une rpartition des plantes pur parcelle de faon ce que chaque parcelle contienneexactement deux types de plantes et que le nombre de parcelles soit minimum.

6/ Donner une rpartition des plantes de faon ce quune parcelle contienne trois plantes et que lenombre de parcelles soit minimum.

R

Po

Pt

Px A

T

Co

Ch



Exercice no 7 France juin 2004 (5 points)Le graphe ci-dessous indique, sans respecter dchelle, les parcours possibles entre les sept btimentsdune entreprise importante.

A

B

E

C

D

A

Un agent de scurit effectue rgulirement des rondes de surveillance. Ses temps de parcours enminutes entre deux btiments sont les suivants :

AB : 16 minutes ; AG : 12 minutes ; BC : 8 minutes ; BE : 12 minutes ; BG : 8 minutes ; CD : 7 minutes ; CE : 4 minutes ; CG : 10 minutes ; DE : 2 minutes ; EF : 8 minutes ; EG : 15 minutes ; FG : 8 minutes.

Sur chaque arte, les temps de parcours sont indpendants du sens de parcours.

1/ En justifiant la rponse, montrer quil est possible que lagent de scurit passe une fois et uneseule par tous les chemins de cette usine. Donner un exemple de trajet.

2/ Lagent de scurit peut-il revenir son point de dpart aprs avoir parcouru une fois et une seuletous les chemins ? Justifier la rponse.

3/ Tous les matins, lagent de scurit part du btiment A et se rend au btiment D.

En utilisant un algorithme que lon explicitera, dterminer le chemin quil doit suivre pour que sontemps de parcours soit le plus court possible, et donner ce temps de parcours.



Exercice no 8 La Runion juin 2004 (5 points)Partie AOn note G le graphe reprsent ci-dessous et M sa matrice obtenue en prenant les sommets danslordre alphabtique. La matrice M3 est galement donne.

e

f

d

h

gc

a

b

M3 =

10 8 11 10 12 5 13 48 2 7 3 5 2 4 3

11 7 8 6 12 3 10 510 3 6 2 11 1 4 812 5 12 11 8 8 13 35 2 3 1 8 0 2 6

13 4 10 4 13 2 6 94 3 5 8 3 6 9 0

Dire, en justifiant votre rponse, si les affirmations suivantes sont vraies ou fausses :

1/ Lordre du graphe est gal au plus grand des degrs des sommets.

2/ Le graphe G contient un sous-graphe complet dordre 3.

3/ Les sommets de G peuvent tre coloris avec trois couleurs sans que deux sommets adjacentssoient de mme couleur.

4/ Il est possible de parcourir ce graphe en passant une fois et une seule par chaque arte.

5/ Il existe au moins un chemin de longueur 3 qui relie chaque sommet chacun des sept autressommets du graphe.

6/ il y a 72 chemins de longueur 3 qui relient le sommet e chacun des huit sommets du graphe.



Partie BLe graphe suivant reprsente un rseau de lignes dautobus. Les sommets du graphe dsignent lesarrts. Les poids des artes sont les dures de parcours, en minutes, entre deux arrts (correspondancescomprises).

e

f

d

h

gc

a

b

3

11

6

17

20

5

6

7

7

3 9

6

11

4

Dterminer, laide dun algorithme, la dure minimum pour aller de larrt a larrt h et donner cetrajet.


Documents

Mathématiques Graphes Annales Terminale ES mars 2007altermundus.fr/pages/downloads/Graphes_TES.pdf · Mathématiques Graphes Annales Terminale ES mars 2007 ... c/ Parmi ceux qui