D
ossier
23
Le problème des sept ponts de Königsberg, à l’origine de la théorie des graphes : peut-on faire un tour complet de
la ville en passant une fois, et une seule, par chacun des ponts ? Euler démontre que c’est impossible.
© À partir de blobbotronic Juulijs - Fotolia
© DR
Claire Mathieu
CNRS, École normale supérieure, Paris
La théorie des graphes est née avec Euler, et
l’étude formelle de la traversée des ponts de
Königsberg, puis a vu sa notoriété en partie renforcée
au XIX
e
siècle, avec la conjecture des 4 couleurs. Pour
autant, avant le développement de l’informatique, les
graphes n’étaient qu’un sous-domaine de la combinatoire,
tandis qu’ils sont désormais omniprésents !
Ainsi, la résolution de systèmes laplaciens est en passe
d’être transformée par la théorie des graphes. Dans ces systèmes, de forme
Ax
=
b
,
A
est symétrique, ses
lignes sont de somme nulle et ses éléments non diagonaux négatifs. Apparaissant naturellement dans
des problèmes de réseaux, de calcul scientifique ou de vision par ordinateur, ils correspondent à la loi de
La théorie des graphes, outil
mathématique des temps modernes
