Théorie des graphes

Ces représentations constituent des modèles abstraits de réseaux reliant ces objets. Ces modèles sont constitués par la donnée de « points », appelés des sommets, et de « liens » entre ces points, appelés arcs ou arêtes selon que le graphe est orienté ou non. Les méthodes utilisées pour résoudre des problèmes de ce domaine ont des applications dans tous les domaines où intervient la notion de réseau : réseau social, réseau informatique, télécommunications, etc.

On fait généralement remonter la naissance de la théorie des graphes au célèbre problème des ponts de Königsberg qui passionnait la bourgeoisie prussienne du XVIII^e siècle : La Ville de Königsberg, sur la Pregel, était pourvue de 7 ponts et la question était de savoir si l’on pouvait imaginer une promenade dans la ville qui emprunterait chacun des 7 ponts une fois et une seule pour revenir à son point de départ. On sait maintenant qu’une telle promenade n’est pas possible et on doit à Euler une démonstration de l’impossibilité de cette promenade.  Pour cela, Euler a défini un type de graphes parcourables qu’on a appelés par la suite les graphes eulériens.  Ce sont les graphes qui passent par toutes les arêtes et que l’on peut tracer sans lever le crayon.