Bases de la théorie des graphes

Dans la ville russe de Königsberg, sept ponts enjambent les bras de la Pregel qui coule de part et d’autre de l’île de Kneiphof. Est-il possible, en partant d’un quartier quelconque de la ville, de traverser tous les ponts sans passer deux fois par le même et de revenir au point de départ ? En 1738, Euler démontra qu’il n’existait aucun chemin répondant à cette question.

Beaucoup d’auteurs considèrent que cette démonstration a donné naissance à la théorie des graphes.

La théorie des graphes est actuellement utilisée pour formaliser des problèmes dans des champs d’application très variés. En effet, cette théorie est utilisée dans de nombreux domaines tels que :

  • la chimie,
  • la biologie,
  • les sciences sociales,
  • le génie industriel,
  • etc.

Elle permet de formaliser des structures, des génomes, des relations, des réseaux, des structures etc. La théorie des graphes constitue l’un des instruments les plus courants et les plus efficaces pour résoudre des problèmes discrets.

Cette synthèse de la théorie des graphes est le support de mon enseignement dispensé en Licence Système d'Information à l'IAE de l'Université de Savoie.

Pour aller plus loin ...

Ouvrages de base: