CORRIGÉS

EXERCICES 4.4

1. Voici trois graphes.Chaîne et cycle eulériens Niveau de difficulté: faible

Dans chacun de ces graphes, trouve, si c’est possible:

a) une chaîne eulérienne;

b) un cycle eulérien.

2. Soit le graphe suivant.

Quelle arête ou quelles arêtes doivent minimalement y être ajoutées pour pouvoir y trouver:Chaîne et cycle eulériens, chaîne et cycle hamiltoniens Niveau de difficulté: faible

a) une chaîne eulérienne?

b) une chaîne hamiltonienne?

c) un cycle eulérien?

d) un cycle hamiltonien?

3. Voici trois graphes.Chaîne et cycle hamiltoniens Niveau de difficulté: faible

Dans chacun de ces graphes, trouve, si c’est possible:

a) une chaîne hamiltonienne;

b) un cycle hamiltonien.

4. Trace un graphe à six sommets qui contient à la fois un cycle eulérien et un cycle hamiltonien.Quelles sont les caractéristiques de ce graphe?Cycle eulérien, cycle hamiltonien Niveau de difficulté: moyen

5. Flora est guide dans le Vieux-Québec. Elle veut offrir à ses clients deux parcours qui permettent d’emprunter toutes les rues feutrées sur la carte sans passer deux fois par la même section de rue.Chaîne eulérienne Niveau de difficulté: moyen

a) Trace un graphe représentant cette situation.

b) Détermine les deux parcours que Flora pourrait offrir à ses clients.

6. Peux-tu reproduire chacune des figures suivantes sans soulever la pointe de ton crayon et sans passer une deuxième fois sur un même trait? Justifie tes réponses.Chaîne eulérienne Niveau de difficulté: moyen

a)

b)

c)

d)

e)

7. Les trois graphes suivants ne contiennent aucun cycle eulérien. Pourquoi?Cycle eulérien Niveau de difficulté: faible

a)

b)

c)

8. Plusieurs employeurs organisent un Salon de l’emploi pour faire connaîtreleur entreprise et recruter du personnel. Martine cherche un emploi et veutpasser à chacun des kiosques d’une partie du Salon pour rencontrer lesemployeurs potentiels. Voici un graphe représentant cette partie du Salon.Dans ce graphe, les sommets représentent les kiosques et les arêtes,le trajet qu’il est possible d’emprunter pour passer directement d’unkiosque à l’autre.Chaîne et cycle hamiltoniens Niveau de difficulté: moyen

Détermine trois trajets différents qui permettront à Martine de se présenterà tous les kiosques sans passer deux fois devant le même kiosque. Au moinsun des trajets doit lui permettre de revenir à son point de départ.

9. Dans un jeu vidéo, le joueur doit déplacer le héros d’unmonde à l’autre pour lui faire acquérir des objetsqui l’aideront à gagner la partie. Le graphesuivant représente les passages possiblesentre les différents mondes.Chaîne hamiltonienne Niveau de difficulté: moyen

Détermine un trajet qui permet au hérosdu jeu de visiter tous les mondes sans passerdeux fois dans le même monde.

10. Les dirigeants d’une entreprise de télécommunications demandent à une agence de publicité de préparer une campagne de promotion pour leur nouveau service de téléphonie sans fil. Voici la proposition faite par l’agence: simultanément, dans deux secteurs achalandés de la ville, deux camions transportant un téléphone géant vont se déplacer en passant dans toutes les rues. Voici un plan de chacun des secteurs dans lesquels les camions devront se rendre. Les chiffres placés dans les plans représentent des points de repère pour les conducteurs des camions.Chaîne eulérienne Niveau de difficulté: moyen

a) Représente chacun des secteurs par un graphe.

b) Détermine, si c’est possible, un trajet qui permet à chacun des deux camions de passer par l’ensemble des rues de chacun des secteurs sans emprunter deux fois le même tronçonde rue. Justifie tes réponses.

EXERCICES 4.8

1. Dans le graphe suivant, détermine:Graphe, chaîne et cycle, degré des sommets

Niveau de difficulté: faible

a) le nombre de sommets et d’arêtes;

b) le degré de chacun des sommets;

c) une chaîne passant par tous les sommets et dont le point de départ est F;

