# La théorie des graphes dans l'enseignement – au croisement de champs disciplinaires et des formations universitaires

Theresia Tabchi, Hussein Sabra, Bernard Riera

► To cite this version:

Theresia Tabchi, Hussein Sabra, Bernard Riera. La théorie des graphes dans l'enseignement – au croisement de champs disciplinaires et des formations universitaires. Journal sur l'enseignement des sciences et technologies de l'information et des systèmes, 2024, 23, pp.0004. 10.1051/j3ea/20240004. hal-04765518

HAL Id: hal-04765518

https://hal.science/hal-04765518v1

Submitted on 4 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# La théorie des graphes dans l'enseignement – au croisement de champs disciplinaires et des formations universitaires

Theresia Tabchi*, Hussein Sabra, Bernard Riera

CReSTIC, Université de Reims Champagne Ardenne
CReSTIC - UFR Sciences Exactes et Naturelles - Moulin de la Housse - BP 1039 - 51687
Reims CEDEX 2

Contact : theresia.tabchi@gmail.com

**RESUME** : Dans cet article, nous parlons de la théorie des graphes dans l'enseignement supérieur. Nous allons essayer de présenter des caractéristiques didactiques de cette théorie qui se développe à l'interface entre les mathématiques et l'informatique. La théorie des graphes admet des champs d'application divers et variés dans l'ingénierie, la modélisation, et dans différents domaines de recherche. En effet, son déploiement dans l'enseignement, devenu nécessaire, soulève plusieurs questions. Nous cherchons à caractériser les formes possibles d'un tel enseignement dans divers parcours de formation tels que les mathématiques, l'ingénierie et l'informatique. Ainsi, nous cherchons à caractériser les formes envisageables pour enseigner la théorie des graphes au supérieur, en tenant compte du contexte spécifique de l'enseignement et de l'impact potentiel de ce contexte sur les choix à effectuer pour structurer l'enseignement de cette matière. Pour ce faire, nous étudions huit ouvrages dédiés à cet enseignement. En outre, nous identifions les défis auxquels les enseignants peuvent être confrontés dans la définition des contenus à enseigner, en passant des cours d'introduction aux domaines d'application spécialisés. Par ailleurs, nous illustrons nos propos en nous penchant sur la formation des automaticiens, où la théorie des graphes joue un rôle essentiel dans l'analyse et la modélisation des systèmes complexes, qu'ils soient discrets ou continus. Nous terminons par quelques propositions pour l'enseignement.

**Mots clés** : Théorie des graphes, enseignement, mathématiques et interactions, formations universitaires, formation des automaticiens.

## 1. Contexte

Dans ce travail, nous nous intéressons à la théorie des graphes. Nous cherchons particulièrement à caractériser les formes possibles d'un enseignement de la théorie des graphes au supérieur en fonction des contextes d'enseignement (mathématiques, ingénierie, informatique, etc.). Nous mettrons en évidence la diversité des choix qui existent au niveau

© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
des contenus, de leur présentation et de leur organisation pour un enseignement de la théorie
des graphes au supérieur.

