Le défi des 1001 graphes

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.

De notre côté, nous étions curieux de découvrir si le savoir et les programmes que nous avions accumulés par le passé nous permettraient d’aller très loin, et si participer à ce concours nous amènerait à les améliorer encore. Nous avons remporté ce concours en résolvant 985 graphes.

Un problème connu en théorie des graphes

Les cycles d’un graphe passant une fois et une seule par chaque sommet sont connus dans la littérature scientifique sous le nom de cycles hamiltoniens. C’est un cas particulier du problème du voyageur de commerce, sur lequel cette revue a déjà publié un article. Ce problème a été défini en 1857 par William Rowan Hamilton, un scientifique irlandais, et avait déjà été étudié en 1856 par Thomas Penyngton Kirkman. C’est depuis cette époque un problème très étudié en théorie des graphes.

Le graphe suivant contient un tel cycle : pouvez-vous le trouver en cliquant sur ses liens ? Plusieurs solutions existent, vous pourrez en visualiser une.

Les deux graphes suivants ne sont pas hamiltoniens. Pour le graphe de gauche, l’arête entre les sommets 2 et 4 sépare le graphe en deux parties. Or, pour trouver un cycle hamiltonien, il faut pouvoir aller au moins une fois de la partie gauche vers la partie droite, puis revenir de la partie droite vers la partie gauche. Comme il n’y a qu’une seule arête entre les deux parties, ce n’est pas possible. Une telle arête est appelée un pont, et tout graphe contenant un pont n’est pas hamiltonien.

 

Il est un peu plus difficile de comprendre pourquoi le graphe de droite (la grille) n’est pas hamiltonien. Pour cela, il faut d’abord observer que ce graphe est biparti, c’est-à-dire que l’on peut séparer ses sommets en un ensemble \(I\) (les sommets impairs) et un ensemble \(P\) (les sommets pairs) et observer que chaque sommet de \(I\) n’est relié qu’à des sommets de \(P\) (et réciproquement). S’il existait un cycle hamiltonien, alors ce cycle passerait par le sommet 0 (qui est pair) puis sur un sommet impair, puis sur un sommet pair et ainsi de suite, en alternant. Le graphe contenant 9 sommets en tout, le dernier sommet découvert par le cycle avant de revenir au sommet 0 serait nécessairement un sommet pair. Mais c’est impossible, puisque 0 ne peut pas être relié à un sommet pair !

Le problème du cycle hamiltonien est ce qu’on appelle un problème de décision. Il s’agit de décider s’il est vrai ou faux que le graphe contient un cycle passant une et une seule fois par chacun de ses sommets. Le problème du voyageur de commerce est quant à lui un problème d’optimisation. En effet, il s’agit de trouver le cycle le plus court passant au moins une fois par chacun des sommets.

Règlement du concours

Il suffisait, pour remporter ce concours, et le prix de 1001 USD, d’être le premier à résoudre le problème du cycle hamiltonien pour l’ensemble des 1001 graphes. Si personne n’en était capable, la victoire irait à celui ou celle qui en aurait résolu le plus grand nombre au bout d’un an.

Pour participer à ce concours, toutes les méthodes imaginables étaient autorisées. En particulier, il n’était pas interdit de résoudre le problème… à la main ! Mais la taille des graphes allant de 66 sommets (le plus petit) à 9528 sommets (le plus gros), il était plus raisonnable de le faire par ordinateur.

L’oracle

Dans cet article, nous utilisons le terme « oracle » pour désigner un programme informatique qui, étant donné un graphe, répond « VRAI » s’il a trouvé un cycle hamiltonien (qu’il retourne également) ou « FAUX » s’il a prouvé que le graphe n’est pas hamiltonien (c’est-à-dire qu’il ne contient pas de cycle hamiltonien).

En pratique, l’oracle est l’implémentation d’une des nombreuses méthodes qui ont été proposées par les scientifiques pour résoudre le problème du cycle hamiltonien. Dans ces méthodes, on trouve des algorithmes consacrés à des graphes ayant une propriété spécifique (par exemple la propriété : « tous les sommets sont de degré 3 »). Ces algorithmes nécessitent de savoir détecter si le graphe possède réellement cette propriété, ce qui est parfois difficile à tester. D’autres algorithmes utilisent des méthodes générales, comme la programmation dynamique, le principe de la procédure de séparation et évaluation, ou encore la programmation linéaire. Nous avons choisi d’utiliser une méthode basée sur la programmation linéaire en nombres entiers (voir l’annexe Formulation pour plus de détails sur cette méthode). Cette méthode offre de bonnes performances en général même si elle peut échouer sur de petits graphes.

