Graphe NSI

Dans le graphe suivant, quel est le chemin critique?

• A - B - C - D - K

• A - B - E - F - G - J - K

• A - B - E - H - I - J - K

• A - B - C - D - G - J - K

La somme des degrés de tous les sommets d’un graphe est ... nombre d’arêtes.

• égale au

• la moitié du

• le double du

• le carré du

Ce graphe est

• complet

• connexe

• orienté

• non orienté

Le sommet E est de degré

• 1

• 2

• 3

• 4

Le diamètre du graphe est égal à

• 3

• 4

• 5

• 6

Une entreprise veut relier entre eux 6 postes informatiques.

Les arêtes du graphe suivant représentent les câbles qu’il est possible d’installer. La valeur associée à chaque arête désigne le coût, en dollars, de l’installation d câble correspondant.

L’entreprise veut minimiser le coût total de l’installation des câbles.

Qu’est-ce que l’entreprise doit chercher dans le graphe?

• Un arbre de valeur minimale contenant 5 arêtes et reliant tous les sommets du graphe.

• Un arbre de valeur minimale contenant 6 arêtes et reliant tous les sommets du graphe.

• Un cycle de valeur minimale contenant 6 arêtes et passant par tous les sommets du graphe.

• Un cycle de valeur minimale contenant 7 arêtes et passant par tous les sommets du graphe.

Kim organise une fête de retrouvailles.

Les sommets du graphe suivant représentent les personnes du groupe.

La présence d’une arête entre deux sommets indique que les deux personnes concernées connaissent le numéro de téléphone l’une de l’autre.

Quel est le nombre minimal d’appels nécessaires pour rejoindre toutes les personnes du groupe?

• 9

• 10

• 15

• 16

Les sommets du graphe ci-dessous représentent les villes situées sur une île. La valeur associée à chaque arête représente le coût, en dollars, du transport entre deux villes.

Antoine visite les sept villes. Son séjour débute dans la ville G et prend fin dans la ville E.

Quel trajet permet à Antoine de minimiser les coûts de transport?

Gérard est le gérant d’un lave-auto qui effectue le nettoyage intérieur et extérieur des véhicules. Le graphe ci-dessous illustre les différentes étapes du nettoyage d’une voiture. La valeur attribuée à chaque flèche représente le nombre de minutes nécessaires pour compléter l’étape correspondante. La direction des flèches indique l’ordre dans lequel les étapes doivent être complétées. Plusieurs étapes peuvent être effectuées simultanément.

Quelle est la durée minimale requise pour qu’une voiture soit complètement nettoyée au lave-auto de Gérard?

• 17 minutes

• 20 minutes

• 22 minutes

• 38 minutes

Le graphe ci-dessous représente, dans l’ordre, les différentes tâches qu’un traiteur doit effectuer pour préparer un événement.

Entre chacune des étapes, on y indique le temps (en minutes) requis avant d’effectuer l’étape suivante.

Quel est le temps minimal requis au traiteur pour effectuer toutes ces étapes?

• 75 minutes

• 95 minutes

• 100 minutes

• 190 minutes