Modéliser avec des graphes

1. Décrire un réseau par un graphe

Des pages web reliées par des liens, des services qui dépendent les uns des autres, des routeurs reliés par des câbles : l’informaticien passe son temps à manipuler des réseaux. Le graphe est l’outil mathématique qui les décrit tous de la même façon, avec des points et des flèches.

Le programme de mathématiques (arrêté du 4/06/2013, module « Graphes et ordonnancement », partie « Graphes ») fixe le contenu de ce chapitre :

Le programme demande des situations « très élémentaires », traitées « sans théorie générale ». Il n’impose aucune méthode pour les niveaux ni aucun algorithme précis pour les chemins optimaux : les méthodes de ce cours (dont l’algorithme de Dijkstra) sont des choix, d’autres sont acceptées si elles sont correctes. La notion de connexité est hors programme. L’ordonnancement d’un projet (méthodes MPM et PERT) est traité au chapitre MATH-10 ; les règles du calcul matriciel, au chapitre MATH-08.