Cette brochure est un document d’information sur la théorie des graphes destiné aux professeurs de mathématiques enseignant en BTS informatique de gestion pour accompagner le programme de ce BTS applicable dès la session 1998. En annexe de ce fascicule figure un extrait de ce programme officiel concernant les graphes.

Une première partie propose une présentation théorique suffisamment simple pour être accessible au non-spécialiste et suffisamment générale pour lui permettre d’avoir une vision globale du sujet.
Après une introduction qui présente la théorie des graphes et fait état de la notion de complexité d’un algorithme, suit un chapitre consacré au vocabulaire et définitions courantes. Des algorithmes pour la plupart matriciels traitent ensuite des problèmes des chemins de longueur fixée, de la fermeture transitive, du problème du plus court chemin et du calcul du rang d’un sommet.

La seconde partie propose des applications pédagogiques.
Un choix d’exercices est proposé associant étroitement graphes et calcul matriciel, montrant que les problèmes relatifs aux graphes peuvent se traiter avec l’outil informatique et proposant des exemples d’utilisation des graphes en gestion (problèmes de choix multicritères ; méthode Electre, problèmes d’ordonnance des tâches : méthode PERT).
Les exercices et les thèmes d’étude sont de type et de niveaux variés : des exemples concrets, des méthodes pratiques permettant à l’étudiant de s’approprier les notions de base, des algorithmes dont les déroulements ont été explicités sur des exemples, des applications de gestion.