Optimisation et graphes

Secondaire V

CST-TS-SN

Savoirs

Programmation linéaire (3 séquences)
- Système d'inéquation du premier degré à deux variables;
- Représentation de contraintes et de la fonction à optimiser (fonction objectif ou économique);
- Détermination et interprétation des sommets et de la région-solution (fermée ou non);
- Modification des conditions de la situation pour la rendre plus efficiente.
Graphes (CST)
- Représentation et modélisation d'une situation à l'aide d'un graphe;
- Comparaison de différents graphes:
  - Graphes simples;
  - Graphes orientés;
  - Graphes colorés;
  - Graphes valués;
  - Graphes connexes;
  - Graphes complets.
- Recherche de chaînes ou de cycles eulériens et hamiltoniens, d'un chemin critique, de la chaîne la plus courte, d'un arbre de valeurs minimales ou maximales ou encore du nombre chromatique.

Domaine où les graphes sont particulièrement utiles: