MAT-5104-1 – Optimisation II

Ce cours est une initiation à la théorie des graphes. Nous y introduisons d’abord la construction de graphes et la définition de concepts qui leur sont propres : sommets, arêtes, chaînes et cycles, chaînes et cycles eulériens, chaînes et cycles hamiltoniens. Enfin, ce cours aborde la résolution de problèmes d’optimisation à l’aide de graphes : optimisation de projets à l’aide de graphes gradués et orientés, optimisation de réseaux à l’aide d’arbres de valeur minimale, optimisation de projets à l’aide du chemin critique dans un graphe orienté et gradué.

Durée : 25 heures (1 unité)

Contenu

• Représentation d’une situation par un graphe;

• Chaînes et cycles ;

• Graphes gradués;

• Arbres;

• Graphes orientés;

• Chemin critique;

• Résolution de problèmes.

Évaluation

Un examen ministériel dans un centre d’éducation des adultes.

Seuil de réussite de l’évaluation pour fin de sanction : 60 %