d) un cycle passant par cinq sommets différents et dont le point d’arrivée est B.

2. La carte suivante représente les districts électoraux de la ville de Rimouski.Graphe, degré des sommets Niveau de difficulté: faible

a) Représente par un graphe les différents districts électoraux de la ville en reliant ceux qui ont une frontière commune.

b) Combien d’arêtes et de sommets le graphe tracé en a comporte-t-il?

c) Quel est le sommet de plus petit degré dans ton graphe? Que représente ce degré dansle contexte?

d) Ce graphe est-il connexe? Justifie ta réponse.

3. La constellation d’Orion est composée de sept étoiles principales, dont trois sont alignées pour former la ceinture d’Orion. Le graphe suivant représente cette constellation.Graphe, chaîne et cycle, distance entre deux sommets Niveau de difficulté: faible

a) Combien d’arêtes comporte ce graphe?

b) Quelle chaîne débutant par l’étoile Bételgeuse permet de repérer chacune des étoiles decette constellation?

c) Détermine le plus long cycle débutant par l’étoile Bételgeuse qui permet de ne pas passer plus d’une fois par la même arête. Quelle est la longueur de ce cycle?

4. Construis un graphe ayant les caractéristiques suivantes.– Il comporte cinq sommets et sept arcs.– Il est possible d’y parcourir le circuit D – A – B – E – D et le chemin D – B – E – C – B.– Le degré des sommets A, B, C, D et E est respectivement 2, 4, 2, 3 et 3.Graphe orienté, chemin et circuit, degré des sommets Niveau de difficulté: faible

5. Représente, par un graphe approprié, les liens de communication professionnels dans une entreprise, sachant:– que la présidente n’est en relation qu’avec ses trois directeurs;– que les trois directeurs doivent se consulter avant de prendre des décisions stratégiques et

qu’ils gèrent chacun trois employés;– que les employés travaillant avec un même directeur doivent interagir entre eux et qu’ils n’ont

aucun contact professionnel avec les autres personnes dans l’entreprise.Graphe Niveau de difficulté: moyen

6. Voici quatre graphes accompagnés d’un tableau dans lequel est noté le degré des sommets.

Graphe et graphe orienté, degré des sommets Niveau de difficulté: faiblea) Complète les tableaux ci-dessus.

b) Que peux-tu affirmer au sujet de la somme des degrés d’un graphe? Justifie ta réponse par un raisonnement mathématique.

7. Observe le graphe suivant.Graphe orienté, chemin et circuit, graphe valué, degré des sommets, poids d’un circuit

Niveau de difficulté: faiblea) De quel type de graphe s’agit-il?

b) Quel est le degré des sommets A, B et F?

SommetDegré

A3

B4

C3

D4

Total14

SommetDegré

E4

F3

G4

H4

I3

Total18

SommetDegré

J2

K2

L3

M5

Total12

SommetDegré

N4

O3

P4

Q3

R2

S0

Total16

c) Détermine le poids du chemin A – B – B – F – D – E – F.

d) Trouve un circuit reliant quatre sommets dont le poids est 14.

8. Voici quatre contextes.

Le trajet d’un livreur d’appareils électroménagers.

La hiérarchie de commandement dans une armée.

Le temps de voyage sur un bateau de croisière entre différentes îles des Caraïbes.

Le réseau de fils électriques d’une maison.Graphe et graphe orienté, graphe valué, arbre Niveau de difficulté: moyen

a) Associe un ou plusieurs contextes à chacun des types de graphe suivants.

1) Graphe connexe

2) Graphe orienté

3) Graphe valué

4) Arbre

b) Précise ce que représenteraient les sommets et les arêtes (ou les arcs) de chacun deces graphes.

9. Observe le tableau suivant, puis réponds aux questions.La durée du trajet en train, en minutes, entre cinq villes d’Europe

Destination

DépartVarsovie Berlin Prague Budapest Munich

Varsovie – 365 520 780

Berlin 365 – 275 345

Prague 520 275 – 365

Budapest 780 –

Munich 345 365 –Graphe orienté, graphe valué, poids d’un chemin Niveau de difficulté: faible

a) Représente les données de ce tableau dans un graphe approprié.

