mercredi 13 décembre 2017
Le défi des 1001 graphes
Par Didier Müller, mercredi 13 décembre 2017 à 06:27 - Enigmes/casse-tête
Le 30 septembre 2015, l'équipe de recherche en Théorie des graphes de la Flinders University d'Adelaïde (Australie) donnait le départ d'un concours ouvert à tous sur le globe, intitulé FHCP Challenge.
Elle mettait à disposition de chercheurs, d'ingénieurs et de tous les curieux une collection de 1001 graphes, c'est-à -dire des réseaux de points connectés entre eux. Pour les participants, le défi consistait à démontrer l'existence, dans chacun de ces graphes, d'un circuit passant par les arêtes de ce graphe et visitant une fois et une seule tous ses sommets.
L'objectif des organisateurs était de faire un « état de l'art » des méthodes connues par les scientifiques et de mesurer leur efficacité en pratique. Le concours devait également permettre d'identifier les graphes vraiment difficiles, c'est-à -dire ceux que personne n'arriverait à résoudre.
Lire l'article de David Coudert et Nathann Cohen sur Interstices
lu 3114 fois