​Le début de la théorie de graphes se trouve en 1736 avec le problème des Sept Ponts de Königsberg. D’abord, Königsberg c’était une ville de la Prusse, qui maintenant s’appelle Kaliningrad en Russie, laquelle c’était une ile avec divers ponts. Le problème consistait à trouver la façon de faire une route pour la citée en passant seulement une fois par chaque pont. Néanmoins, Leonhard Euler, un mathématicien, démontrait que c’était impossible. Ce problème est considéré le premier article de l'histoire de la théorie de graphes.  

​

​

​

​

​

​

​

​

​

​

 

                                            Leonhard Euler                                         Le problème des sept ponts de Königsberg 

​

​

Depuis  ce moment il commencent à apparaitre des nouvelles applications de cette théorie. En 1847 on trouve l’application des graphes dans les lois de Kirchhoff, dans l’analyse des réseaux électriques, pour calculer le voltage et le courant. 

En 1852, il se propose un nouveau problème nommée le problème des quatre couleurs. Cette fois, Francis Guthrie cherchait de colorer tous les pays d’une carte du monde avec  quatre couleurs, en regardant qu’aucun couleur soit répété dans deux pays voisins.  

​

​

​

​

​

​

​

​

​

                                                     Problème des quatre couleurs                             Francis Guthrie 

​

Ensuite, l’année 1857, Arthur Cayley résoudrait le problème de l’énumération des isomères en utilisant des graphes. Donc on peut apercevoir une contribution dans le domaine de la chimie. 

 

​

​

​

​

​

         

​

                                                   Arthur Cayley                                                                                  Arbre de Cayley                                                           

En 1936, le mathématicien Dénes König, écrit le premier livre sur la Théorie de Graphes.  

                                                                                                                                                              

 

 

 

                                                                                                                                                                                                         

                                                                                                                                                                                                         

 

 

                                                                                                           Dénes König 

​

En 1953 Shimbel introduit les calculs en utilisant cette théorie au APSP (All Pairs Shortest Path), c’est-à-dire, les chemins plus courts entre tous les pareils.  

​

L’année 1956, il se propose le premier modèle pour résoudre le problème du chemin le plus court, aussi appelé SSSP ( “Single Source Shortest Path” ). C’est Lester Ford Jr qui a l’idée. Et en 1959 il apparaisse l’algorithme Dijkstra, pour calculer le SSSP, lequel sera très utilisé pour faire des routes. 

​

​

​

​

​

 

                                                                             

 

                                                                                                         Lester Ford Jr.

​

Pendant les années suivants beaucoup d’algorithmes sont reconnus pour calculer le APSP et aussi le SSSP. On trouve quelques personnages très importants dans le calcul du APSP comme: Floyd Warshall, Donald Bruce Johnson ou Mikkel Thourup.