b) Détermine deux trajets différents pour se rendre à Budapest à partir de Munich. Lequel de ces deux trajets est de plus courte durée?

c) Un voyageur veut prendre le train à Berlin pour se rendre à Prague. Comme il n’y a pas de trajet direct entre ces deux villes à l’heure où il souhaite partir, il devra passer par Munich pour se rendre à Prague. Combien de temps de plus lui prendra son voyage?

10. Soit les graphes suivants.

Arbre Niveau de difficulté: moyena) Lequel de ces graphes est un arbre? Explique pourquoi.

b) Décris les modifications minimales que tu pourrais apporter aux trois autres graphes pour qu’ils deviennent des arbres.

11. Tu fais un petit sondage auprès des membres d’un groupe en leur demandant quel est le premier mot qui leur vient à l’esprit quand on leur parle de l’hiver. Les résultats sont compilés dans le tableau suivant.

Mots Neige Froid Noël Ski Long Autres

Fréquence 37 21 10 6 14 12

Graphe orienté, graphe valué Niveau de difficulté: faiblea) Représente les résultats du sondage par un graphe approprié.

b) Quel type de graphe as-tu tracé?

12. Ludo veut brancher son système de cinéma maison.Graphe, distance entre deux sommets Niveau de difficulté: faible

a) Illustre par un graphe les branchements entre les différents appareils de son système de cinéma maison, sachant que:– les cinq haut-parleurs sont branchés sur l’amplificateur;– le lecteur de DVD, la télévision et l’amplificateur sont branchés les uns aux autres;– le récepteur satellite est branché sur la télévision.

b) Quel est le type de graphe utilisé?

c) Trouve la chaîne représentant le trajet du son qui arrive par le récepteur satellite.

13. Les chalets, les points d’intérêt et les pistes d’un circuit de motoneige sont représentés par le graphe suivant. Les distances sont indiquées en kilomètres.

Graphe, chaîne et cycle, poids d’une chaîne, distance entre deux sommets Niveau de difficulté: faiblea) Combien de kilomètres parcourt une motoneigiste qui débute sa randonnée à l’accueil, se rend

au sommet, puis au chalet B, pour aller ensuite directement au chalet D et revenir à l’accueil?

b) Quelle chaîne a un poids de 363 km?

c) Quelle est la longueur de la chaîne trouvée en b?

d) Quelle est la distance entre le sommet et le chalet D?

e) Est-il possible de fermer des pistes tout en permettant aux motoneigistes, à partir del’accueil, d’accéder à tous les chalets, au sommet et à la vallée? Combien de pistes pourraient être fermées?

14. Représente par un graphe les liens existant entre un polyèdre, un polyèdre régulier, un prisme droit à base rectangulaire, un cube, un prisme droit à base triangulaire et une pyramide droiteà base carrée:Graphe et graphe orienté Niveau de difficulté: faible

a) en considérant la relation «est aussi un»;

b) en considérant la relation «a toujours le même nombre de faces que».

15. Le jeu suivant est un labyrinthe en bois que l’on incline pour faire avancer une bille en contournant les trous, représentés par les chiffres de 1 à 10. Le but du jeu est de faire tomber la bille dans le trou numéro 10 en partant de l’entrée.Graphe orienté, chemin Niveau de difficulté: moyen

a) Représente ce jeu par un graphe en utilisant l’entrée du labyrinthe et les trous comme sommets.

b) Trouve tous les chemins qui représentent les trajets possibles de la bille afin de passer de l’entrée au trou numéro 10.

16. Soit les quatre graphes suivants.

Graphe et graphe orienté, graphe valué, arbre Niveau de difficulté: faiblea) Décris précisément chacun des graphes.

b) Invente un contexte pour chacun des graphes en identifiant à quoi correspondent les sommets et les arêtes.

17. Le plan suivant illustre le sous-sol de la bibliothèque municipale d’une grande ville où sont entreposées les archives.

Graphe, chaîne, distance entre deux sommets Niveau de difficulté: faiblea) Représente par un graphe le plan du sous-sol en joignant les lieux qui sont directement

accessibles par une porte ou par le corridor.

b) De quel type est le graphe tracé en a?

c) Détermine la distance entre la salle I et la salle G.