La table suivante montre le temps de calcul nécessaire à notre oracle pour trouver la solution des premiers graphes. Nous observons des temps de calculs très variables, des graphes plus gros pouvant être résolus beaucoup plus vite que des graphes plus petits. Nous observons surtout des temps de calculs très importants, comme pour le graphe n°12. Le problème du cycle hamiltonien étant difficile à résoudre, il n’est pas surprenant que le temps mis par l’oracle pour retourner sa réponse puisse être très long (des années). Sachant que les graphes ont en moyenne 3000 sommets, l’utilisation de l’oracle n’aurait pas suffi à elle seule. Notons tout de même que, à notre grande surprise, l’oracle a trouvé en 5 minutes la solution du graphe n°1000 qui a pourtant 9058 sommets.

Notre travail a consisté à développer des méthodes spécifiques pour aider l’oracle, en nous basant sur notre compréhension de la structure des graphes. Ces méthodes, que nous décrivons dans la suite, consistent par exemple à découper le problème en sous-problèmes plus petits (voir par exemple la section 2-connexité), à substituer des parties du graphe par des graphes plus simples (section motif de taille 16), à prouver que certaines arêtes peuvent être supprimées, ou encore à imposer un ensemble d’arêtes (l’oracle cherche alors s’il existe un cycle hamiltonien contenant ces arêtes). Pour le graphe n°12, nos méthodes nous permettent maintenant d’obtenir la solution en moins d’une seconde.

Pour les simplifier, il faut les comprendre. Quelle allure ont donc ces graphes ?

À la découverte des graphes

Impossible de résoudre un tel problème sans avoir une représentation visuelle de ces graphes. Nous avons donc commencé à les visualiser un par un, et ce que nous avons découvert nous a beaucoup aidés. En cliquant sur les liens bleus portant le numéro des graphes, vous en verrez autant que nous.

Des presque-cycles

Liens vers les graphes n°58  et n°78.

À notre grande surprise, beaucoup de graphes ressemblaient déjà à des cycles. Notre oracle aurait dû être capable de trouver un cycle hamiltonien tout seul ! Mais à y regarder de plus près, le problème était plus compliqué.

En effet, chacun de ces cycles est en réalité composé de trois brins principaux, liés par un maillage. Il existe beaucoup de façons de faire passer un chemin hamiltonien à l’intérieur de tels maillages, et, pour cette raison, notre oracle avait du mal à se décider car il cherchait à les explorer toutes.

 

De plus, bien que ces graphes semblent n’être qu’un long enchainement du même motif, il existe dans chacun d’entre eux un point particulier autour duquel le maillage est légèrement différent : c’est là que notre oracle devrait concentrer ses efforts, au lieu d’hésiter sur le chemin à emprunter là où le maillage est simple !

 

Pour aider notre algorithme, nous avons tout simplement retiré des arêtes du graphe là où le maillage était simple, afin de ne plus laisser l’oracle hésiter inutilement : il lui restait à ces endroits si peu d’arêtes qu’il avait à peine de quoi faire passer un chemin ! En revanche, nous lui avons laissé faire la partie difficile du travail, aux endroits où le maillage était plus compliqué.

Le motif de taille 16

Liens vers les graphes n°48, 62, 175, 400.

À force de visualiser des graphes en s’interrogeant sur leur structure, nous avons trouvé qu’un petit motif revenait régulièrement. Il n’avait pas l’air assez gros pour poser problème à notre oracle, mais il apparaissait très souvent et semblait avoir été placé là avec une intention très précise.

Ce motif possède 16 sommets, et n’est relié au reste du graphe que par quatre liens : deux liens sont rattachés au sommet central (0 sur la figure), et un lien vers le reste du graphe part de chacun des sommets 1 et 2 (qui ont exactement trois voisins sur la figure).

