Qu'ont en commun tes amitiés, les molécules et les cartes routières ?

Les amitiés, les molécules et les cartes routières peuvent toutes se dessiner de la même façon : des points reliés par des traits. Les mathématiciens appellent un tel dessin un graphe, et la théorie des graphes étudie ces structures, qui modélisent des relations entre objets pris deux à deux. Les points sont des sommets, les traits des arêtes. Dans un graphe d'amitiés, les gens sont les sommets et une arête signifie qu'ils se connaissent. Dans une molécule, les atomes sont les sommets et les liaisons chimiques les arêtes. Sur une carte routière, les carrefours sont les sommets et les routes les arêtes, chacune portant une longueur ou un temps de trajet : c'est exactement ainsi que les GPS calculent ton itinéraire.

Le domaine est né d'une énigme. En 1736, Leonhard Euler se demande si l'on peut traverser les sept ponts de Königsberg une seule fois chacun, et son article est considéré comme le premier de la théorie des graphes. Le mot graphe lui-même est venu plus tard, en 1878, quand James Joseph Sylvester a emprunté l'idée aux dessins de molécules des chimistes.

Les graphes mesurent aussi la proximité entre les gens. Paul Erdős, un mathématicien qui a publié au moins 1 525 articles et voyageait avec tout ce qu'il possédait dans deux valises, a inspiré le nombre d'Erdős : ses coauteurs ont le nombre 1, leurs coauteurs le nombre 2, et ainsi de suite. C'est la longueur du plus court chemin jusqu'à lui dans le graphe des collaborations. Celui d'Albert Einstein vaut 2. La plupart des mathématiciens qui en ont un tournent autour de 5.