d) Chaque soir, l’archiviste principal doit s’assurer que toutes les portes sont bien fermées avant de partir. Propose-lui deux itinéraires différents lui permettant de faire le tour de toutes les salles à partir de deux points de départ différents.

EXERCICES 4.10

1. Pour chacun des graphes suivants, détermine l’arbre de valeurs maximales et son poids.Arbre de valeurs maximales, algorithme de Kruskal Niveau de difficulté: faible

a)

b)

2. Détermine le poids de l’arbre de valeurs minimales du graphe suivant.Arbre de valeurs minimales, algorithme de Kruskal Niveau de difficulté: faible

3. Les administrateurs d’une zone d’exploitation contrôlée (ZEC) dans la région de la Mauricie veulent réduire les frais d’entretien des routes donnant accès aux zones de chasse et de pêche. Ils veulent toutefois conserver au moins un accès pour chacune de ces zones. Le tableau suivant présente les routes qui sillonnent le territoire de la ZEC.

Route Distance (km)Chalet (C) – Lac Jaune (L J) 2,2Chalet (C) – Lac Vert (LV) 1,7Forêt à l’ours (FAL) – Lac Jaune (L J) 3,1Forêt Drouin (FD) – Lac Vert (LV) 2,7Lac Vert (LV) – Lac Jaune (L J) 1,9Lac Vert (LV) – Forêt à l’ours (FAL) 1,9Chalet (C) – Forêt Drouin (FD) 2,6

Quelle est la longueur maximale de route qui sera fermée?Arbre de valeurs minimales, algorithme de Kruskal Niveau de difficulté: moyen

4. Maximilien travaille pour un organisme humanitaire.Il doit planifier des travaux d’irrigation quipermettront d’acheminer de l’eau à partird’une nappe d’eau souterraine (N) versdifférents villages (V1 à V6). Le graphe ci-contrereprésente le plan des canaux du systèmed’irrigation. Le poids de chaque arête représentele temps, en jours, nécessaire pour creuserles canaux.

Sachant que les canaux seront creusés les uns après les autres, combien de temps, au minimum, faudra-t-il pour acheminer l’eau de façon directe ou indirecte aux six villages?Arbre de valeurs minimales, algorithme de Kruskal Niveau de difficulté: moyen

5. Une montagne est choisie comme site pour l’aménagement d’un futur centre de glisse. On étudie toutes les lignes de remonte-pentes possibles pour relier différents secteurs de la montagne. Le tableau suivant présente les lignes de remonte-pentes possibles et une évaluation du nombre d’usagers qui pourront être transportés simultanément.

Le nombre d’usagers pouvant être transportés par chaque ligne de remonte-pentes

Est relié a: La vallée (V) Le versantest (E)

Le boisé(B)

Le sommet(S)

Le versantnord (N)

La vallée (V) – 224 280 400 172Le versant est (E) 224 – 346 512 140Le boisé (B) 280 346 – 300 210Le sommet (S) 400 512 300 – 180Le versant nord (N) 172 140 210 180 –

Le coût des travaux d’aménagement des lignes de remonte-pentes est faramineux. On décide donc de donner minimalement un accès par un remonte-pente à chacun des sites, tout en permettant à un maximum d’usagers d’être transportés simultanément. Quelles lignes de remonte-pentes seront aménagées?Arbre de valeurs maximales, algorithme de Kruskal Niveau de difficulté: moyen

6. Soit le graphe suivant.

Chaîne la plus courte, algorithme de Dijkstra Niveau de difficulté: faibleTrouve la chaîne la plus courte de ce graphe pour se rendre:a) du sommet G au sommet E;

b) du sommet A au sommet K;

c) du sommet C au sommet H.

7. Un spéléologue amateur a emprunté un réseau de passages souterrains pour explorer différentes salles. Le graphe suivant représente le réseau de salles en question. Le poids de chaque arête représente le temps, en minutes, nécessaire pour se rendre d’une salle à une autre en empruntant les passages souterrains.

Quel chemin le spéléologue doit-il emprunter pour atteindre la sortie le plus rapidement possible à partir de la salle 12 (S12)? En combien de temps fera-t-il le trajet?Chaîne la plus courte, algorithme de Dijkstra Niveau de difficulté: moyen