Quelles sont ses propriétés ? Comment un cycle hamiltonien peut-il passer à travers ce petit motif ? Puisque seuls trois sommets sont reliés au reste du graphe, il n’existe que quatre possibilités :

• Le cycle entre par 0, visite les 16 sommets et ressort par 1 (ou inversement).
• Le cycle entre par 0, visite les 16 sommets et ressort par 2 (ou inversement).
• Le cycle entre par 1, visite les 16 sommets et ressort par 2 (ou inversement).
• Le cycle entre par 0 et ressort immédiatement.
  Plus tard, il rentrera par 1 et sortira par 2 après avoir visité les 15 sommets qui n’ont pas encore été vus (ou inversement).

Nous avons vérifié que toutes ces possibilités étaient réalisables, c’est-à-dire que les liens de ce petit motif permettaient de trouver dans ces 16 sommets les chemins évoqués dans les 4 possibilités ci-dessus. Que pouvons-nous faire avec une telle information ?

Nous pouvons nous rendre compte qu’il existe un graphe plus simple ayant la même propriété, et que ce graphe est un triangle. Il ne nous restait plus qu’à écrire un programme permettant de détecter automatiquement ce graphe à 16 sommets, et de le remplacer par un triangle pour simplifier le travail de notre oracle. En effet, le graphe n°48 qui a 338 sommets est transformé en un graphe à 78 sommets. Le graphe n°400 à 2366 sommets est transformé en un graphe à 546 sommets. D’autres techniques peuvent ensuite être appliquées pour réduire encore la taille du graphe, comme la décomposition en composantes 3-sommets-connexe. Une fois le problème résolu avec ces triangles, on pouvait facilement reconstruire la solution du problème original en analysant, pour chaque motif, les 4 possibilités.

Les ‘BigDegree’

Lien vers le graphe n°268.

Ces graphes se distinguent des autres parce qu’ils ont deux sommets de très gros degré (deux sommets de degré 192 pour le graphe n°268 et les autres sommets sont de degré au plus 6). Ici, l’affichage du graphe ne nous apporte aucune information exploitable.

Maintenant, si nous retirons les deux sommets de plus gros degré, alors une structure se dégage. C’est une sorte de double grille avec des motifs supplémentaires.

Si nous regardons d’encore plus près, nous pouvons voir que le graphe contient de multiples copies du sous-graphe suivant. Les sommets 1, 3, 7 et 9 sont reliés au reste du graphe par une ou deux arêtes. Ce sous-graphe a la particularité que si le cycle hamiltonien arrive par le sommet 1, alors il suivra obligatoirement et dans l’ordre les sommets 1, 2, 3, 6, 5, 4, 7, 8 puis 9 avant de ressortir. Si le cycle arrive par le sommet 3, alors il suivra dans l’ordre les sommets 3, 2, 1, 4, 5, 6, 9, 8, 7 avant de ressortir. Ceci nous indique que le graphe a une structure très forte et que peu de choix suffisent pour forcer un très grand nombre d’arêtes.

Pour trouver les cycles hamiltoniens dans ces graphes, nous avons d’abord remarqué que les sommets de gros degré ont un voisin de degré 2, ce qui permet de fixer une arête du cycle. Nous avons ensuite cherché la seconde arête incidente au sommet de plus gros degré par essai/erreur (voir degré 2), c’est-à-dire en imposant une arête avant d’interroger l’oracle. Celui-ci répond rapidement si ce choix conduit à une impossibilité, auquel cas l’arête est supprimée et on recommence avec une autre, ou si c’est le bon choix.

La famille du 1001

Liens vers les graphes n°703 et n°1001.

Le graphe portant le numéro 1001 a 9528 sommets. Il est beaucoup trop complexe pour notre oracle, mais possède une structure qui nous permet de le décomposer en petites parties. Bien entendu, la visualisation est assez longue et il est nécessaire de déplacer certains sommets manuellement pour y comprendre quelque chose.

Avec un peu de volonté, on arrive au résultat suivant :

On remarque aisément la présence d’une petite trentaine de gros ‘blocs’ denses, liés aux autres par un nombre très réduit de liens. Nous aimerions pouvoir découper ce graphe en séparant les blocs les uns des autres, mais il faut pour cela comprendre la structure des liens qui les connectent entre eux.

