Ajouter un/des document(s)
Vous pouvez ajouter un ou plusieurs fichier (+). Word, pdf des images et/ou des fichiers audio.
Feuille de route
Brault & Bouthillier |
 Feuille de route
 Feuille de route modifiable
|
Vidéos
Notions
- Caractéristiques d’un graphe
- Description d’un graphe ou d’un composant de graphe : sommet, arête, boucle, ordre, degré d’un sommet, chaîne, chaîne simple, cycle simple, graphe connexe, graphe complet, etc.
- types de chaînes : eulérien ou hamiltonien;
- types de cycles : eulérien ou hamiltonien;
- description d’un trajet passant une seule fois par toutes les arêtes ou tous les sommets d’un graphe.
- Graphes valués et arbres
- Valeur de la chaîne la plus courte entre deux sommets dans un graphe valué;
- arbre de valeur minimale dans un graphe valué;
- trajet optimal;
- problèmes d’optimisation liés à la valeur d’un chemin ou circuit optimal dans un graphe valué et orienté;.
- Graphes valués et orientés
- Situation représentée par un graphe valué et orienté;
- valeur d’un chemin ou circuit optimal dans un graphe valué et orienté;
- chemin critique d’un projet à l’aide graphe valué et orienté;
- problèmes liés à la résolution de conflits;
- problèmes d’optimisation liés au calcul du temps minimal d’un projet donné.
- Graphes valués, arbres et graphes orientés
- Types de graphes : arbre, graphe valué ou graphe orienté.
Domaine d'examen
C'est à partir des comportements observables ci-dessous que seront construits les items de l'épreuve. On devra respecter les exigences et les limites précisées dans les climensions ainsi que dans les objectifs du programme.
Dimension 1
Étant donné des énoncés décrivant un graphe dont la représentation est donnée ou un composant de ce graphe, déterminer si chaque énoncé est vrai ou faux. /10
ou
Étant donné des graphes dont la représentation est donnée, identifier lequel ou lesquels correspondent à un ou à des énoncés décrivant un graphe ou un composant d'un graphe. /5
(structurer)
Dimension 2
Étant donné des énoncés décrivant un graphe dont la représentation est donnée, déterminer si chaque énoncé portant sur un type de chaîne ou un type de cycle est vrai ou faux. /10
ou
Étant donné des graphes dont la représentation est donnée, identifier lequel ou lesquels correspondent à un ou à des énoncés portant sur un graphe qui illustre un type de chaîne ou. /5
(structurer)
Note : Si on choisit la première option dans la dimension 1, on devra prendre la seconde dans la dimension 2 et vice versa.
Dimension 3 Étant donné une situation décrite par un texte accompagné d'un schéma traduisible en graphe, décrire un trajet correspondant à la situation donnée et passant une seule fois par toutes les arêtes ou tous les sommets du graphe. Le trajet doit être décrit en énumérant, dans l'ordre, les arêtes ou les sommets par lesquels passe ce trajet. (opérer) /10
Dimension 4
Étant donné la représentation de quelques graphes et les termes : arbre, graphe valué ou graphe orienté, déterminer le type de graphes illustré par chacun d'eux.
(structurer) /5
Dimension 5 Étant donné un graphe valué illustrant une situation, déterminer l'arbre de valeur minimale qui optimise ce graphe. L'arbre obtenu doit contenir au plus cinq arêtes.
(opérer) /10
Dimension 6
Déterminer un trajet optimal d'une situation décrite par un texte accompagné d'un tableau ou d'un schéma et pouvant être représentée par un graphe qui contient au plus cinq sommets. Le trajet recherché peut être une chaîne ou un cycle. L'élève doit construire le graphe requis et présenter clairement les éléments de sa démarche.
(opérer) /10
Dimension 7
Étant donné un graphe valué illustrant une situation, calculer la valeur de la chaîne la plus courte entre deux sommets. La chaîne obtenue doit contenir au plus cinq arêtes. L'élève doit présenter clairement les éléments de sa démarche. ou Étant donné un graphe valué et orienté illustrant une situation, calculer la valeur d'un chemin ou le circuit optimal correspondant à un trajet. Le chemin ou circuit obtenu doit contenir au plus cinq arcs. L'élève doit présenter clairement les éléments de sa démarche.
(opérer) /10
Dimension 8
Résoudre deux problèmes d'optimisation à l'aide de graphes. La résolution peut demander la résolution de conflits, le calcul de la valeur d'un chemin ou celui du circuit optimal dans un graphe valué et orienté. L'élève doit présenter clairement les éléments de sa démarche.
(synthétiser) /20
Dimension 9
Représenter par un graphe valué et orienté une situation décrite par un texte accompagné d'un tableau ou d'un schéma. Le graphe doit compter au moins trois sommets et de dix à quinze arcs. L'élève doit présenter clairement le graphe.
(mathématiser) /10
Dimension 10
Résoudre un problème lié à la détermination du chemin critique et au calcul du temps minimal d'un projet à l'aide d'un graphe valué et orienté. Le projet est décrit par un texte accompagné d'un tableau des étapes nécessaires à la réalisation du projet. Le nombre d'étapes doit être compris entre cinq et dix. Chaque étape doit être décrite de manière à identifier la ou les autres étapes qui lui sont préalables, de même que la ou les étapes qui lui sont parallèles. L'élève doit construire le graphe et présenter clairement les éléments de sa démarche.
(synthétiser) /10
*Direction de la formation générale des adultes
Service de l'évaluation