8. Deux amies, Valérie et Chloé, se sont donné rendez-vous à leur café favori. Elles s’y rendent, en partant de chez elles, par les sentiers piétonniers aménagés le long de certaines rues de leur quartier. Le graphe suivant représente le réseau de sentiers piétonniers. La valeur de chaque arête représente la distance, en mètres, séparant différents endroits.

Si toutes deux choisissent le chemin le plus court, quelle distance auront-elles parcourue au total?Chaîne la plus courte, algorithme de Dijkstra Niveau de difficulté: moyen

9. Le graphe suivant représente le coût d’une course en taxi entre différents endroits d’une ville.

Quel est le coût minimal d’une course en taxi pour se rendre du point A au point F?Chaîne la plus courte, algorithme de Dijkstra Niveau de difficulté: moyen

10. En effectuant des travaux d’excavation dansune ville européenne, on a découvert unréseau de tunnels reliant des bunkers datantde la Seconde Guerre mondiale. Au total,neuf bunkers ont été restaurés pour permettredes visites guidées. Le tableau ci-contre présentela longueur des tunnels reliant ces neuf bunkers.

À l’aide d’un graphe, détermine le tempsminimal que mettra une personne pour serendre du bunker principal (BP) au bunker 8 (B8),si elle marche à une vitesse de 3,6 km/h.Chaîne la plus courte, algorithme de Dijkstra

Niveau de difficulté: moyen

11. Est-il possible de trouver deux chaînes les plus courtes dans un même graphe? Si oui, trace un tel graphe. Sinon, explique pourquoi.Chaîne la plus courte, algorithme de Dijkstra Niveau de difficulté: moyen

Le réseau de tunnels entre les bunkers

Bunkers reliés Longueur du tunnel (km)BP – B1 2,3B4 – B5 1,7BP – B5 4,6B1 – B2 1,9B1 – B4 1,6B1 – B6 2,1B2 – B5 2,0B2 – B7 3,2B3 – B7 1,1B3 – B8 0,8B4 – B7 5,3

EXERCICES 4.11

1.Trouve le nombre chromatique de chacun des graphes suivants.Coloration des sommets d’un graphe, nombre chromatique Niveau de difficulté: faible

a)

b)

c)

2. Carmen et Gérald préparent un voyage en Amérique du Sud. Ils désirent se rendre dans chacun des pays du continent sud-américain. Pour déterminer leur itinéraire, ils ont affiché une grande carte de l’Amérique du Sud sur le mur de leur salon. Pour mieux s’y retrouver, ils veulent colorier la carte de telle manière que des pays voisins soient de couleurs différentes. Combien de couleurs, au minimum, devront-ils utiliser?Nombre chromatique Niveau de difficulté: moyen

3. Paul adore cuisiner, mais il n’aime pas combiner certains aliments dans une même recette. Il a donc rédigé un aide-mémoire sur les incompatibilités de goût qui existent, selon lui, entre certains aliments. Le graphe suivant représente les résultats de son travail. Les sommets représentent les aliments et les arêtes, une incompatibilité entre deux aliments.Coloration des sommets d’un graphe, nombre chromatique Niveau de difficulté: moyen

S’il veut utiliser tous les aliments qui se trouvent dans le graphe pour ses desserts, tout en tenant compte des incompatibilités de goût, combien de desserts différents devra-t-il préparer?

4. Jérémie s’occupe du marchandisage dans une boutique qui vend de la vaisselle. Il planifie en ce moment l’agencement des présentoirs et souhaite mettre l’accent sur les différentes couleurs de vaisselle offertes. Voici les trois types de présentoir qui seront utilisés. On peut y placer une pièce de vaisselle dans chaque case.

Jérémie souhaite que les pièces de vaisselle voisines soient de couleurs différentes.Détermine le nombre minimal de couleurs dont il aura besoin pour agencer chacundes présentoirs.Nombre chromatique Niveau de difficulté: faible

5. Benjamin a coloré les sommets du graphe suivant.Coloration des sommets d’un graphe, nombre chromatique Niveau de difficulté: faible

Il affirme que le nombre chromatique de ce graphe est 4. Gabrielle n’est pas d’accord avec lui.A-t-elle raison? Justifie ta réponse.

