Rien de plus banal que de consulter un plan du métro, utiliser un catalogue de liaisons aériennes pour préparer nos déplacements, envoyer un mail, utiliser un moteur de recherche pour trouver une page web, découvrir quels sont les amis de nos amis sur un réseau social, faire un plan de table pour un mariage… Le point commun de toutes ces actions ? C’est l’utilisation implicite ou explicite des relations qui existent entre les éléments de ce que vous manipulez : les liaisons entre stations de métro ou les aéroports pour aller d’un point à un autre, les connexions entre les diverses machines (routeurs) qui acheminent un message de votre boîte mail à celle de votre correspondant, les hyperliens sur lesquels il est possible de cliquer et qui constituent un maillage des pages du web (la Toile), les liens entre des personnes dans des réseaux sociaux, familiaux, professionnels, etc.
La notion commune est donc ici celle de relation entre les entités du système que vous manipulez. Elle peut être représentée par un objet abstrait étudié en théorie des graphes, une branche des mathématiques peu connue du grand public. Un graphe est la donnée d’un ensemble d’éléments, nommés les sommets (qui vont représenter les stations, les pages web, les gens, etc.), et les relations entre ces sommets que l’on appelle les arêtes. Par exemple le graphe des liaisons aériennes directes de la compagnie Air France contient une arête entre les sommets Paris et New York, car cette compagnie propose un vol direct entre ces deux villes. Par contre il n’y a pas d’arête entre Clermont-Ferrand et New York, car aucun vol direct ne les connecte.
Multigraphes, graphes pondérés, orientés…
Plusieurs sous-catégories de graphes ont été proposées pour tenir compte de spécificités du système à modéliser : graphes pondérés pour représenter des coûts de trajets ; graphes orientés pour capturer l’idée de relations asymétriques du type « X est strictement plus riche (ou plus grand, etc.) que Y » ; les hypergraphes pour mettre en relation plus de deux sommets ; les multigraphes pour exprimer le fait que deux sommets peuvent être liés par plus d’une relation, etc.). Mais le point important est que tout cela capture des relations entre des sommets.
Dessiner un petit graphe est facile. En voici un qui contient six sommets et sept arêtes. Dans un graphe, deux sommets quelconques sont soit reliés directement (comme a et c ou f et d) soit pas (comme a et b ou c et f). Bien sûr dans celui-là, il est possible « d’aller » de d vers a en transitant par b et c (ou par b et e). C’est ce que l’on appelle un chemin que va suivre une personne ou un message électronique pour voyager.
L’informatique joue un rôle central dans l’exploitation des graphes. Les ordinateurs permettent de les stocker et les manipuler automatiquement (par exemple pour chercher des plus courts chemins entre deux sommets donnés). Malgré la puissance croissante des machines, et malgré l’apparente simplicité de ces objets, de nombreux problèmes sont encore non résolus. Par exemple, on ne sait pas traiter dans un temps raisonnable les problèmes NP-complets. Des équipes universitaires un peu partout en France et dans le monde travaillent sur ce thème. Des doctorats sont soutenus, des conférences internationales sont organisées, des postes de chercheurs ou d’enseignants-chercheurs sont ouverts aux concours à l’université, des entreprises exploitent des graphes, souvent dans le cadre d’activités de recherche opérationnelle (optimisation de la mise en place de services, d’utilisations de ressources, de circulation des biens, etc.), des scientifiques les utilisent pour représenter les relations entre des espèces animales ou végétales ou pour visualiser les liens entre des individus d’un groupe humain donné ou pour relier des données entre elles… C’est un domaine de recherche vivant, actif, dont les applications réelles et potentielles sont multiples mais qui est pourtant très mal connu du grand public.
Les graphes permettent donc, au travers d’applications informatiques, de guider et d’optimiser vos trajets mais peuvent aussi aider des firmes à cerner vos communautés, vos goûts, vos relations en explorant les liaisons de vos réseaux sociaux. Associée à des techniques d’intelligence artificielle par exemple, cette information est précieuse pour vous « modéliser » et vous proposer à la vente des produits, des services, des rencontres… Un peu comme Google utilise le « graphe des pages web » (entre autres choses) pour vous proposer les contenus les plus adaptés à vos requêtes.
Les graphes ont été inventés et développés principalement au cours du XXe siècle, même si le génial mathématicien suisse Leonhard Euler a produit dès le XVIIIe siècle un premier résultat important et toujours utilisé dans ce champ disciplinaire qui n’avait pas encore de nom. Arrêtons-nous quelques instants sur ce résultat classique. L’histoire dit que des habitants de la ville de Königsberg demandèrent à Euler de les aider à résoudre une énigme : comment, en se promenant, passer une et une seule fois par tous les ponts de la ville tout en revenant au point de départ à la fin de la balade ? L’histoire de grandes idées débute parfois sur des questions bien futiles…
Le génie d’Euler a été de voir que la réponse à cette question n’était pas de nature géométrique mais combinatoire. Le plan précis des ponts n’est pas important, mais les relations entre les ponts est quelque chose de central, ce que l’on obtient en construisant le « graphe des ponts ». Ses travaux ont permis de caractériser les graphes ou il était possible de passer exactement une fois par chaque arête. Cela a permis de démontrer que le problème de promenade dominicale des habitants de Königsberg n’avait pas de solution. Mais, plusieurs siècles après, ces résultats servent de base à des algorithmes pour résoudre des problèmes de déplacement de véhicules : comment un camion peut collecter les ordures en parcourant les rues d’un quartier sans repasser inutilement par des rues déjà traitées plus tôt ? Le domaine de l’optimisation de tournées de véhicules utilise ce concept pour diminuer les trajets inutiles et polluants. La théorie des graphes est riche de possibilités : répondre à certaines questions qu’elle soulève, comme on le fait par exemple lors de jeux mathématiques, peut faire surgir des solutions opérantes pour d’autres applications.