Premières notions sur les graphes en série ES |
|
![]() |
La théorie des graphes
C’est pour résoudre le célèbre problème des « ponts de Königsberg » que Leonhard Euler a posé les fondements de la théorie des graphes, qui s’est surtout développée depuis la deuxième moitié du 19e siècle et connaît une grande effervescence depuis les années 30.
Quelles applications ?
La théorie des graphes est un outil de modélisation et donc de résolution de problèmes, utilisée dans un grand nombre de disciplines (mathématiques, physique, économie, etc.).
Concrètement, elle s’applique dans de nombreux domaines :
Selon quelle démarche ?
La résolution de problèmes de graphes est un domaine essentiellement développé par les informaticiens pour lesquels un graphe est une structure de données, tout comme un arbre ou un tableau.
Exemple 1- Sur les ponts
![]() |
Königsberg, 1736 : Sept ponts enjambent la Pregel, reliant quatre quartiers de la ville. Les habitants se demandent s’il existe un trajet leur permettant d’emprunter une seule fois tous les ponts. |
![]() |
Euler modélise le problème et ouvre ainsi une
nouvelle théorie. Les quartiers sont les sommets du graphe, les ponts les arêtes. Il y a quatre sommets (l'ordre du graphe est 4), au sommet A arrivent trois arêtes (le degré de A est 3). Le problème posé induit deux questions : existe-t-il un trajet partant d'un point donné, passant par toutes les arêtes une et une seule fois (chaîne eulérienne) ? Ou bien existe-t-il une chaîne eulérienne revenant au point de départ (cycle eulérien) ? |
A Königsberg, rebaptisée depuis Kaliningrad, il y a deux nouveaux ponts, l'un entre B et C et l'autre entre B et A. Y a-t-il une chaîne eulérienne ? Où faudrait-il construire un autre pont pour obtenir un cycle eulérien ?
Exemple 2- À l’école
Une école doit faire passer des tests à quatre élèves : Adrien, Sophie, Charlotte et Matthieu. Sept disciplines sont concernées : les mathématiques, la physique, la biologie, le français, l'anglais, l'espagnol et l’histoire.
Adrien doit passer les mathématiques, la physique et l'anglais, Sophie les mathématiques, la biologie et le français, Charlotte les mathématiques, l'anglais et l'espagnol et Matthieu la physique, le français et l'histoire.
Quel est le nombre minimal de plages horaires à prévoir pour qu'aucun élève n'ait à passer deux tests simultanément ?
On peut modéliser la situation par le graphe suivant :
![]() |
les sommets représentent les disciplines, les arêtes
relient les disciplines dont les tests ne peuvent avoir lieu simultanément. Les plages horaires sont représentées par des formes géométriques (ou par des couleurs). On attribue à chaque sommet une forme, deux sommets adjacents ne pouvant avoir la même. Le sous-graphe complet M, A, E (tous les sommets sont adjacents) nécessite trois formes. Le dessin prouve que trois sont suffisantes pour le graphe. Ainsi le nombre chromatique du graphe est trois. |
Si Adrien doit aussi passer le test d’histoire, le nombre chromatique devient supérieur ou égal à quatre.
Un dessin prouve qu'il est de quatre.
Les graphes en série ES
Objectifs
Divers documents sur les graphes sont disponibles sur ce serveur