6. Érika est propriétaire d’un chenil. Pour le mois à venir, elle aura 10 pensionnaires. Elle sait que certains chiens ont des incompatibilités de caractère. Elle veut déterminer le nombre minimal d’enclos à prévoir pour que les chiens y cohabitent sans problème. Le tableau suivant compileles incompatibilités de caractère des différents chiens.Coloration des sommets d’un graphe, nombre chromatique Niveau de difficulté: moyen

Est incompatibleavec: Mali Max Patate Chanel Fanny Princesse Rocky Nougat Benji Cachou

Mali X X X X X X X X

Max X X

Patate X X X X X

Chanel X X X

Fanny X X X

Princesse X X X X

Rocky X X X X

Nougat X X

Benji X X X

Cachou X X X X

À l’aide d’un graphe, détermine le nombre minimal d’enclos qu’Érika devra prévoir et les chiensqui y cohabiteront.

7. Complète les phrases suivantes.Chaîne et cycle eulériens, chaîne et cycle hamiltoniens, nombre chromatique

Niveau de difficulté: faiblea) Une chaîne passant une seule fois par chacun des sommets d’un graphe est dite

.

b) Le nombre chromatique d’un graphe est toujours ou égal à s 1,

où s représente le plus grand des sommets du graphe.

c) Un cycle eulérien est un cycle passant par d’un graphe.

d) Les graphes qui comportent des chaînes hamiltoniennes sont nécessairement .

e) Les graphes qui comportent des chaînes eulériennes n’ont aucun ou exactement

de degré .

EXERCICES 4.13

1. Le tableau suivant présente les principales étapes suivies par les membres d’une famille qui préparent une tourtière du Lac-Saint-Jean pour le temps des fêtes.

La confection d’une tourtière du Lac-Saint-Jean

Étape Temps(min)

Étape(s)préalable(s)

A Réunir les ingrédients sur le plan de travail. 5 –B Mesurer les ingrédients pour la pâte. 3 AC Mélanger les ingrédients pour la pâte. 4 BD Abaisser la pâte. 10 CE Peler et couper les pommes de terre en cubes. 20 AF Couper le bœuf en cubes. 15 AG Couper le porc en cubes. 15 AH Mélanger les pommes de terre, le bœuf et le porc

dans un grand bol en ajoutant du bouillon de bœufet un sachet de soupe à l’oignon.

3 E, F et G

I Couvrir le plat de cuisson de pâte. 4 DJ Déposer le mélange de pommes de terre, de bœuf et de porc

sur la pâte. 1 I et H

K Ajouter de l’eau et du bouillon de poulet. 1 JL Recouvrir le tout de pâte. 5 D et KM Cuire au four à feu doux. 240 LN Servir. 4 M

Combien de temps, au minimum, devra-t-il s’écouler avant qu’ils puissent manger la tourtière?Chemin critique Niveau de difficulté: moyen

On trace le graphe représentant la situation:

Le chemin critique est Début - A – E – H – J – K – L – M – N – Fin et son poids est de 279. Il faudra qu’il s’écoule un minimum de 279 minutes, soit 4 heures 39 minutes, avant qu’il puissent manger la tourtière.

A : 5B : 3

C : 4 D : 10

I : 4E : 20

F : 15

G : 15

H : 3 J : 1 H : 1 L : 5 M : 240 N : 4

2. Combien y a-t-il de chemins critiques dans le graphe suivant? Pourquoi en est-il ainsi?Justifie ta réponse.Chemin critique Niveau de difficulté: faible

3. Soit le graphe suivant.

Chemin critique Niveau de difficulté: moyenQuelle valeur ou quelles valeurs peut prendre y si le poids du chemin critique de ce graphe est de:

a) 32?

b) 25?

c) 40?

G : 1

F : 4

E : 4

D : 5

C : 3

B : 3

A : 4FinDébut

4. Une équipe de pâtissiers confectionne des gâteaux à la purée de fruits. Le tableau suivant présente toutes les étapes nécessaires à la confection de ces gâteaux.

La confection d’un gâteau à la purée de fruits

Étape Durée(heures)

Étape(s)préalable(s)

A Réunir les ingrédients sur le plan de travail. 5 –B Mesurer chacun des ingrédients nécessaires à la confection