Fort heureusement, les liens entre ces blocs et le reste du graphe ne passent que par 4 sommets (voir image ci-dessus) : nous pouvons utiliser cette information pour simplifier le calcul d’un cycle hamiltonien.

En effet, comme pour le motif de taille 16 présenté plus haut, il n’est pas nécessaire de savoir où exactement passe le chemin hamiltonien à l’intérieur d’un bloc donné pour savoir où il doit passer dans les autres blocs : il suffit de savoir en quels points du bloc le cycle hamiltonien entre, en quels points il ressort, et peu importe ce qu’il fait lors de son parcours à l’intérieur du bloc !

Puisque seuls 4 sommets connectent chaque bloc au reste du graphe, il n’existe que très peu de possibilités (au maximum 9), et chaque bloc est suffisamment petit pour qu’il soit possible de calculer cette information.

Le problème des cloches

Les graphes de cette famille sont ceux qui ont su nous résister jusqu’à la fin.

Les plus petits exemples de cette famille présents parmi les 1001 graphes ont été résolus sans problème par notre oracle, mais ils sont rapidement devenus trop complexes. De plus, la visualisation de ces graphes ne nous apprend pas grand-chose.

En revanche, ces graphes possèdent plusieurs symétries au sens de la théorie des groupes (cf. Wikipedia). Nous avons également réussi à décortiquer ces graphes jusqu’à nous rendre compte qu’ils étaient la superposition de centaines de copies de deux graphes très simples, représentés ci-dessous.

 

Malgré cela, et malgré bien d’autres observations faites par la suite, nous n’avons jamais réussi à exploiter leur structure au point de trouver un cycle hamiltonien dans chacun d’entre eux. D’où viennent-ils ? Nos différentes explorations nous avaient indiqué que la structure de ces graphes était très réfléchie.

La réponse à cette question nous a été apportée par les organisateurs après la fin du concours. Ces graphes trouvent leur origine dans le problème combinatoire de change ringing (cf. Wikipedia en version anglaise) : il s’agit d’une façon de faire sonner à tour de rôle les k cloches d’une église jusqu’à avoir entendu toutes les cloches dans tous les ordres possibles (c’est-à-dire toutes les permutations).

Plus précisément, imaginons que 5 cloches sont disposées en face de nous, et qu’à côté de chacune d’entre elles se trouve un sonneur. Les sonneurs sont identifiés par des numéros allant de 1 à 5, et sonnent chacun leur cloche quand c’est leur tour. Après que chaque sonneur a sonné sa cloche, il a la permission d’aller vers une nouvelle cloche (mais attention, une cloche doit toujours avoir un sonneur !) et de recommencer ce processus.

Combien de fois est-il possible de répéter ce processus sans entendre deux fois la même mélodie ? La réponse est \(5!=120\), car c’est le nombre total de mélodies possibles. Pour simplifier le travail des sonneurs, on leur a donné deux façons de se déplacer entre eux afin que les changements soient plus faciles à mémoriser, qui sont appelées les changements de Erin. Est-il toujours possible d’explorer les \(5!\) possibilités en suivant uniquement les changements de Erin ? Si oui, est-il possible de les explorer toutes et de revenir finalement à la position de départ ?

Ce problème est difficile à résoudre, et les auteurs du concours l’avaient traduit en un graphe dont l’existence d’un cycle hamiltonien fournissait une solution au problème précédent. Mais nous étions très loin d’imaginer tout cela en analysant les propriétés du graphe ! Les 16 graphes que nous n’avons pas réussi à résoudre contenaient tous une copie d’un graphe de cette famille, avec parfois plus de 4000 sommets.

Pour les lecteurs curieux d’en savoir plus, les auteurs du concours ont expliqué leur méthode dans un article de recherche disponible en ligne.

Composition de graphes

La 2-connexité

Un graphe est dit connexe s’il est possible de relier toute paire de sommets par un chemin. Un graphe est 2-sommets-connexe si il reste connexe après la suppression de n’importe quel sommet, il est 3-sommets-connexe s’il reste connexe après la suppression de n’importe quelle paire de sommets, et ainsi de suite.