La didactique des mathématiques, comme discipline scientifique, offre un large éventail
d'outils et de méthodes pour explorer les mathématiques dans l'enseignement et la formation.
Cependant, les recherches en didactique des mathématiques sur la théorie des graphes restent
encore peu développées. La thèse de Tabchi [1] constitue une avancée notable dans ce
domaine, examinant des pratiques d'enseignement de la théorie des graphes. Parallèlement, le
Groupement de Recherche CNRS DEMIPS (Didactique et Épistémologie des
Mathématiques, liens avec l'Informatique et la Physique, dans le Supérieur) a joué un rôle
crucial en facilitant la réflexion sur les interactions entre les mathématiques et l'informatique,
où la théorie des graphes émerge à l'interface de ces deux disciplines.

## 2. La théorie des graphes, recherche, application et enseignement

La théorie des graphes fait partie des mathématiques discrètes qui s'inscrit dans le cadre
des mathématiques « contemporaines ». Elle occupe une place importante dans le champ de
recherche en mathématiques discrètes [2]. Elle possède une réelle importance
épistémologique vu qu'elle se déploie dans différents domaines mathématiques et a des
applications concrètes dans les différents domaines scientifiques [3]. Les graphes fournissent
une introduction à la modélisation, à l'optimisation, à la recherche opérationnelle et aux
mathématiques expérimentales [4,5]. Ils permettent d'établir des liens entre la théorie et les
applications, ce qui est particulièrement important dans certaines filières telles que
l'ingénierie, où la relation entre la théorie et la pratique est cruciale pour rendre les
mathématiques plus pertinentes pour les étudiants [6].

Ferrarello et Mammana [7] soutiennent que l'intégration de la théorie des graphes dans les
programmes scolaires permet d'initier les élèves à la modélisation, de développer leurs
compétences de raisonnement, et d'établir des liens avec la vie réelle. Par conséquent, elle
peut contribuer à développer une compréhension approfondie des mathématiques qui va au-
delà de la simple mémorisation de règles, mais qui permet aux élèves de percevoir les
mathématiques comme un cadre pour aborder des questions pertinentes de la nature et des
produits de la création humaine [7]. Dans ce contexte, la théorie des graphes est un bon outil
pour modéliser des problèmes.

Les graphes jouent de même un rôle crucial dans l'enseignement des mathématiques au
niveau universitaire dans divers domaines, notamment l'informatique, l'ingénierie et
l'économie. Leur importance réside dans leur efficacité en tant qu'outils pour modéliser des
problèmes réels, les rendant très applicables dans des domaines variés tels que les réseaux de
transport, la télécommunication, les réseaux sociaux et la planification des tâches [8, 9, 10].
Par ailleurs, Milková [8] souligne l'aptitude de la théorie des graphes à stimuler la pensée
critique des étudiants, à élargir leur créativité et à les initier à divers problèmes pratiques.

Dans un article de synthèse qui explore des applications potentielles de la théorie des
graphes en informatique et met l'accent sur ces applications dans les réseaux sociaux, Majeed
et Rauf [11] soulignent l'importance des graphes dans la modélisation et l'analyse de la
dynamique des réseaux sociaux. Selon l'article, la théorie des graphes, avec ses concepts
largement utilisés dans la conception d'algorithmes, joue un rôle crucial dans de nombreuses
applications en informatique. Par exemple, dans le réseau Group Special Mobile (GSM), la
représentation graphique des structures cellulaires hexagonales et des tours de communication est essentielle pour renforcer la sécurité du réseau contre les attaques en temps réel et hors ligne. Les problèmes complexes d'ordonnancement des tâches et des vols trouvent des solutions efficaces grâce à des approches basées sur les graphes. Dans le domaine de l'Internet des objets (IoT), la théorie des graphes est utilisée pour le regroupement, l'évaluation des risques, la diffusion de l'information et l'évaluation des vulnérabilités. De plus, l'émergence de la technologie blockchain ouvre de nouvelles applications, telles que l'allocation des ressources informatiques, la modélisation des contrats intelligents, l'analyse des transactions et l'amélioration des systèmes de santé. En vision par ordinateur, la théorie des graphes est un outil puissant pour abstraire les processus et analyser des applications complexes, démontrant ainsi sa polyvalence et sa praticité dans la formation de la technologie moderne et des applications.

Dans leur étude de 2023, Tiwari et Swati [12] soulignent la diversité des applications offertes par la théorie des graphes dans le domaine des mathématiques appliquées, mettant en avant son rôle essentiel dans la résolution de problèmes à travers différentes disciplines. Selon les auteurs, les concepts de la théorie des graphes sont largement utilisés pour étudier et modéliser des applications dans des domaines variés, démontrant des liens avec l'algèbre, l'analyse, la géométrie, la théorie des nombres, la probabilité et la topologie. La polyvalence de la théorie des graphes s'étend à ses applications dans d'autres branches de la science, notamment en informatique, dans la coloration de cartes et la sécurité des réseaux. Son utilisation dans ces domaines met en évidence son impact pratique et sa pertinence pour relever des défis spécifiques et optimiser des processus, affirmant ainsi son importance croissante dans les domaines de l'informatique appliquée et de la recherche opérationnelle.

Dans son ouvrage sur les applications de la théorie des graphes dans l'ingénierie et l'informatique, Deo [13] met en avant l'importance cruciale de cette théorie dans divers domaines pratiques tels que l'analyse des réseaux électriques, la conception de circuits, les structures de données et la recherche opérationnelle. Il souligne que ces applications conduisent souvent à des graphes de grande taille, impossibles à analyser sans l'aide d'ordinateurs, ce qui explique l'intérêt croissant pour cette théorie à l'ère numérique. Il recommande d'adapter l'enseignement de la théorie des graphes aux besoins spécifiques des étudiants en fonction de leur discipline, ce qui en fait un outil essentiel pour les formations en génie électrique, informatique, recherche opérationnelle, et mathématiques appliquées.

La théorie des graphes constitue un champ de recherche en plein expansion. En revanche, les contenus dans l'enseignement supérieur ne sont pas toujours stabilisés et sont parfois diffus. Dans l'enseignement supérieur, la théorie des graphes est enseignée dans différentes filières en France (mathématiques, maths-info, informatique, ingénierie). Les potentialités de la théorie des graphes dans la recherche comme dans l'enseignement peuvent la rendre assujettie à différentes formes de présentation notamment dans le choix des concepts à mettre en avant, dans leur présentation, ainsi que dans les liens établis entre eux et avec diverses applications.

Nous explorons la théorie des graphes et les modalités d'enseignement de ce domaine mathématique dans divers parcours de formation. Différentes approches de ce domaine à l'intersection entre mathématiques et autres disciplines existent. Ainsi, nous allons caractériser les formes envisageables pour l'enseignement de la théorie des graphes au supérieur, et ce : 1) en fonction du contexte spécifique de l'enseignement (buts de l'enseignement, attentes, parcours de formation) ; 2) l'influence potentielle de ce contexte sur
les choix à effectuer pour un enseignement de la théorie des graphes. Ainsi, nous allons apporter des réponses aux questions suivantes :

Q1 : Quelles sont les formes possibles d'un enseignement de la théorie des graphes au supérieur ?

Q2 : Comment pouvons-nous caractériser l'influence du contexte institutionnel de la formation (parcours, disciplines, débouchés professionnels, etc.) sur les choix effectués par les enseignants ?

Nous commencerons par mettre en place des outils d'analyse adaptés à la théorie des graphes afin de mener une étude didactique prospective sur ce type de contenus.

## 3. Des apports de la didactique des mathématiques pour analyser les ouvrages

### La définition d'un concept par Vergnaud

En 1991, Vergnaud [14] a développé la théorie des champs conceptuels qui vise, selon lui, à étudier le développement et l'apprentissage des compétences complexes, notamment celles qui relèvent des sciences et des techniques. Son objectif principal était de comprendre les filiations et les ruptures entre les connaissances lors du processus de conceptualisation des savoirs mathématiques. Selon Vergnaud [14], l'apprentissage d'un concept ne se limite pas à apprendre sa définition. Un concept prend du sens à travers la résolution de problèmes. Il définit un concept comme étant un ensemble d'invariants utilisables dans l'action, associés à un ensemble de situations qui constituent la référence des différentes propriétés du concept. Par exemple, le concept du cycle hamiltonien, qui est un cycle qui passe exactement une fois par chaque sommet du graphe, revenant au sommet initial sans emprunter la même arête deux fois, prend du sens dans les problèmes théoriques de la théorie des graphes et dans des situations réelles. Considérons, par exemple, un graphe simple avec quatre sommets formant un rectangle, reliés par des arêtes. Pour illustrer un cycle hamiltonien, on pourrait débuter au sommet en haut à gauche, suivre le contour du rectangle dans le sens des aiguilles d'une montre et parcourir tous les sommets sans revenir sur ses pas en revenant au sommet initial, ce qui constitue un exemple classique dans le contexte de la théorie des graphes. Une application pratique des cycles hamiltoniens se retrouve dans le problème du voyageur de commerce (TSP), où l'objectif est de trouver le trajet le plus court en visitant chaque ville une fois et en retournant à la ville de départ. Dans le TSP, les villes représentent les sommets et les routes entre elles représentent les arêtes du graphe, visant à minimiser la distance totale en trouvant un cycle hamiltonien.

### Les registres de représentation sémiotique selon Duval

Duval [15] met en avant le rôle fondamental des « signifiants » dans l'activité mathématique. Pour lui, « représenter » un objet signifie le rendre perceptible par un signe, une image, une description, etc. et appréhender un objet mathématique n'est pas possible sans une représentation faite de cet objet [15]. Il souligne l'importance de distinguer entre un objet mathématique et les représentations possibles de cet objet pour comprendre les mathématiques. Par ailleurs, « toute représentation est cognitivement partielle par rapport à ce qu'elle représente » [15, p. 49-50]. En effet, une représentation particulière ne rend compte que d'une sélection de caractéristiques d'un objet donné, une sélection contrainte par les
capacités inhérentes à la représentation choisie. Nous présentons dans l'encadré 1 des représentations sémiotiques relatives à la théorie des graphes.

Duval [15] distingue entre les représentations sémiotiques qui sont constituées par l'emploi des signes appartenant à un système de représentation ayant ses contraintes propres de signifi ance et de fonctionnement et les représentations mentales correspondant aux images mentales que l'individu développe sur un objet. Les représentations sémiotiques jouent un rôle crucial dans le développement des représentations mentales qu'un individu peut avoir d'un objet mathématique. Elles servent à communiquer ces représentations mentales, les rendant ainsi externes et accessibles aux autres.

Par ailleurs, Duval [15] définit un « registre de représentation sémiotique » comme étant un système comprenant des représentations sémiotiques de même nature et permettant trois activités cognitives fondamentales : la formation de représentations, le traitement et la conversion des représentations. Nous nous intéressons dans notre travail aux registres de représentation sémiotique mobilisés dans un enseignement de la théorie des graphes et les activités cognitives qui en découlent.

Encadré 1. Des registres de représentation sémiotique dont la mobilisation est estimée possible dans le cas de la théorie des graphes

**Registre de représentation par un schéma** : la représentation des objets mathématiques peut être réalisée à travers des schémas ou des figures. Ce registre de représentation offre la possibilité de décrire et d'illustrer les caractéristiques des objets mathématiques abstraits. Les schémas servent non seulement à décrire mais aussi à faciliter la réflexion et les traitements sur ces objets. De plus, il est possible de convertir une représentation par un schéma en d'autres registres de représentation.

**Registre de représentation par un graphe** : ce registre permet de représenter des objets mathématiques tels qu'un chemin ou un cycle, d'effectuer des traitements sur ces graphes (comme la détermination d'un chemin optimal), et de convertir ces représentations par graphes en d'autres registres de représentation, et inversement.

**Registre de représentation par le langage naturel** : la représentation des objets mathématiques peut se faire à travers des phrases ou la rédaction de textes. Ce registre permet de former des représentations des objets mathématiques par des énoncés et de mener une réflexion sur ces objets.

**Registre de représentation par un tableau** : la représentation de certains attributs des objets mathématiques peut se faire à travers des symboles ou des nombres présentés dans un tableau structuré. Il est parfois possible d'effectuer des traitements sur les représentations par tableau, et il est possible de convertir des représentations d'autres registres en des représentations par des tableaux et vice versa.

**Registre de représentation par une matrice** : les matrices peuvent servir à représenter des objets mathématiques en théorie des graphes. En revanche, il est

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
possible d'effectuer des traitements sur les représentations par une matrice en mobilisant des opérations sur les matrices telles que l'addition ou la puissance.

**Registre de représentation formelle :** représentation des objets par des symboles mathématiques (Ø, α, ≤, ...), des quantificateurs (∀, ∃, ...), des opérations (+, −, ×, etc.) et des opérateurs logiques (↔, ⇒, ∧, ∨ ...).

Par exemple, un cycle hamiltonien peut être défini en langage naturel comme un cycle simple dans un graphe G qui passe par chaque sommet exactement une fois et revient au sommet de départ. Il peut également être défini dans le registre formel comme le cycle simple $x_0, x_1, ..., x_{n-1}, x_n, x_0$ dans le graphe $G = (V, E)$ étant donné que $V = \{x_0, x_1, ..., x_{n-1}, x_n\}$ et $x_i \neq x_j$ pour $0 \le i < j \le n$.

Un autre exemple illustre une conversion de la représentation par un graphe dans la figure 1 en une représentation par un tableau.

<figure><img src="image_2.png" /></figure>

<table><caption>Figure 1. La recherche d'un cycle hamiltonien dans le graphe pondéré à gauche en utilisant le tableau à droite [16, p. 656]</caption><thead><tr><th>Route</th><th>Total Distance (In Kilometers)</th></tr></thead><tbody><tr><td>ABCD A</td><td>30 + 30 + 25 + 40 = 125</td></tr><tr><td>ABDCA</td><td>30 + 35 + 25 + 50 = 140</td></tr><tr><td>ACBDA</td><td>50 + 30 + 35 + 40 = 155</td></tr><tr><td>ACDBA</td><td>140 [ABDCA backwards]</td></tr><tr><td>ADBCA</td><td>155 [ACBDA backwards]</td></tr><tr><td>ADCBA</td><td>125 [ABCD A backwards]</td></tr></tbody></table>

De même, cette représentation par un tableau (cf. figure 1) permet un traitement qui est la recherche d'un cycle hamiltonien allant du sommet A à lui-même en listant tous les cycles possibles et en calculant la longueur de chacun d'eux.

## Théorie des graphes : objet vs processus

Nous nous appuyons sur Sfard [17] pour définir les objets mathématiques tels que nous les considérons dans la suite de notre travail. Sfard [17] différencie un *objet* d'un *processus*. Selon elle, considérer une entité mathématique comme un objet revient à la percevoir comme une structure statique, présente dans un certain espace et temps. En contraste, envisager une notion comme un *processus* signifie la considérer comme une conception opérationnelle d'une notion, une potentialité émergente d'une série d'actions plutôt qu'une réalité concrète.

Sfard [17] souligne que les conceptions opérationnelles et structurelles d'une même notion mathématique sont complémentaires, bien qu'elles puissent paraître incompatibles. Elle soutient que les concepts mathématiques peuvent être définis structurellement et opérationnellement et que la capacité de les percevoir comme *processus* et objets à la fois est indispensable pour une « compréhension » des mathématiques. Par exemple, un cycle hamiltonien peut être considéré à la fois comme un objet et comme un *processus*. Trouver le cycle hamiltonien sur un graphe implique la conception opérationnelle du concept, et le cycle hamiltonien obtenu à la suite de ce *processus* représente la conception structurelle du concept.
Dans la suite de notre travail, et en ce qui concerne les graphes, nous adoptons la définition d'un concept présentée par Vergnaud [14], tout en admettant que celui-ci peut être envisagé à la fois comme un processus et comme un objet, comme le souligne Sfard [17]. Nous rejoignons aussi Sfard [17] en ce qui concerne la distinction entre l'aspect statique d'un objet et la nature dynamique d'un processus.

# 4. Sélection des ouvrages et choix effectués par les concepteurs

Notre méthodologie de consultation des ouvrages prend appui sur une consultation des choix effectués en termes de contenus et de leur organisation dans les ouvrages sélectionnés (cf. annexe 1). Nous nous concentrons particulièrement sur les objectifs explicités par les auteurs dans les préfaces des ouvrages, ainsi que sur les choix qu'ils expriment en termes de contenus et de présentation de ces contenus (cf. annexe 2). Ces choix explicités peuvent en effet nous renseigner sur les caractéristiques de la théorie des graphes, mais aussi sur des points de vue de chercheurs dans le domaine. Ils peuvent nous permettre de mettre à jour d'éventuelles disparités ou tendances communes qui peuvent exister dans les choix de contenus et de leur présentation par des concepteurs poursuivant un même objectif. Ainsi, la consultation des ouvrages nous permettra de cerner le spectre de choix qui existent pour la conception de ressources pour l'enseignement de la théorie des graphes, ainsi que l'influence potentielle des facteurs épistémologiques et institutionnels sur ces choix.

Nous nous intéressons aussi à l'identification, à partir de cette consultation des ouvrages, des spécificités de la théorie des graphes, à savoir : les concepts mathématiques impliqués et leurs relations ; les différentes représentations sémiotiques de ces concepts ; les liens éventuels avec d'autres domaines mathématiques et d'autres disciplines ; et la possibilité d'utiliser la théorie des graphes pour représenter ou modéliser des phénomènes issus de la vie réelle. Nous souhaitons ainsi faire apparaître d'éventuelles disparités ou tendances communes existantes dans la présentation de mêmes contenus mathématiques.

Pour illustrer nos analyses, nous considérons plus particulièrement les concepts de chemin et cycle considérés comme des notions fondamentales en théorie des graphes par les concepteurs des ouvrages. Nous examinons plus particulièrement les parcours eulériens, les parcours hamiltoniens et les plus courts chemins. En effet, les problèmes de parcours sont présents dans les premiers chapitres des ouvrages de la théorie des graphes que nous avons consultés, et dans les premières sections des chapitres portant sur les graphes dans les ouvrages de mathématiques discrètes. Ainsi, pour chacun de ces concepts, nous nous intéressons à son émergence dans l'histoire, aux théorèmes fondamentaux et leurs preuves présentés dans les ouvrages, aux algorithmes mobilisés dans des preuves ou dans la résolution des problèmes, aux registres de représentation sémiotique mobilisés et aux activités cognitives qui en découlent (représentation, traitement et conversion) [15]. Nous examinons également les liens établis par les auteurs avec d'autres domaines mathématiques, d'autres disciplines, ainsi qu'avec des applications dans la vie réelle.

La caractérisation des choix effectués dans ces ouvrages nous permettra de cerner la conception d'une unité d'enseignement de la théorie des graphes, et de caractériser les influences potentielles de facteurs didactiques (choix des contenus et leur présentation dans les ouvrages), épistémologiques (particularités de la théorie des graphes en tant que champ mathématique), et institutionnels (public cible, visé par l'ouvrage).
**4.1. Présentation des ouvrages consultés**

Dans le but de caractériser l'univers du possible au niveau des choix pouvant être effectués dans la conception d'un enseignement de la théorie des graphes dans divers contextes institutionnels, nous avons consulté neuf ouvrages destinés à être diffusés pour l'enseignement de la théorie des graphes au supérieur (cf. annexe 1). Bien que ces ressources ne soient pas exhaustives pour un public d'enseignants ou d'étudiants, elles ont été sélectionnées en raison de la diversité de leurs destinataires et de leurs années de publication, couvrant ainsi une période étendue. Trois de ces ouvrages inscrivent la théorie des graphes dans le champ des mathématiques discrètes et comprennent des chapitres dédiés à la théorie des graphes [16, 18, 19] tandis que les six autres sont entièrement consacrés à la théorie des graphes [20, 21, 22, 23, 24, 25]. Les neuf ouvrages sont, sans exception, rédigés par des mathématiciens qui mènent des recherches principalement en mathématiques discrètes. Ils s'adressent à un public varié, comprenant des enseignants, des chercheurs en formation, et des étudiants issus de différentes filières, notamment les mathématiques, l'informatique, l'ingénierie, et « mathematics education ». Les ouvrages sont publiés sur un intervalle de cinquante années (entre 1963 et 2018), une époque marquée par l'évolution significative de la théorie des graphes, selon Bondy et Murty [22].

**4.2. La théorie des graphes dans la recherche et l'enseignement, selon les auteurs des ouvrages consultés**

Nous avons examiné les préfaces des ouvrages susmentionnés afin de cerner les points de vue des auteurs des ouvrages sur la théorie des graphes et la place qu'elle occupe dans la recherche et dans l'enseignement.

Les auteurs des ouvrages soulignent unanimement le rôle significatif de la théorie des graphes dans le paysage mathématique actuel, tant dans l'enseignement que dans la recherche. Selon ces auteurs, la théorie des graphes se distingue par sa capacité à établir des liens avec d'autres domaines mathématiques et à représenter des situations provenant d'autres domaines scientifiques ou de la vie réelle. Les auteurs mettent l'accent sur le rôle de la théorie des graphes dans l'élaboration d'algorithmes.

Bondy et Murty [22] ont particulièrement mis en évidence son évolution dynamique sur plusieurs décennies marquée par des avancées majeures telles que la création d'algorithmes efficaces à temps polynomial, la découverte de problèmes NP-complets (cf. Encadré 2) et la résolution de la conjecture des quatre couleurs. Ils ont également souligné son application pratique dans divers domaines mathématiques et disciplines. Des auteurs comme Berge [20] et Wilson [23] renforcent cette idée en mettant en avant comment la théorie des graphes trouve des applications dans des domaines aussi variés que la recherche opérationnelle, la génétique ou encore la linguistique.
Un algorithme destiné à résoudre un problème est une procédure précise qui prend une instance du problème en entrée et fournit une solution en sortie. Deux questions théoriques clés se posent alors : la première est de s'assurer de la fiabilité de l'algorithme, et la seconde est d'évaluer son efficacité. Cette efficacité est souvent mesurée par la « complexité de l'algorithme ».

La complexité d'un algorithme se réfère au nombre d'opérations de base, comme les calculs arithmétiques ou les comparaisons, nécessaires pour son fonctionnement. Ce nombre varie en fonction de la taille et de la nature de l'entrée. La complexité temporelle représente le temps requis pour accomplir le traitement. Si cette complexité est limitée par un polynôme en fonction de la taille de l'entrée, l'algorithme est dit polynomial.

Les algorithmes polynomiaux sont précieux car ils peuvent être exécutés efficacement sur un ordinateur, même avec des entrées volumineuses. Cependant, une complexité exponentielle rend l'algorithme inefficace pour des entrées de taille modérée, caractérisant ainsi les problèmes NP-complets.

Toutefois, Bondy et Murty [22] soulignent brièvement les liens entre la théorie des graphes et d'autres domaines mathématiques tels que la topologie, la géométrie et la probabilité. Ils mentionnent également que des concepts de l'algèbre, de l'analyse et de la théorie des nombres sont appliqués à la théorie des graphes avec des résultats significatifs et que les méthodes de résolution issues de cette théorie se révèlent pertinentes dans d'autres domaines mathématiques tels que l'algèbre et la théorie des ensembles. Bondy et Murty [22] mettent l'accent sur l'importance de la théorie des graphes dans les sciences appliquées, en particulier dans la quête d'algorithmes efficaces qui ont stimulé de nombreuses recherches sur la nature des graphes. En effet, résoudre certains problèmes exige la mise au point d'algorithmes répondant à des critères précis d'efficacité et de complexité (cf. encadré 2).

West [24] et Rosen [18] soulignent que la théorie des graphes offre aux étudiants une formation solide dans la construction de preuves, en particulier par induction mathématique, renforçant ainsi leur aptitude à penser de manière abstraite. Epp [16] précise que cela les familiarise avec l'emploi d'arguments logique et avec la déduction, tout en les habituant à travailler avec des concepts abstraits et à utiliser des représentations formelles.

D'après Bondy et Murty [22], la théorie des graphes est parfaitement adaptée à l'enseignement des mathématiques pour plusieurs raisons, notamment parce qu'elle se prête à être visualisée comme la géométrie. Ils estiment qu'elle offre des concepts accessibles nécessitant peu de prérequis, ainsi que des problèmes ouverts encourageant une réflexion approfondie de la part des étudiants. Bien que la théorie des graphes soit considérée comme pertinente pour l'enseignement, West [24] souligne qu'il n'y a pas encore de consensus sur la manière de l'aborder.

En se référant aux perspectives des auteurs mentionnés précédemment concernant l'enseignement et la recherche en théorie des graphes, nous dégageons les idées centrales suivantes. La théorie des graphes est en constante évolution et entretient des connexions avec divers autres domaines mathématiques et disciplines. Elle présente un intérêt pour de nombreux domaines d'enseignement et de formation, offrant à la fois des défis de recherche
et des opportunités d'enseignement. Toutefois, sa présentation et son intégration dans les programmes éducatifs restent des sujets de réflexion, comme en témoignent les préfaces des ouvrages que nous avons examinés. Ces particularités de la théorie des graphes soulèvent des questions quant à la « cohérence » des programmes universitaires, notamment en ce qui concerne le choix des contenus, leur présentation et leur intégration avec d'autres branches des mathématiques et disciplines connexes. Pour mieux comprendre les diverses approches possibles dans la conception d'un module d'enseignement sur la théorie des graphes, nous avons examiné les objectifs et les choix explicités par les auteurs dans les préfaces des ouvrages consultés.

## 4.3. Présentation des objectifs et des choix explicités par les auteurs des ouvrages consultés

Dans cette partie, nous avons examiné les préfaces des ouvrages pour identifier les passages où les auteurs énoncent leurs objectifs et les choix qu'ils effectuent. Il est intéressant de constater qu'un choix évoqué dans une préface peut englober à la fois le contenu et la manière dont il est présenté. Prenons l'exemple de West [24] :

> « Many results in graph theory have several proofs; illustrating this can increase students' flexibility in trying multiple approaches to a problem. I include some alternative proofs as remarks and others as exercises » [24, p. XIII].

Dans cette citation, la décision de West d'inclure différentes preuves peut être vue comme un choix en termes de contenus. De plus, la façon dont il les présente, soit comme des remarques soit comme des exercices, reflète également un choix en termes de présentation.

Nous avons observé que la longueur des préfaces varie considérablement, allant d'une page et demie à neuf pages. En effet, il peut exister des choix implicites non explicités par les auteurs dans les préfaces. Cependant, notre analyse se concentre uniquement sur les choix clairement formulés par les auteurs.

Les objectifs à atteindre des auteurs d'un ouvrage influencent la manière dont ils présentent le contenu. Cela englobe la manière de clarifier les relations entre concepts, d'établir des liens avec d'autres branches des mathématiques, d'illustrer les applications dans divers domaines ou situations réelles, le choix des représentations (que ce soit par écrit, schéma, tableau, etc.), ainsi que le niveau de formalité adopté pour exposer les idées.

Pour notre analyse, nous avons mis en relation les objectifs déclarés par les auteurs dans les préfaces des ouvrages et les choix formulés en termes de contenus et de leur présentation. Nous présentons ci-dessous les principaux résultats de notre analyse.

Nous avons remarqué que certains choix sont partagés par les auteurs de plusieurs ouvrages. Par exemple, six ouvrages expliquent comment structurer le contenu pour de manière à être utilisé dans un cours d'introduction à la théorie des graphes. Ce choix nous semble cohérent avec un objectif énoncé dans huit des ouvrages : offrir aux enseignants des ressources adaptées à leur enseignement.

Certains choix énoncés par les auteurs semblent être divergents. Par exemple, deux auteurs choisissent de placer les « contenus de base » au début de leurs ouvrages ou dans les premières parties de leurs chapitres. Bien que ces deux choix soient différents, ils ont en commun l'objectif de faciliter l'identification des contenus qu'ils considèrent de base par les

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
lecteurs. En revanche, d'autres choix peuvent refléter des tensions au niveau de la
structuration du contenu. Par exemple, certains auteurs peuvent préférer limiter la
dépendance entre les chapitres, tandis que d'autres peuvent privilégier une progression
spiralaire des concepts à travers plusieurs chapitres. Ces deux choix sont divergents étant
donné que le développement en spirale des concepts suppose l'apparition d'un même concept
dans plusieurs chapitres de l'ouvrage, accentuant ainsi la dépendance entre les chapitres.

Nous tenons à préciser que les choix effectués par un enseignant-chercheur concepteur d'un ouvrage, lors de la conception d'un ouvrage, que ce soit en matière de contenu ou de présentation, peuvent être guidés par ses propres objectifs et par le public visé. Pour illustrer cette idée, nous détaillerons ci-dessous certains choix et objectifs des concepteurs, tels qu'ils les ont exprimés dans les préfaces de leurs ouvrages.

Bondy et Murty [22] cherchent à initier les étudiants en mathématiques et en informatique à la théorie des graphes, tout en familiarisant les lecteurs avec la recherche dans ce domaine. Ils choisissent d'inclure des représentations par des graphes pour éclairer les concepts et les notions, et des exercices variés en termes de complexité, ainsi que des problèmes ouverts qu'ils jugent pertinents pour ceux envisageant des recherches en théorie des graphes. Rosen [18], qui souhaite familiariser les étudiants de diverses disciplines (notamment en informatique et en mathématiques) avec les mathématiques discrètes et fournir aux enseignants une ressource adaptable selon leurs besoins, propose des exercices liés à l'informatique et à d'autres secteurs, ainsi que des algorithmes accompagnés de l'analyse de leur efficacité. Il inclue aussi des exemples illustrant les concepts et différentes méthodes de résolution de exercices. Quant à Berge [20], son objectif est de fournir aux lecteurs un outil mathématique adaptable à plusieurs domaines et disciplines comme les sciences du comportement, la théorie de l'information ou encore la théorie des ensembles. Ainsi, il inclut dans son ouvrage des définitions provenant d'autres domaines mathématiques comme l'algèbre ou la théorie des ensembles. Ces variations dans les choix en termes de contenus peuvent être justifiées par les objectifs des concepteurs et les publics cibles des ouvrages.

Dans l'ouvrage de Bondy et Murty [22], destiné à des étudiants en mathématiques et en
informatique, les auteurs se concentrent sur les raisonnements mis en œuvre dans la
construction des preuves avec peu de recours au registre formel dans la rédaction des preuves
exposées dans le registre du langage naturel avec passage à des représentations par des
graphes ; une activité de conversion qui, selon eux, contribue à illustrer les concepts et les
notions. Rosen [18], visant un public varié, utilise un langage simple, avec peu de
formalisme, détaillant les algorithmes en pseudocode, avec des indications montrant les
projets informatiques les plus difficiles. Les choix effectués par Epp [16], dont l'ouvrage est
aussi destiné à un public varié, rejoignent ceux de Rosen [18] en termes de présentation des
contenus. Pourtant, elle choisit un développement en spirale des concepts en les exposant
dans plusieurs chapitres. Ainsi, dans les ouvrages d'Epp [16] et Rosen [18] ciblant un public
similaire, malgré des objectifs communs, font des choix de présentation variés, combinant
des points de convergence et des disparités. Berge [20], dans son ouvrage ayant pour objectif
de fournir un outil mathématique s'appliquant à différents domaines mathématiques et à
différentes disciplines, privilégie l'utilisation du registre formel et l'abstraction des contenus.
Larramendy Valverde et Marie-Jeanne [25], dont l'ouvrage est destiné à un public spécifique
d'étudiants en informatique à l'IUT ainsi qu'aux étudiants de première année en licence «
mathématiques et informatique », optent pour une présentation des algorithmes classiques
comme résultant des concepts mathématiques abordés en amont. De plus, étant donné que
leur public cible est plus restreint que celui des autres ouvrages, les prérequis nécessaires, et
qui sont issus d'un baccalauréat à dominante scientifique, sont exposés en annexe.

Ces choix divers des concepteurs des ouvrages quant à la présentation des contenus dépendent des objectifs de ces concepteurs, du public cible ainsi que des relations particulières qu'ils entretiennent avec la théorie des graphes selon leur domaine de recherche. En revanche, ces choix soulignent clairement le potentiel de la théorie des graphes à :

- Relier des concepts théoriques à des applications concrètes comme intégrer des applications liées aux concepts théoriques abordés dans le cours ;

- Adapter les contenus pour répondre aux besoins variés des utilisateurs, par exemple en offrant des exercices axés sur l'informatique et divers domaines, ou en incorporant des exemples issus de la vie réelle et d'autres disciplines ;

- Proposer des modes de présentations clairs pour faciliter la compréhension, telles que présenter les preuves dans un langage naturel et minimiser l'usage du registre formel.

Cet éventail étendu de choix, concernant les contenus et leur présentation, pouvant être effectués dans/pour l'enseignement, rend l'élaboration d'un module d'enseignement de la théorie des graphes une tâche relativement complexe.

Toutefois, cette diversité, en matière de contenus et de leur présentation illustre le large spectre de choix disponibles pour les enseignants-chercheurs lorsqu'ils conçoivent des ressources pour l'enseignement de la théorie des graphes. Ces choix peuvent être influencés par des considérations didactiques (en lien avec la présentation des contenus), institutionnelles (en lien avec le parcours de formation) ou épistémologiques (en lien avec la recherche). Il est essentiel de reconnaître que ces choix déterminent des orientations générales adoptées par les auteurs, qui peuvent se manifester différemment dans la conception des ouvrages. Nous avons consulté les contenus dans ces ouvrages afin de caractériser la mise en application de ces choix et objectifs. Nous présentons les principaux résultats dans la suite.

## 4.4. Les problèmes autour du concept « parcours »

Les concepts de « chemin » et « cycle » sont considérés comme des notions fondamentales en théorie des graphes par les auteurs des ouvrages. En effet, les problèmes de parcours sont abordés dans les premiers chapitres des ouvrages de théorie des graphes que nous avons consultés, ainsi que dans les premières sections des chapitres dédiés aux graphes dans les ouvrages de mathématiques discrètes. Dans cette section, nous aborderons respectivement les parcours eulériens (§ 4.4.1), les parcours hamiltoniens (§ 4.4.2) et les plus courts chemins (§ 4.4.3). Dans chaque partie, nous fournirons une description analytique de la mise en application des choix déclarés par les auteurs des ouvrages dans les préfaces. Nous avons consulté les chapitres alloués à ces concepts dans chacun des ouvrages dans le but d'identifier les concepts et les notions mis en avant et la manière dont ils sont présentés. Ainsi, pour chaque type de parcours, nous avons considéré : son émergence et son évolution dans l'histoire, les théorèmes fondamentaux présentés dans les ouvrages et les preuves les accompagnant, les algorithmes mobilisés dans les preuves ou pour la résolution de problèmes, les registres de représentation sémiotique mobilisés et les activités cognitives qui en découlent (représentation, traitement et conversion), les liens établis avec les autres

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
domaines mathématiques ainsi qu'avec les autres disciplines, et finalement les situations proposées par les auteurs offrant ainsi des occasions d'appliquer la théorie des graphes dans des activités de représentation et/ou de modélisation de situations issues de la vie réelle.

### 4.4.1 Exemple 1 - Parcours eulériens : chemins et cycles

De nombreux problèmes en théorie des graphes se concentrent sur les parcours eulériens, impliquant l'existence et la construction de chemins ou de cycles. La connexité du graphe est une condition nécessaire, mais pas suffisante, pour garantir l'existence d'un parcours eulérien. De plus, déterminer l'existence d'un parcours eulérien dans un graphe $G$ peut être simplifié en analysant les degrés des sommets du graphe, c'est-à-dire en évaluant le nombre d'arêtes connectées à chaque sommet. Toutefois, dans les situations où ce parcours existe, l'attention se tourne vers la recherche d'une construction possible, souvent élaborée à travers le développement d'un algorithme.

En examinant les différents théorèmes relatifs aux parcours eulériens et leurs preuves, nous constatons qu'ils requièrent peu de prérequis intrinsèques à la théorie des graphes. En effet, une connaissance des définitions fondamentales de la théorie des graphes, telles que graphe, sommet, arête, degré d'un sommet, cycle, chemin simple, graphe connexe, ainsi que l'ajout ou la suppression d'arêtes, est suffisante. Ces notions sont liées, la connexité du graphe et la somme des degrés déterminant l'existence de chemins ou cycles eulériens. Les raisonnements associés ne sont pas nécessairement spécifiques à la théorie des graphes, tels que le contre-exemple minimal ou la maximalité. Certaines preuves mettent particulièrement en évidence la distinction entre une condition nécessaire et une condition suffisante, comme la parité des degrés, nécessaire pour un cycle eulérien, mais non suffisante en l'absence de connexité du graphe.

Les preuves privilégient souvent un langage naturel, accompagné de quelques représentations formelles pour désigner les objets mathématiques. Les auteurs semblent ainsi accorder plus d'importance aux modes de raisonnement qu'aux détails de la notation mathématique formelle. En revanche, dans les exemples et les exercices, plusieurs registres de représentation sémiotique sont mobilisés (langage naturel, formel et par graphe), entraînant souvent des conversions entre ces registres. En ce qui concerne l'algorithme de Fleury, il peut être formulé soit dans un langage formel, soit dans le langage naturel, tout en faisant appel à des représentations graphiques pour expliquer et illustrer les différentes étapes de son exécution. Il est à noter que la construction des parcours eulériens à l'aide de l'algorithme de Fleury, telle qu'elle est présentée dans les ouvrages, ne fait pas appel à des logiciels ; les étapes sont souvent effectuées sur des représentations par un graphe à l'aide de papier et de crayon.

Finalement, les parcours eulériens occupent une place centrale dans divers problèmes de la théorie des graphes où l'application de concepts mathématiques abstraits tels que les chemins et la connexité permet également la représentation ou la modélisation de situations variées issues d'autres disciplines ou de la vie réelle. Ces problèmes présentent une opportunité d'explorer la modélisation dans l'enseignement, incitant les étudiants à réfléchir sur la manière de représenter une situation donnée par un graphe, de choisir les arêtes et les sommets, etc.

La consultation des ouvrages met en évidence la diversité des choix qui existent au niveau des modes de présentation des parcours eulériens. Pour un même théorème, différentes

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
preuves peuvent être proposées, l’algorithme de Fleury pour la construction des parcours eulériens peut être inclus ou non, des registres de représentation sémiotique divers peuvent être mobilisés (par graphe, formel, langage naturel) impliquant souvent des traitements dans ces registres et des conversions entre eux. Par ailleurs, la diversité des applications des parcours eulériens, tant à l’intérieur qu’à l’extérieur du domaine mathématique, offre une flexibilité concernant les choix d’exemples pouvant être effectués pour la conception de ressources pour l’enseignement de la théorie des graphes.

## 4.4.2 Exemple 2 - Parcours hamiltoniens

La recherche de parcours hamiltoniens, au cœur de nombreux problèmes mathématiques en théorie des graphes, nécessite des connaissances préalables similaires à celles requises pour les parcours eulériens, englobant des notions fondamentales telles que graphe, sommet, arête, degré d'un sommet, cycle, chemin simple et graphe connexe. Bien que les définitions des cycles eulériens et hamiltoniens puissent sembler analogues, des distinctions significatives existent. Il pourrait sembler qu'il existe une méthode universelle pour déterminer systématiquement l'existence de cycles hamiltoniens, notamment parce que, dans de nombreux ouvrages, les parcours hamiltoniens sont présentés après les parcours eulériens [16, 18, 21, 23] et les définitions des cycles eulériens et hamiltoniens peuvent paraître analogues. Pour les cycles eulériens, des critères simples, tels que le décompte des degrés des sommets et la vérification de la connexité du graphe, suffisent à déterminer leur existence, facilitant la construction d'un cycle eulérien à l'aide de l'algorithme de Fleury. En revanche, aucun algorithme similaire ni critères définis n'existent pour déterminer l'existence d'un cycle hamiltonien dans un graphe. Néanmoins, en exploitant les propriétés spécifiques des cycles hamiltoniens, il est souvent possible de démontrer qu'un graphe dépourvu de ces propriétés ne peut pas contenir de cycles hamiltoniens.

Certains théorèmes, tels que les théorèmes d'Ore et de Dirac, fournissent des conditions suffisantes pour la présence de cycles hamiltoniens. Bien que des conditions nécessaires soient parfois énoncées dans les ouvrages, aucune condition à la fois nécessaire et suffisante n'a été établie jusqu'à présent pour garantir l'existence d'un cycle hamiltonien.

Les preuves des théorèmes sont formulées dans un langage naturel, tout en intégrant des représentations formelles. Dans certaines preuves, des représentations par graphe sont incorporées pour rendre les concepts plus accessibles. Les exemples et les exercices présentés font appel à diverses représentations (langage naturel, par graphe, formelle et par tableau) avec parfois des conversions d'une représentation à une autre. En outre, plusieurs activités cognitives sont impliquées telles que la conversion d'une représentation à une autre dans les preuves et dans les exemples, les traitements sur des représentations données ou la représentation/modélisation d'une situation par un graphe dans les preuves, les exemples et les exercices.

Les problèmes impliquant des graphes hamiltoniens sont divers et variés, intégrant des connaissances essentielles en théorie des graphes, interagissant avec des concepts tels que les graphes planaires et les sous-graphes couvrants. Les choix distincts effectués par les auteurs influent sur les modes de présentation, comme illustré par les ouvrages de Bondy et Murty. Dans [21], les graphes hamiltoniens sont abordés en relation avec les parcours eulériens et les composantes connexes des sous-graphes, tandis que dans [22], ils sont explorés en lien avec les graphes planaires et hypohamiltoniens. La disparité dans la présentation des cycles

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
hamiltoniens par les mêmes auteurs dans ces deux ouvrages pourrait être attribuable aux évolutions de la théorie des graphes et de ses applications sur une période de trois décennies entre les éditions des livres.

En conclusion, les parcours hamiltoniens peuvent établir des connexions avec d'autres domaines mathématiques en utilisant des concepts tels que la bijection ou le produit cartésien. Ils peuvent également être appliqués à des problèmes provenant d'autres disciplines et à des situations de modélisation de la vie réelle. Leur exploration offre aux étudiants l'occasion de renforcer leur raisonnement mathématique en illustrant le rôle des concepts abstraits dans la résolution de situations concrètes. Ainsi, différentes situations peuvent nécessiter une recherche de parcours hamiltoniens, avec l'utilisation de divers registres de représentation sémiotique. Cette diversité, combinée à l'évolution de la théorie des graphes au fil du temps, contribue à la disparité des modes de présentation des graphes hamiltoniens dans les ouvrages et dans la création de ressources pour enseigner ce concept.

### 4.4.3 Exemple 3 - Recherche du plus court chemin dans un graphe

La recherche du chemin le plus court entre deux sommets d'un graphe vise généralement l'optimisation. Dans un graphe non pondéré, cela correspond au chemin avec le moins d'arêtes, définissant ainsi la distance entre les sommets. En revanche, dans un graphe pondéré, chaque arête est associée à une valeur numérique représentant sa longueur. Il est important de souligner que la longueur peut prendre différentes significations, telles que la distance en kilomètres, le coût d'un trajet ou même la durée, etc. L'objectif est de minimiser la somme des longueurs des arêtes pour obtenir un chemin optimal entre les deux points.

Dans un graphe pondéré, l'algorithme de Dijkstra est utilisé pour trouver le chemin le plus court. Les ouvrages varient dans leur présentation de cet algorithme, certains le décrivant comme un moyen de construire le plus court chemin entre deux sommets spécifiques d'un graphe pondéré [16, 18, 21, 23, 24], tandis que d'autres l'emploient pour rechercher le plus court chemin dans des graphes orientés [19, 20, 22]. Les approches diffèrent également, avec des ouvrages présentant la recherche du plus court chemin comme le développement d'un arbre et l'utilisation d'algorithmes tels que le Breadth-First Search [19, 22, 24].

Certains ouvrages examinés visent à montrer l'efficacité de cet algorithme et fournissent une preuve par induction [16, 18, 24]. L'utilisation fréquente du raisonnement inductif dans l'analyse des algorithmes est soulignée, étant donné que les relations de récurrence jouent un rôle crucial dans leur élaboration. Ces ouvrages détaillent généralement les étapes de l'algorithme et illustrent celles-ci avec des exemples concrets.

Pour expliquer le fonctionnement de l'algorithme de Dijkstra pour la recherche du plus court chemin dans un graphe, les ouvrages font usage de divers registres de représentation sémiotique (langage naturel, formel, par graphe, par matrice et par tableau). Certains ouvrages privilégient le langage naturel, d'autres combinent le langage naturel et le registre formel, et d'autres mobilisent les deux registres de représentation sémiotique, langage naturel et formel. Les étapes de l'algorithme sont souvent illustrées par des traitements dans les registres de représentation formelle, par graphe et en langage naturel. Lorsque la recherche du plus court chemin est effectuée sur des graphes avec un nombre limité d'arêtes, cela se fait généralement à l'aide de papier et de crayon. Par exemple, dans l'ouvrage d'Epp [16], les étapes sont expliquées en convertissant la représentation par graphe en une représentation par tableau. Ce recours à plusieurs registres et à des traitements dans divers registres et à des

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
conversions entre les registres contribue à la disparité des modes de présentation du concept dans les ouvrages.

En résumé, le concept du plus court chemin peut être formulé en utilisant la distance topologique, établissant des liens entre la théorie des graphes et d'autres domaines mathématiques tels que la topologie, en particulier en ce qui concerne la distance métrique et géodésique. Par ailleurs, la recherche du plus court chemin occupe une place centrale dans divers contextes provenant d'autres disciplines scientifiques ou de situations de la vie réelle. Les différentes approches pour définir ce concept, les multiples situations où la recherche du plus court chemin est appliquée, ainsi que la diversité des registres de représentation sémiotique mobilisés dans de telles situations témoignent de la variété des méthodes de présentation envisageables. Cela englobe les choix de concepts et de définitions, l'utilisation d'algorithmes et de constructions spécifiques, ainsi que la mobilisation de différentes représentations sémiotiques.

### 4.4.4 Synthèse et discussion

Ce large spectre de choix identifiés dans les ouvrages pour la conception de ressources pour l'enseignement de la théorie des graphes, dont quelques exemples ont été présentés, témoigne de l'étendue de cette discipline. Cette variété reflète la capacité de la théorie des graphes à répondre aux besoins d'utilisateurs issus de diverses filières de formation en associant des concepts théoriques à des applications concrètes. Ces choix sont également influencés par des considérations didactiques telles que la représentation des profils des étudiants et de leurs éventuelles difficultés, des facteurs institutionnels comme le parcours de formation et le volume horaire, ainsi que des éléments épistémologiques liés à la nature de la théorie des graphes et à ses relations avec d'autres domaines mathématiques et disciplines connexes.

Le large spectre de choix, constitue en effet un levier pour remanier et restructurer une théorie des graphes pour l'enseignement, qu'on peut appeler une « théorie des graphes enseignée ». En revanche, cette caractéristique peut faire émerger des phénomènes dans des formations où les enseignants ont des profils différents (mathématiciens, informaticiens, ingénieurs) et même des approches scientifiques différentes dans la recherche dans une même discipline (par exemple en mathématiques, une approche combinatoire ou une approche algébrique).

Les défis de l'enseignement de la théorie dans des formations professionnalisantes sont un peu différents. Les enjeux sont dans ces cadres institutionnels sont ceux de la présentation de la théorie comme un outil pertinent pour des formes d'applications. Le challenge de l'enseignant est de concevoir des situations contextualisées qui permettent de développer un sens aux concepts employés. C'est ce qu'on va développer dans la section suivante, en s'intéressant à la discipline scientifique qu'est l'automatique, et aux graphes utilisés.

## 5. Automatique et graphes

Les graphes sont un outil important pour les automaticiens des systèmes continus, événementiels et hybrides. Ils peuvent être utilisés, entre autres, pour la commande de différentes manières :
- Modélisation du système : Les graphes peuvent être utilisés pour représenter la structure du système à contrôler, ainsi que les interactions entre ses différents composants.

- Analyse du système : Les graphes peuvent être utilisés pour analyser les propriétés du système, telles que sa stabilité, sa robustesse et sa performance.

- Conception de lois de commande : Les graphes peuvent être utilisés pour concevoir des lois de commande qui permettent d'atteindre les objectifs de performance du système.

- Simulation du système : Les graphes peuvent être utilisés pour simuler le comportement du système sous différentes conditions.

La distinction entre les graphes utilisés par les automaticiens pour les systèmes continus et ceux pour les systèmes à événements discrets est importante, car les caractéristiques et les modèles de ces deux types de systèmes sont fondamentalement différents. Les graphes utilisés par les automaticiens pour les systèmes continus mettent l'accent sur la modélisation des comportements en temps continu, tandis que ceux pour les systèmes à événements discrets se concentrent sur la modélisation des changements d'état et des événements discrets dans le temps.

Parmi les graphes utilisés pour les Systèmes Continus, on peut citer :

- Le diagramme de blocs : C'est l'un des graphes les plus utilisés pour les systèmes continus. Il représente les relations entre les composants d'un système dynamique et permet de visualiser le transfert d'énergie ou de signal entre eux.

<figure><img src="image_3.png" /><figcaption>Figure 2. Exemple d'un diagramme de blocs (Source : https://public.iutenligne.net/automatique-et-automatismes-industriels/verbeken/cours_au_mv/chapitre5/chap51.html)</figcaption></figure>

- Le graphe de transfert : Ce type de graphe représente la fonction de transfert d'un système continu, montrant la relation entre l'entrée et la sortie en termes de fréquence. Le graphe de transfert est constitué de « nœuds », et de flèches appelées « chemins ». Il existe un nœud pour chaque grandeur physique (entrée, sortie et grandeurs internes) et un chemin pour chaque fonction de transfert élémentaire entre un nœud « cause » et un nœud « effet ».
<figure><img src="image_4.png" /><figcaption>Figure 3. Un exemple d'un graphe de transfert (Source : Wikipédia)</figcaption></figure>

- Le graphe de liaison (bond-graph en anglais) : Ce type de graphe permet de représenter les flux d'énergie et d'information dans un système et offre une vision unifiée des aspects mécaniques, électriques, hydrauliques et thermiques d'un système.

<figure><img src="image_5.png" /><figcaption>Figure 4. Un exemple de graphe de liaison d'un circuit RLC en série (à gauche) et en parallèle à droite (Source Wikipédia)</figcaption></figure>

Parmi les graphes utilisés pour les Systèmes à Événements Discrets, on peut citer :

- L'automate fini : Un automate fini est un graphe orienté utilisé pour modéliser les systèmes à événements discrets. Les états représentent les conditions du système, et les transitions indiquent les changements d'état en réponse à des événements discrets.
<figure><img src="image_6.png" /><figcaption>Figure 5. Un exemple d'un automate fini (automate déterministe non complet, Source : https://perso.liris.cnrs.fr/sylvain.brandel/wiki/lib/exe/fetch.php%3Fmedia%3Dens:liflf:liflf-cm04.pdf)</figcaption></figure>

- Le réseau de Petri : Les réseaux de Petri sont largement utilisés pour modéliser les systèmes à événements discrets. Ils sont représentés par des graphes bipartis. Ils décrivent les états du système, les transitions entre ces états et les conditions qui déclenchent ces transitions.

<figure><img src="image_7.png" /><figcaption>Figure 6. Un réseau de Petri représenté par un graphe biparti [27]</figcaption></figure>

- Le GRAFCET : Le GRAFCET [26], acronyme de « Graphe Fonctionnel de Commande Étape-Transition », est utilisé principalement pour décrire le comportement

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
séquentiel d'un système en spécifiant les étapes (ou états) qu'il peut traverser et les transitions entre ces étapes.

<figure><img src="image_8.png" /><figcaption>Figure 7. Exemple de GRAFCET avec synchronisation de tâches et ressource commune [28]</figcaption></figure>

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
On constate que les graphes utilisés par les automaticiens sont orientés et composés de plusieurs types de nœuds, avec des arcs qui, le plus souvent, ne relient jamais des nœuds de même type.

Il pourrait être intéressant, dans le cadre d'un cours sur la théorie des graphes pour les ingénieurs, de présenter les différents types de graphes existants et leur utilisation.

## 6. Conclusion

La théorie des graphes rencontre des évolutions récentes du point de vue de la recherche (en théorie, en modélisation et dans les champs d'application de ses outils). De cette évolution de la considération des graphes dans la recherche et dans les applications découlent les enjeux relatifs au déploiement des enseignements en lien avec les graphes dans des différentes formations, comme en mathématique, ingénierie et autres.

Dans le présent article nous avons essayé de répondre aux deux questions :

* Q1 : Quelles sont les formes possibles d'un enseignement de la théorie des graphes au supérieur ?

* Q2 : Comment pouvons-nous caractériser l'influence du contexte institutionnel de la formation (parcours, disciplines, etc.) sur les choix effectués par les enseignants ?

En ce qui concerne Q1, nous avons distingué entre :

- L'introduction de la théorie des graphes dans l'enseignement comme objet principal d'enseignement, ce choix met en évidence des défis relatifs à des présentations des concepts de base qui peuvent engendrer des conceptualisations différentes dans l'apprentissage (§ 4.4) ;

- La mobilisation de la théorie des graphes dans des formations professionnalisantes comme outil pour modéliser, analyser et simuler des systèmes discrets et des systèmes continus (§ 5).

En ce qui concerne l'introduction de la théorie des graphes, le large spectre de choix identifiés dans les ouvrages pour la conception de ressources pour l'enseignement de la théorie des graphes rend compte de l'ample portée de la théorie des graphes. Dans le monde de recherche, nous pouvons nous demander s'il existe « une seule théorie des graphes ou plusieurs ». Cependant, en se basant sur les analyses présentées, nous nous permettons de soutenir l'idée qu'il existe effectivement plusieurs « théories des graphes à enseigner ». Cette perspective souligne la diversité des approches, des applications et des concepts au sein de la théorie des graphes qui peuvent être présentés et enseignés en fonction des besoins spécifiques des apprenants. En reconnaissant cette diversité, les enseignants pourront mieux adapter l'enseignement de la théorie des graphes aux divers profils d'étudiants, aux contextes institutionnels variés et aux objectifs pédagogiques spécifiques, enrichissant ainsi l'expérience d'apprentissage et facilitant la compréhension approfondie de ce domaine mathématique.
La théorie des graphes occupe une place fondamentale dans la formation des automaticiens, qu'ils travaillent sur des systèmes discrets ou continus. Cette théorie offre une richesse d'outils et de concepts qui permettent d'analyser, de modéliser et de simuler une variété de systèmes complexes. Dans le domaine des systèmes discrets, tels que les réseaux de communication, les automates et les systèmes de contrôle, les graphes sont utilisés pour représenter les interactions entre les composants, les flux d'information et les états possibles du système. Quant aux systèmes continus, comme les réseaux électriques, les circuits électroniques et les systèmes dynamiques, la théorie des graphes intervient notamment dans la modélisation des interconnexions entre les différents éléments, la représentation des flux d'énergie ou de matière.

L'enseignement des graphes aux futurs automaticiens peut présenter plusieurs défis. Tout d'abord, il est essentiel de fournir une compréhension approfondie des concepts fondamentaux de la théorie des graphes, tout en les reliant de manière pertinente aux applications spécifiques dans le domaine de l'automatique. Cela nécessite une approche didactique qui met en évidence les liens entre les concepts abstraits des graphes et les problèmes concrets rencontrés dans la conception et l'analyse des systèmes automatiques. En effet, il est nécessaire qu'une réflexion soit menée sur la trajectoire d'apprentissage qu'on développe via des choix d'enseignement entre les concepts de base de la théorie des graphes comme objets d'enseignement et la mobilisation de ces concepts comme outils. Ceci nécessite de choisir une approche adaptée aux enjeux de la formation (approche combinatoire, approche algébrique ou approche algorithmique) et le choix de situations contextualisées adaptées permettant le développement d'un sens en lien avec l'approche choisie. Un autre défi pour les enseignants est d'illustrer la pertinence et l'applicabilité des graphes dans des contextes réels d'ingénierie automatique. Cela implique que les graphes ne restent pas seulement des connaissances sous-jacentes, mais que leur potentiel dans la résolution de problèmes réels et complexes soit mis en lumière de manière plus explicite.

Enfin, avec l'évolution rapide des technologies et des méthodes dans le domaine de l'automatique, il est important que l'enseignement des graphes reste dynamique et soit constamment mis à jour pour refléter les dernières avancées et les nouvelles applications émergentes. Cela peut nécessiter une collaboration étroite avec l'industrie et la recherche académique pour s'assurer que les étudiants soient exposés aux techniques les plus pertinentes et les plus avancées dans ce domaine en évolution constante.

En ce qui concerne la question Q2, l'influence du contexte institutionnel de la formation, y compris les parcours académiques des étudiants et les disciplines liées à l'automatique, peut jouer un rôle significatif dans les choix effectués par les enseignants dans leur enseignement de la théorie des graphes. Voici quelques facteurs qui ont un impact sur les façons dont cela peut se manifester :

**Disciplines liées à l'automatique** : Les enseignants peuvent choisir d'illustrer les concepts de la théorie des graphes en utilisant des exemples spécifiques à l'automatique. Par exemple, dans un cours sur le contrôle des systèmes, les enseignants pourraient mettre l'accent sur les graphes de transition d'états pour modéliser les systèmes dynamiques ou les
diagrammes de blocs pour représenter les boucles de rétroaction. Cette approche permettrait aux étudiants de percevoir directement la pertinence des graphes dans leur domaine d'étude.

**Exigences de la formation et du programme d'études** : Les enseignants peuvent également être influencés par les objectifs et les compétences spécifiques que les programmes d'études exigent des étudiants en matière de théorie des graphes. Par exemple, si un programme met l'accent sur l'application des graphes à des problèmes d'optimisation dans le domaine de l'automatique, les enseignants pourraient concentrer une partie de leur enseignement sur les algorithmes de parcours de graphe et les techniques d'optimisation associées. Il est intéressant de mettre les exigences de la formation aux regards des débouchés professionnels et des besoins du terrain.

**Recherche et tendances dans le domaine** : Les enseignants peuvent également être influencés par les développements récents dans le domaine de la recherche en théorie des graphes et leur application à l'automatique. Les tendances émergentes, telles que l'utilisation de graphes dynamiques pour modéliser des systèmes en évolution dans le temps ou l'application de l'apprentissage automatique aux problèmes de graphes, pourraient être intégrées dans l'enseignement pour refléter les avancées actuelles dans le domaine.

En résumé, le contexte institutionnel de la formation peut jouer un rôle crucial dans les choix didactiques des enseignants en matière d'enseignement de la théorie des graphes, en influençant la manière dont les concepts sont présentés, les exemples utilisés et les compétences qui sont priorisées dans le cadre de la formation. Dans ce cadre et pour créer un équilibre entre tous ces facteurs, des besoins de formation peuvent émerger auprès des enseignants ayant des profils diversifiés, des centres d'intérêt différents dans la recherche, et des liens diversifiés avec le terrain.
Références bibliographiques

[1] Tabchi, T. (2020). Relation entre enseignement et recherche dans le travail documentaire des enseignants-chercheurs – cas de l’enseignement de la théorie des graphes [Thèse de doctorat, Université de Reims Champagne-Ardenne, Université Libanaise].

[2] Gross, J. L., & Yellen, J. (dir.). (2004). *Handbook of graph theory* (2e éd.). Florida, United States of America: CRC Press.

[3] Hart, E. W., & Martin, G. W. (2016). Discrete Mathematics is Essential Mathematics in a 21st Century School Curriculum. Dans E. W. Hart, & J. Sandefour (dir.), *Teaching and Learning Discrete Mathematics Worldwide: Curriculum and Research, ICME-13 Monographs* (p. 3-19). Hamburg: Springer.

[4] Grenier, D., & Payan, C. (1998). Spécificités de la preuve et de la modélisation en mathématiques discrètes. *Recherches en Didactique des Mathématiques, 18*(1), 59-100.

[5] Maurer, S. B. (1997). What is Discrete Mathematics? The Many Answers. Dans J. G. Rosenberg, D. S. Franzblau, & F. S. Roberts (dir.), *Discrete Mathematics in the Schools* (pp. 121-132). American Mathematical Society and National Council of Teachers of Mathematics.

[6] Flegg, J., Mallet, D., & Lupton, M. (2012). Students’ perceptions of the relevance of mathematics in engineering. *International Journal of Mathematical Education in Science and Technology, 43*(6), 717–732.

[7] Ferrarello, D. & Mammana, M. F. (2018). *Graph Theory in Primary, Middle, and High School*. 10.1007/978-3-319-70308-4_12.

[8] Milková, Eva. (2009). Constructing knowledge in graph theory and combinatorial optimization. *WSEAS Transactions on Mathematics*. 8.

[9] Tabchi, T. (2018). University teachers-researchers’ practices: the case of teaching discrete mathematics. *INDRUM 2018 Proceedings*, pp. 432-441.

[10] Tabchi, T., Sabra, H., & Ouvrier-Buffet, C. (2019). Resources for teaching graph theory for engineers – issue of connectivity. *ICMT3 2019 Proceedings*, pp. 323-328.

[11] Majeed, A., & Rauf, I. (2020). *Graph Theory: A Comprehensive Survey* about Graph Theory Applications in Computer Science and Social Networks. *Inventions, 5*(1), 10. https://doi.org/10.3390/INVENTIONS5010010

[12] Tiwari, C. & Swati (2023). An introduction of graph theory in applied mathematics. *Stochastic Modeling and Applications*. 25(1), 301-306

[13] Deo, N. (2016). *Graph theory with applications to engineering and computer science*. Courier Dover Publications.

[14] Vergnaud, G. (1991). La théorie des champs conceptuels. *Recherches en Didactique des Mathématiques, 10*(2.3), 133-170.

[15] Duval, R. (1993). Registres de représentation sémiotique et fonctionnement cognitif de la pensée. *Annales de Didactique et de Sciences Cognitives, 5*, 37-65.

[16] Epp, S. S. (2010). *Discrete mathematics with applications* (4e éd.). Boston: Cengage learning.

[17] Sfard, A. (1991, February). On the Dual Nature of Mathematical Conceptions: Reflections on Processes and Objects as Different Sides of the Same Coin. *Educational Studies in Mathematics*, 22(1), 1-36. Repéré sur http://www.jstor.org/stable/3482237

[18] Rosen, K. H. (2012). *Discrete mathematics and its applications* (7e éd.). New York:
McGrawHill.

[19] Dierker, P. F., & Voxman, W. L. (1986). *Discrete mathematics*. San Diego: Harcourt Brace Jovanovich.

[20] Berge, C. (1963). *Théorie des graphes et ses applications* (2e éd.). Paris: Dunod.

[21] Bondy, J. A., & Murty, U. S. (1976). *Graph theory with applications* (5e éd.). Great Britain: The Macmillan Press Ltd.

[22] Bondy, J. A., & Murty, U. S. (2008). *Graph theory*. New York: Springer.

[23] Wilson, R. J. (1996). *Introduction to graph theory* (4e éd.). Essex: Longman.

[24] West, D. B. (2001). *Introduction to graph theory* (2e éd.). Deli: Pearson education.

[25] Larramendy, I. & Marie-Jeanne, A. (2018). *Introduction à la théorie des graphes*. Paris: Ellipses.

[26] Bondy, J. A., & Murty, U. S. (2008). *Théorie des graphes*. (F. Havet, Trad.) Berlin: Springer.

[27] David, R., Allah, H. (1997). *Du Grafcet au réseau de Petri* (deuxième édition revue augmentée). Editions Hermès, Paris.

[28] IEC 60848. (2012). *GRAFCET specification language for sequential function charts* (3rd edition).

## Biographie des auteurs

**Theresia Tabchi** : Enseignante-chercheure, didactique des mathématiques (section 26) - Université Libanaise, Liban

**Hussein Sabra** : MCF-HDR, didactique des mathématiques (section 26), CReSTIC, Université de Reims Champagne Ardenne

**Bernard Riera** : PU, automatique (section 61), CReSTIC, université de Reims Champagne-Ardenne
Annexe 1 : Les ouvrages consultés, les profils des auteurs et le public destinataire de chaque ouvrage (selon les auteurs)

<table><thead><tr><td>Ouvrage, année</td><td>Domaine de recherche des auteurs</td><td>Public destinataire de l'ouvrage (selon les auteurs)</td></tr></thead><tbody><tr><td>Graph theory with applications (1976) - J.A. Bondy et U.S.R. Murty</td><td>Bondy : Chercheur en théorie des graphes<br>Murty : Chercheur en combinatoire et optimisation</td><td>Le public n'est pas précisé.</td></tr><tr><td>Graph theory (2008) - J.A. Bondy et U.S.R. Murty<fnref n="1" /></td><td>Bondy : Chercheur en théorie des graphes<br>Murty : Chercheur en combinatoire et optimisation</td><td>L'ouvrage s'adresse aux étudiants en mathématiques et informatique ainsi qu'aux enseignants qui envisagent enseigner un cours de théorie des graphes.<br>Il peut également être utilisé comme une introduction à la recherche en théorie des graphes.</td></tr><tr><td>Discrete mathematics with applications (2011) - S. Epp</td><td>Epp : Chercheure en mathématiques, elle s'intéresse aux mathématiques discrètes et à la logique mathématique</td><td>L'ouvrage est destiné aux étudiants en informatique, mathématiques, « mathematics education », futurs ingénieurs ainsi qu'aux enseignants souhaitant enseigner un cours de théorie des graphes.</td></tr><tr><td>Discrete mathematics and its applications (2012) - K. Rosen</td><td>Rosen : Chercheur en mathématiques, il s'intéresse aux mathématiques discrètes et théorie des nombres</td><td>L'ouvrage s'adresse à des utilisateurs suivant des formations variées dont informatique, mathématiques et ingénierie, ainsi qu'aux enseignants qui envisagent enseigner un cours de théorie des graphes.</td></tr><tr><td>Théorie des graphes et ses applications (1963) - C. Berge</td><td>Berge : Chercheur en mathématiques qui a travaillé sur la théorie des graphes</td><td>Le public n'est pas précisé.</td></tr></tbody></table>

<footnote n="1">¹ Bondy et Murty ont rédigé cet ouvrage une trentaine d'années après la publication de la première édition de « Graph theory with applications » en 1976.</footnote>

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
<table><tr><td>Introduction to graph theory (2001) - D. West</td><td>West : Chercheur en théorie des graphes</td><td>Le public n'est pas précisé, cependant l'auteur donne des indications aux enseignants intéressés par l'enseignement d'un cours de théorie des graphes.</td></tr><tr><td>Introduction to graph theory (1996) - R. J. Wilson</td><td>Wilson : Chercheur en théorie des graphes et en histoire des mathématiques</td><td>L'ouvrage est destiné aux étudiants en mathématiques et à des lecteurs appartenant à différents domaines qui souhaitent étudier la théorie des graphes.</td></tr><tr><td>Discrete mathematics (1986) - P. F. Dierker et W. L. Voxman</td><td>Dierker<fnref n="2" /> : Chercheur en mathématiques<br/>Voxman : Chercheur en théorie des nombres</td><td>Le public n'est pas précisé, cependant les auteurs notent l'importance d'un cours de mathématiques discrètes dans divers domaines tels que l'informatique, les mathématiques et d'autres formations axées sur les mathématiques.<br/>Ils donnent des indications aux enseignants souhaitant enseigner un cours de théorie des graphes.</td></tr><tr><td>Introduction à la théorie des graphes (2018) - I. Larramendy Valverde et A. Marie-Jeanne</td><td>Larramendy Valverde : chercheure en mathématiques (équipe Probabilités et Statistique).<br/>Marie-Jeanne : professeur agrégé en mathématiques</td><td>L'ouvrage est destiné aux étudiants en informatique de l'IUT de Montpellier ainsi qu'aux étudiants en première année d'une licence « mathématiques et informatique ».<br/>L'ouvrage est aussi à destination des enseignants souhaitant enseigner un cours de théorie des graphes et préparer leurs travaux dirigés.</td></tr></table>

<footnote n="2">² Nous avons trouvé un seul article pour lui sur les plateformes qui date de 1977 et qui porte sur la théorie des graphes. https://epubs.siam.org/doi/abs/10.1137/0132028?journalCode=smjmap</footnote>

<footnote>© The Author(s). This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</footnote>
Annexe 2 : Les objectifs des ouvrages et les choix d'exposition des contenus, explicités par les auteurs

<table><thead><tr><td>Ouvrage, auteur(s) et année de publication</td><td>Objectifs de l'ouvrage</td><td>Choix des contenus, si explicités par les auteurs</td><td>Modes de présentation des contenus, si explicités par les auteurs</td></tr></thead><tbody><tr><td>Graph theory with applications (1976) - J.A. Bondy et U.S.R. Murty</td><td>L'ouvrage vise à introduire la théorie des graphes. Les auteurs visent à présenter ce qu'ils jugent être les notions fondamentales, ainsi qu'une diversité d'applications, tant dans d'autres domaines mathématiques que dans d'autres disciplines et situations de la vie réelle.</td><td>- Des applications basées sur la partie théorique du cours ;<br>- Une gamme d'exercices proposant différents niveaux de difficulté ;<br>- Un tableau répertoriant un certain nombre de problèmes non résolus en théorie des graphes en annexe ;<br>- Des suggestions de lectures supplémentaires fournies en annexe ;<br>- L'intégration de plusieurs algorithmes accompagnés d'une analyse de leur efficacité ;<br>- Aucune référence à l'exécution des algorithmes à l'aide de logiciels.</td><td>- Traitement « approfondi » des applications ;<br>- Identification des exercices les plus complexes et indications pour leur résolution, le cas échéant, fournies en annexe ;<br>- Introduction de nouvelles définitions dans certains exercices ;<br>- Indication des exercices utilisés dans des sections ultérieures ;<br>- Présentation des propriétés des graphes dans un tableau en annexe.</td></tr><tr><td>Graph theory (2008a) - J.A. Bondy et U.S.R. Murty</td><td>L'objectif initial de cet ouvrage était d'apporter des modifications mineures à l'ouvrage précédent des auteurs intitulé « graph theory with applications ». Ce dernier visait à fournir une introduction à la théorie des graphes pour les étudiants en mathématiques et en informatique. Tout en conservant le même objectif, le présent ouvrage a également pour but de servir d'introduction à la</td><td>- Présentation des contenus à aborder dans un cours de théorie des graphes au niveau universitaire ;<br>- Utilisation de représentations graphiques pour illustrer les concepts et les idées ;<br>- Proposition d'exercices variés de différents niveaux de difficulté ;<br>- Intégration de sections traitant de sujets nécessitant plusieurs notions préalables ;<br>- Mise en avant et discussion de</td><td>- Description détaillée des modes de raisonnement mis en œuvre dans la construction des preuves ;<br>- Indications montrant les exercices les plus difficiles ;<br>- Indications montrant les exercices nécessaires à la compréhension des notions et des concepts abordés ;<br>- Structuration des contenus facilitant leur utilisation dans un cours d'introduction à la théorie des graphes.</td></tr></tbody></table>
<table><tr><td></td><td>recherche en théorie des graphes.</td><td>problèmes ouverts pertinents pour la recherche ;<br/>- Présentation de problèmes de recherche stimulants en théorie des graphes en annexe.</td><td></td></tr><tr><td>Discrete mathematics with applications (2011) - S. Epp</td><td>L'objectif de l'ouvrage est de présenter de manière claire et accessible les concepts des mathématiques discrètes, adaptés aux étudiants de diverses filières telles que : informatique, mathématiques, éducation mathématique et ingénierie. L'objectif principal est de mettre en avant les concepts mathématiques que l'auteur estime crucaux pour les cours d'informatique.</td><td>- Intégration d'une multitude d'exemples pratiques et d'exercices (2600 exercices) ;<br/>- Intégration de sujets jugés fondamentaux dans l'enseignement des mathématiques discrètes pour les étudiants en informatique ;<br/>- Présentation d'aperçus historiques sur certains résultats.</td><td>- Présentation des preuves dans un langage naturel, avec peu de formalisme ;<br/>- Explication détaillée des modes de raisonnement mis en œuvre dans la construction des preuves ;<br/>- Progression graduelle des concepts, réapparaissant dans plusieurs chapitres ;<br/>- Solutions fournies pour certains exercices à la fin de l'ouvrage ;<br/>- Structuration en sous-sections pour la plupart des parties de l'ouvrage ;<br/>- Regroupement des « contenus de base » dans les premières sections des huit premiers chapitres ;<br/>- Structuration des contenus favorisant leur utilisation dans un cours de mathématiques discrètes.</td></tr><tr><td>Discrete mathematics and its applications (2012) - K. Rosen</td><td>L'ouvrage a deux objectifs : Premièrement, il vise à offrir aux étudiants de diverses disciplines une présentation pertinente et claire des mathématiques discrètes, tout en fournissant aux</td><td>- Mise en avant du raisonnement mathématique et des diverses méthodes de résolution des exercices ;<br/>- Accent sur l'induction mathématique ;</td><td>- Présentation des idées dans un langage naturel, avec peu de formalisme ;<br/>- Description des modes de raisonnement mis en œuvre pour construire les preuves ;</td></tr></table>
<table><tr><td></td><td>étudiants en informatique les bases mathématiques nécessaires et en permettant aux étudiants en mathématiques de mieux appréhender les concepts mathématiques essentiels et leurs applications. Deuxièmement, il cherche à fournir aux enseignants un document qu'ils peuvent utiliser dans l'enseignement des mathématiques discrètes, en leur offrant la flexibilité nécessaire pour l'adapter aux besoins de leurs étudiants.</td><td>- Présentation des exercices mettant en avant les applications en informatique et dans divers domaines ;<br/>- Illustration des concepts à l'aide d'exemples ;<br/>- Intégration d'applications issues de la vie réelle ou d'autres disciplines ;<br/>- Intégration de plusieurs algorithmes accompagnés d'une analyse de leur efficacité ;<br/>- Ensemble de projets informatiques proposés à la fin de chaque chapitre ;<br/>- Intégration d'explorations impliquant l'utilisation de logiciels ;<br/>- Intégration d'un ensemble de projets historiques ou axés sur des concepts non abordés dans le texte ;<br/>- Présentation d'aperçus historiques comprenant les biographies de 83 mathématiciens et informaticiens.</td><td>- Indications montrant les exercices les plus difficiles ;<br/>- Présentation de questions d'examen à la fin de chaque chapitre ;<br/>- Présentation des algorithmes dans une forme de pseudocode ;<br/>- Indication des projets informatiques les plus arduis ;<br/>- Regroupement des « contenus de base » dans les premiers chapitres de l'ouvrage ;<br/>- Structuration des contenus facilitant leur utilisation dans un cours de mathématiques discrètes ;<br/>- Réduction de la dépendance des chapitres sur les contenus des chapitres précédents.</td></tr><tr><td>Théorie des graphes et ses applications (1963) - C. Berge</td><td>L'objectif de l'ouvrage est de fournir au lecteur un outil mathématique applicable à divers domaines et disciplines, tels que les sciences du comportement, la théorie de l'information, la cybernétique, les jeux, les réseaux de transport, la théorie des ensembles et les matrices, entre autres.</td><td>- Définitions provenant d'autres domaines mathématiques tels que l'algèbre ou la théorie des ensembles rappelées au fur et à mesure selon les besoins.</td><td>- Présentation formelle et abstraction des contenus ;<br/>- Énoncés courts et nombreux ;<br/>- Énoncés exposés uniquement lorsqu'ils sont nécessaires à la démonstration de théorèmes ultérieurs ;<br/>- Premiers chapitres centrés sur les notions « orientées », et derniers chapitres abordant les notions « non</td></tr></table>
<table><tr><td>Introduction to graph theory (2001) - D. West</td><td>Cet ouvrage peut servir d'introduction à la théorie des graphes pour un cours de premier ou deuxième cycle universitaire, ou même pour deux cours distincts, chacun dispensé sur un semestre.</td><td><ul><li>Illustration des concepts par des exemples ;</li><li>Utilisation de représentations graphiques pour illustrer les concepts et les idées ;</li><li>Présentation des différentes preuves d'un théorème, lorsque cela est pertinent ;</li><li>Mise en avant du raisonnement mathématique ;</li><li>Intégration d'une multitude d'exemples pratiques et d'exercices (plus de 1200 exercices) ;</li><li>Des exercices variés de différents niveaux de difficulté ;</li><li>Intégration de plusieurs algorithmes ;</li><li>Introduction en annexe de notions essentielles telles que celles concernant les ensembles et l'induction pour les étudiants novices en théorie des graphes.</li></ul></td><td>orientées ».</td></tr><tr><td>Introduction to graph theory (1996) - R. J. Wilson</td><td>L'ouvrage vise à offrir une introduction à la théorie des graphes, conçue pour être</td><td><ul><li>Intégration de 250 exercices dans l'ouvrage ;</li><li>Proposition d'exercices de divers</li></ul></td><td><ul><li>Exposition des preuves dans un langage naturel, avec peu de formalisme ;</li><li>Différentes preuves d'un théorème fournies en tant que remarques ou incluses dans des exercices ;</li><li>Définitions de nouveaux termes introduites au fur et à mesure selon les besoins ;</li><li>Indications montrant les exercices les plus difficiles et suggestions pour leur résolution, le cas échéant, fournies en annexe ;</li><li>Présentation des exercices qui requièrent la mobilisation de plusieurs concepts après avoir introduit tous les concepts nécessaires à leur résolution ;</li><li>Report de l'introduction des digraphes à la fin du premier chapitre ;</li><li>Regroupement des « contenus de base » dans les premières sections des chapitres ;</li><li>Structuration des contenus pour faciliter leur intégration dans un cours de théorie des graphes.</li></ul></td></tr></table>
<table><tr><td></td><td>accessible aussi bien aux mathématiciens qu'aux non-spécialistes désireux d'acquérir rapidement une compréhension du sujet.</td><td>niveaux de difficulté.</td><td>base » dans les premiers chapitres de l'ouvrage, incluant des définitions et des exemples de graphes, de connectivité, de chemins et de cycles eulériens et hamiltoniens, ainsi que d'arbres ;<br/>- Introduction des digraphes reportée jusqu'à la troisième partie de l'ouvrage.</td></tr><tr><td>Discrete mathematics (1986)<br/>- P. F. Dierker et W. L. Voxman</td><td>L'objectif de l'ouvrage l'objectif de l'ouvrage est de proposer aux étudiants des sujets à la fois intéressants et utiles, tout en offrant un contenu mathématique robuste.</td><td>- Mise en avant des liens entre la théorie et la pratique en mathématiques discrètes ;<br/>- Soulignement des aspects informatiques liés aux mathématiques discrètes et à leur théorie sous-jacente ;<br/>- Utilisation d'une approche algorithmique pour résoudre plusieurs problèmes ;<br/>- Explications détaillées des différentes étapes d'un algorithme.</td><td>- Introduction de la théorie des graphes dans le troisième et le quatrième chapitre de l'ouvrage composé de onze chapitres ;<br/>- Présentation des algorithmes dans un langage naturel qui est compréhensible par plusieurs langages de programmation ;<br/>- Structuration des contenus pour faciliter leur utilisation dans un cours de mathématiques discrètes ;<br/>- Structuration des contenus pour offrir aux enseignants une flexibilité dans le choix des sujets.</td></tr><tr><td>Introduction à la théorie des graphes (2018) – I. Larramendy Valverde et A. Marie-Jeanne</td><td>L'ouvrage vise à initier les étudiants en informatique de l'IUT de Montpellier ainsi qu'aux étudiants en première année d'une licence « mathématiques et informatique » à la théorie des graphes. Il vise également à offrir aux enseignants une sélection</td><td>- Apparition des algorithmes classiques comme des conséquences des concepts mathématiques introduits au préalable ;<br/>- Priorité donnée à une vision d'ensemble cohérente et rigoureuse ;<br/>- Présentation uniquement des propriétés qui soutiennent la</td><td>- Construction progressive d'une théorie mathématique.<br/>- Introduction des algorithmes classiques comme des conséquences des concepts mathématiques.<br/>- Allègement des notations mathématiques pour éviter un ouvrage trop formel.</td></tr></table>
<table><tr><td>d'exercices pour préparer leurs travaux dirigés, tout en permettant aux étudiants, après lecture, de comprendre des théorèmes et algorithmes non inclus dans l'ouvrage et de développer leurs propres algorithmes.</td><td>structure mathématique ;<br/>- Inclusion d'exercices adaptés à chaque chapitre.</td><td>- Cours succincts mais complets, accompagnés de corrections détaillées pour certains exercices.<br/>- Prérequis présentés en annexe.</td></tr></table>

Huit des neuf ouvrages examinés visent à introduire la théorie des graphes ou les mathématiques discrètes à des étudiants de divers domaines tels que les mathématiques, l'informatique, l'ingénierie, etc. De plus, ils ont pour objectif de fournir aux enseignants des ressources pour leur enseignement. Tous ces ouvrages sont conçus pour être utilisés dans différentes formations, ce qui les rend accessibles à un large éventail d'utilisateurs. La polyvalence de la théorie des graphes dans la représentation et la modélisation de diverses situations, comme décrit par Bondy et Murty (2008a), lui confère une importance dans de nombreux domaines de formation. En outre, dans l'ouvrage "Graph theory" de Bondy et Murty (2008a), un objectif supplémentaire est énoncé : servir d'introduction à la recherche pour les chercheurs en formation dans le domaine de la théorie des graphes.

Dans les préfaces des ouvrages examinés, les auteurs détaillent leurs décisions concernant les contenus et leur présentation en accord avec les objectifs de chaque ouvrage. Nous avons observé que plusieurs auteurs partagent certains de ces choix. Dans le tableau ci-dessus, nous présentons respectivement tous les choix relatifs aux contenus (dans la troisième colonne) et à leur présentation (dans la quatrième colonne) que nous avons relevés, en précisant entre parenthèses le nombre d'auteurs qui les ont explicités.

Dans notre analyse, nous avons répertorié une diversité de choix en termes de contenu, totalisant 29 options, que nous avons regroupées selon plusieurs axes. Ces axes englobent notamment l'utilisation de représentations graphiques pour éclairer les concepts et les idées, l'accent mis sur la corrélation entre la théorie et la pratique dans le domaine des mathématiques discrètes, ainsi que la présentation de contenus adaptés aux cours avancés de théorie des graphes. De plus, nous avons observé une inclusion conséquente d'exercices à différents niveaux de difficulté, ainsi qu'un nombre significatif d'exemples concrets et d'applications issues de la vie réelle ou d'autres disciplines. L'accent sur les différentes approches de résolution des exercices, ainsi que sur le raisonnement mathématique et l'induction, a également été relevé. De plus, certains ouvrages ont mis en évidence l'importance des applications informatiques dans le domaine des mathématiques discrètes, tout en intégrant des sections sur des sujets nécessitant plusieurs notions comme prérequis. En outre, la présence d'explications détaillées sur les étapes d'exécution des algorithmes et des projets informatiques à la fin de chaque chapitre a été notée. Enfin, des aspects historiques, notamment des aperçus sur certains résultats et les
biographies de mathématiciens et informaticiens, ainsi que des suggestions de lectures supplémentaires en annexe, ont également été inclus dans certains ouvrages.

Nous avons identifié un total de 32 choix distincts en ce qui concerne la présentation des contenus, révélant ainsi une diversité des choix adoptés par les auteurs. Certains ouvrages organisent les contenus de manière à faciliter leur utilisation dans un cours d'introduction à la théorie des graphes, tandis que d'autres privilégient le regroupement des notions fondamentales dans les premiers chapitres ou les premières sections des chapitres. La séquence d'introduction des digraphes varie également, certains les reportant à la fin du premier chapitre tandis que d'autres les introduisent plus tard, par exemple, dans la troisième partie de l'ouvrage. L'organisation des contenus est pensée pour offrir aux enseignants une flexibilité dans le choix des sujets, tout en minimisant la dépendance entre les chapitres. Les auteurs adoptent différentes approches dans la présentation des preuves, certains optant pour une description détaillée des modes de raisonnement dans un langage naturel, tandis que d'autres exposent les preuves dans un style plus concis, parfois intégrées dans des exercices. La manière d'exposer les algorithmes varie également, avec certains utilisant un langage naturel commun à plusieurs langages de programmation, alors que d'autres préfèrent une présentation plus formelle. Les indications concernant la résolution des exercices difficiles sont traitées de différentes manières, soit directement dans le texte principal, soit en annexe, et parfois les solutions sont fournies à la fin de l'ouvrage. L'accent sur l'approfondissement des applications, la formalisation des contenus, et la concision des énoncés varie également selon les ouvrages. Enfin, certaines publications incluent des propriétés des graphes exposées dans un tableau en annexe, tandis que d'autres préfèrent les intégrer directement dans le texte.

Il est remarquable de constater que certains choix sont communs à plusieurs auteurs d'ouvrages. Par exemple, l'organisation des contenus de manière à faciliter leur utilisation dans un cours d'introduction à la théorie des graphes est explicitée dans six des ouvrages, ce qui est cohérent avec l'objectif partagé par huit des ouvrages de fournir aux enseignants des contenus adaptés à leur enseignement. Cependant, des disparités peuvent exister parmi les choix énoncés par les auteurs. Certains choix formulés par deux auteurs peuvent être compatibles, comme le regroupement des contenus de base dans les premiers chapitres ou dans les premières sections des chapitres, tous deux visant à faciliter l'identification des concepts essentiels. En revanche, d'autres choix peuvent révéler des tensions l'orientation de la construction des connaissances. Par exemple, la minimisation de la dépendance entre les chapitres et le développement en spirale des concepts présentent des approches divergentes en matière d'organisation des contenus, le développement en spirale impliquant une récurrence des concepts dans plusieurs chapitres et donc une augmentation de la dépendance entre eux.