Chapitre II : Cadre
théorique
II-1. Aperçu
historique
La théorie des graphes est née en 1736 avec la
communication d'Euler dans laquelle il proposait une solution au
célèbre problème des ponts de Königsberg.
Euler proposa le problème suivant : deux
îles (A et B sur la figure ci-dessous) sur la rivière Pregel
à Königsberg étaient reliées entre elles ainsi qu'aux
rivages à l'aide de sept ponts. La question est : lors d'une
promenade, est-il possible de passer sur tous les ponts de la ville une et une
seule fois?
C
B
A
D
Euler introduisit deux nouveautés : d'abord il
remarqua que ce problème peut être remplacé par celui
consistant à tracer une figure géométrique sans lever le
crayon et sans repasser plus d'une fois sur un même trait.
D
B
C
A
En plus, cette façon de présenter ce qui
semblait, à cette époque, comme un casse-tête, et qui
l'aida à expliquer la preuve que ce problème n'a pas de solution
inaugure, en fait, une nouvelle technique de modélisation de situation.
Depuis cette date et jusqu'à la première
moitié du dix neuvième siècle, on ne trouve pratiquement
aucune trace de travaux faits par des mathématiciens sur ce type de
sujet. En 1847, Kirchhoff (1824-1887) et un peu plus tard Cayley (1821-1895)
développeront chacun de son côté la théorie des
arbres. Möbius (1790-1868) présenta, dans l'un de ses cours en
1840, la conjecture des quatre couleurs qui affirme que quatre couleurs
suffisent pour colorier n'importe quelle carte plane. Ce problème resta
à l'état de conjecture jusqu'en 1976, année durant
laquelle Appel et Haken présentèrent une preuve de ce
théorème.
C'est surtout au vingtième siècle que l'on peut
observer une sorte d'engouement des mathématiciens envers la
théorie des graphes, engouement dû en grande partie aux
problèmes, de plus en plus complexes posés par l'économie,
le commerce, l'industrie et surtout par les problèmes d'organisation et
de logistique. C'est à König(1936) que revient l'honneur
d'écrire le premier ouvrage consacré entièrement à
la théorie des graphes.
Claude BERGE (BERGE, 1967), dans son ouvrage
« Théorie des graphes et ses applications »
publié en 1958, donna à cette théorie une structure
unifiée et abstraite rassemblant l'état des résultats
épars des recherches jusqu'à cette date. Ce livre est encore, de
nos jours, considéré comme une référence
incontournable en matière de théorie des graphes. En 1959,
l'informaticien néerlandais Edgser DIJKSTRA a proposé un
algorithme qui permet de déterminer un plus court chemin entre deux
sommets d'un graphe orienté et qui sert, entre autres, aux
systèmes de navigation.
Depuis, la théorie des graphes est devenue un domaine
à part entière des mathématiques au même titre que
l'algèbre, la géométrie et l'analyse.
Nous nous proposons, dans la suite de présenter la
théorie des graphes telle que présentée dans nos jours
dans les publications destinées à la formation des enseignants du
cycle secondaire.
| 