Une condition nécessaire à l’existence d’un cycle hamiltonien est que le graphe soit 2-sommets-connexe. Il est en effet facile de voir que si le graphe n’est pas 2-sommets-connexe, alors il existe un sommet s dont la suppression sépare le graphe en 2 sous-graphes A et B (tels que A et B n’ont ni sommet commun ni arête de l’un vers l’autre), ce qui revient à dire que tout chemin d’un sommet de A vers un sommet de B passe par s. Comme un cycle hamiltonien passe une seule fois par un sommet, une fois arrivé dans B, on ne peut plus revenir dans A pour fermer le cycle.

Le graphe papillon n’est pas hamiltonien.

Maintenant, supposons qu’il existe 2 sommets u et v qui séparent le graphe en 2 sous-graphes A et B (dont la suppression découpe le graphe en 2 sous-graphes). Alors, un cycle hamiltonien dans le graphe est l’union d’un chemin hamiltonien de u à v n’empruntant que les sommets de A et d’un chemin de v à u n’empruntant que les sommets de B.

Cette propriété est très intéressante, car elle permet de découper un graphe en un ensemble de graphes plus petits. En effet, nous pouvons construire 2 graphes, le premier contenant A, les sommets u et v et les arêtes les reliant à A, plus un nouveau sommet z relié à u et v. Le deuxième graphe est construit de la même façon avec B. Il reste à trouver un cycle hamiltonien dans chacun de ces graphes que nous pourrons ensuite assembler pour obtenir un cycle hamiltonien dans le graphe d’origine.

 

Nous avons utilisé ici une décomposition du graphe en composantes 3-sommets-connexes, ce qui se calcule très rapidement (en temps linéaire).

Les sommets de degré 2

Si un sommet est de degré 2, alors nous savons que ses deux arêtes incidentes sont dans le cycle. Ceci nous permet d’identifier dès le départ un ensemble d’arêtes du cycle que nous cherchons. De plus, il est important de remarquer que si le sommet u a deux voisins x et y de degré 2, alors nous pouvons éliminer du graphe toutes les autres arêtes incidentes à u. Ceci simplifie le graphe, diminue le degré d’un certain nombre de sommets, et peut ainsi révéler de nouveaux sommets de degré 2, comme le montre la figure ci-dessous.

  

Nous avons identifié 11 graphes pour lesquels l’application répétée de cette règle permet de résoudre le problème en réduisant le graphe à un cycle, qui n’est autre que le cycle hamiltonien recherché. Ce sont des graphes très denses, c’est-à-dire qu’ils ont un très grand nombre d’arêtes par rapport au nombre de sommets. Par exemple, le graphe nᵒ59 a 40001 arêtes pour 400 sommets (on ne voit pas grand chose sur la figure), et le graphe nᵒ188 a 315283 arêtes pour 1123 sommets. Ces graphes ont tous deux sommets de degré 2 qui de plus ont un voisin commun.

L’organisateur du concours nous a appris par la suite que ces graphes ont un unique cycle hamiltonien et qu’il pensait que le grand nombre d’arêtes pourrait poser problème à de nombreuses méthodes de résolution. En pratique, ces graphes n’ont posé aucun problème à notre oracle qui, en interne, procède de façon similaire en simplifiant les contraintes une à une.

Maintenant, si un sommet u a un voisin de degré 2, alors il nous reste à trouver la bonne arête parmi ses autres arêtes incidentes. Comme cette opération n’est pas simple, nous pouvons d’abord chercher à éliminer des arêtes en montrant qu’elles ne sont pas dans le cycle. Pour ce faire, nous faisons l’hypothèse qu’une arête est dans le cycle et nous interrogeons l’oracle. Si l’oracle nous répond qu’il n’existe pas de cycle hamiltonien contenant cette arête, alors nous pouvons la supprimer du graphe et passer à l’arête suivante. En procédant ainsi, nous pouvons révéler de nouveaux sommets de degré 2 et des sommets incidents à 2 sommets de degré 2, ce qui nous permet de progresser dans la résolution du problème. En règle générale, l’oracle détecte très rapidement les impossibilités, quelques secondes suffisent. Aussi, nous avons limité le temps de calcul de l’oracle à 10 secondes et analysé sa réponse. Lorsque l’oracle répond que le problème est infaisable, nous supprimons l’arête. S’il nous retourne une solution, alors c’est que nous avons trouvé notre cycle. Enfin, s’il ne sait pas décider, nous conservons l’arête et passons à la suivante (ou au sommet suivant si nous avons déjà testé toutes les arêtes). Nous avons utilisé cette technique avec succès pour les graphes ‘BigDegree’, comme par exemple le nᵒ268, ainsi que sur de nombreux autres graphes.