du gâteau. 3 A

C Tamiser les ingrédients secs du gâteau. 3 BD Mettre tous les ingrédients du gâteau dans un bol et

bien mélanger. 6 C

E Mesurer chacun des ingrédients nécessaires à la préparationdu glaçage. 3 A

F Mélanger tous les ingrédients du glaçage. 4 EG Faire cuire le gâteau. 25 DH Réfrigérer le glaçage. 10 FI Laver les fruits. 6 A

J Écraser les fruits à l’aide d’un pilon à purée. 4 IK Faire cuire les fruits. 12 JL Faire refroidir la purée de fruits. 20 KM Laisser refroidir le gâteau. 15 GN Couper le gâteau dans le sens de la longueur et étendre

du glaçage entre les étages. 8 M et H

P Napper le gâteau de glaçage. 10 NQ Verser la purée de fruits sur le gâteau. 2 L et P

Chemin critique Niveau de difficulté: faiblea) Combien de temps faut-il pour confectionner un gâteau à la purée de fruits?

b) La purée de fruits est encore chaude après avoir été laissée à refroidir sur le plan de travail pendant 20 minutes (étape L). Le chef pâtissier décide de la laisser refroidir 20 minutes de plus. Quel impact ce délai aura-t-il sur le temps de confection du gâteau? Justifie ta réponse.

A : 5B : 3

C : 3 D : 6 G : 25 M : 5

E : 3 F : 4 H : 10 P : 10

J : 4 K : 12 L : 20

N : 8

I : 6

Q : 2Début Fin

5. Détermine le poids du chemin critique des graphes suivants.Chemin critique Niveau de difficulté: faible

a)

b)

6. Le comité d’organisation de la fête d’Halloween d’une école secondaire a déterminé les étapes à accomplir avant la fête et la durée approximative nécessaire à leur réalisation. Voici la liste des tâches à faire.

Combien de temps faudra-t-il, au minimum, pour organiser la fête d’Halloween?Chemin critique Niveau de difficulté: faible

A : 1

B : 2 D : 1 I : 1

J : 2

C : 1 E : 1 F : 1

G : 1 H : 1

Début Fin

Choisir une ville où acheter

3

Consulter un agent immobilier

2

Rechercher une maison à construire dans Internet

4

Consulter le représentant d’une institution bancaire

3

Visiter des maisons3

Choisir une maison1

Acheter la maison

7. Le graphe suivant représente les étapes que Frida et Marco doivent suivre pour faire l’achat de leur première maison. La valeur de chaque arc représente la durée, en semaines, nécessaire àla réalisation d’une étape.

Frida et Marco n’ont pris que deux semaines pour rechercher dans Internet des maisons construites qui leur plaisent. Quel est l’effet de ce changement sur le temps minimal nécessaire à la réalisation de toutes les étapes pour faire l’achat de leur maison?Chemin critique Niveau de difficulté: moyen

8. Le graphe ci-dessous représente les étapes à suivre pour atteindre un objectif. La valeur de chaque arc représente le temps, en années, nécessaire à la réalisation d’une étape.

Trouve deux façons différentes d’atteindre cet objectif en 17 ans, en réduisant le temps nécessaire à la réalisation d’une étape.Chemin critique Niveau de difficulté: moyen

FinDébutJ : 0

H : 2

G : 3

I : 3

F : 2

E : 1

D : 5

C : 1

B : 1

A : 5

A – B – D – E – H – J = 14

A – B – D – F – I – J = 16

A – C – D – E – H – J = 18

9. Que dois-tu chercher si on te demande:Arbre de valeurs maximales, arbre de valeurs minimales, chaîne la plus courte, chemin critique

Niveau de difficulté: faiblea) de définir l’itinéraire d’un secouriste qui doit atteindre le plus rapidement possible des

spéléologues amateurs perdus dans un dédale de galeries souterraines?

b) de déterminer le temps minimal nécessaire à la réalisation de toutes les étapes de la construction d’une maison?

c) de relier tous les appareils électriques d’une maison en utilisant le moins de fils possible?

d) de déterminer le nombre maximal de kilomètres de route à asphalter pour relier huit villages par sept routes?

e) de déterminer le chemin le plus rapide pour se rendre à un rendez-vous?