Graph
création en cours...
La théorie des graphes
On fait généralement remonter la théorie des graphes au problème dit « des ponts de Königsberg » (Kaliningrad). Résolu par Leonhard Euler en 1736, ce problème, à l'allure de casse-tête, s'énonce ainsi : est-il possible, en partant d'une zone de la ville, de retourner dans la même zone en traversant chacun de ses sept ponts une fois et une seule ?
La théorie des graphes sert avant tout à représenter et à organiser les tâches de façon optimale : après avoir traduit un problème sous forme de graphe, on cherche des méthodes systématiques qui permettent de trouver la succession la plus rapide ou la moins coûteuse pour effectuer toutes les tâches.
De fait, ses applications pratiques sont très diverses : optimisation des réseaux de transport – transports routiers ou transports d'information –, conception de réseaux électriques, de réseaux de communication, mécanique statistique, formules chimiques, informatique théorique, sciences sociales, géographie, architecture…