Sous-graphes isomorphes

En décomposant certains des 1001 graphes (en utilisant les petits motifs ou la 2-connexité), nous avons obtenu des morceaux que nous avions déjà vus par ailleurs.

En effet, il se peut tout à fait que le graphe nᵒ150 soit construit en combinant le graphe nᵒ17 avec le graphe nᵒ73 ! Puisque nous avions déjà calculé un cycle hamiltonien sur ces graphes, il était plus intelligent d’essayer d’identifier les morceaux plutôt que de relancer notre oracle sur chacun d’entre eux.

La copie du graphe nᵒ17 qui pourrait se trouver à l’intérieur du graphe nᵒ150, cependant, n’est pas si facile à identifier : la raison est que le nom des sommets dans le graphe nᵒ17 n’est pas celui de leur équivalent dans le graphe nᵒ150.

 

Existe-t-il un programme permettant de déterminer si deux graphes dont les sommets ont des noms différents sont en réalité identiques ?

Il s’agit là du problème dit d’isomorphisme de graphe (cf. Wikipedia). À ce jour, il n’a pas été résolu de façon satisfaisante par la recherche théorique. Certains logiciels, comme Nauty, ont en pratique de très bonnes performances, même si les scientifiques savent qu’il peut demander un temps exponentiel dans le pire des cas (cf. Wikipedia).

Conclusion

Le problème du cycle hamiltonien est un problème NP-complet, ce qui en fait l’un des problèmes combinatoires les plus difficiles à résoudre selon la hiérarchie de la complexité théorique. Malgré tout, il est possible d’écrire des programmes capables de résoudre des instances de grande taille (≈10 000 sommets dans le cas présent).

À la suite de discussions avec les organisateurs, il s’est avéré que l’aspect déterminant de notre approche était l’importance de la visualisation et de l’étude des propriétés des classes de graphes disponibles. Ceci a été rendu possible par l’utilisation d’une librairie JavaScript appelée d3.js, de la librairie SageMath et du solveur de programmes linéaires CPLEX.

En effet, la plupart de nos concurrents ont abordé le concours à travers l’utilisation d’heuristiques connues pour le problème de cycle hamiltonien. Ces programmes effectuent leurs calculs bien plus rapidement mais ne sont pas certains de trouver la réponse : il faut donc les relancer plusieurs fois en « croisant les doigts ». Nous avons pour notre part opté pour une approche plus systématique d’exploration de toutes les possibilités de cycles hamiltoniens : elle est en général plus coûteuse en temps de calcul, sauf si l’on parvient à comprendre la structure des graphes et à en faire bon usage.

Nous n’avons pas eu à visualiser chacun des 1001 graphes, mais beaucoup d’entre eux tout de même. En effet, chaque nouvelle stratégie a été appliquée systématiquement à tous les graphes non encore résolus. Une fois les calculs terminés, nous prenions l’un des graphes restants pour l’observer et comprendre sa structure.

Nous avons envoyé nos 985 solutions deux mois après l’ouverture du concours. Nous avons ensuite fait de multiples tentatives pour résoudre les 16 graphes restant, et laissé tourner des programmes pendant des mois, sans aucun succès.

Ce concours nous aura donné une meilleure intuition de ce que notre oracle était capable de résoudre de lui-même, et des différents obstacles qui le ralentissent dans ses calculs. Nous n’avons cependant pas trouvé de méthode miraculeuse qui lui permettrait de résoudre chacun des 1001 graphes sans intervention (au moins ponctuelle) d’un œil humain.

Après tout, ce n’est que justice : il y avait également beaucoup d’intelligence dans la construction de ces 1001 graphes, et les ordinateurs ne savent jamais qu’obéir aux ordres.