Sherlock Holmes - Résolution

Méthode heuristique

Donnons d'abord une méthode intuitive, qui a malheureusement l'inconvénient de ne pas prouver aisément que la solution trouvée est la seule.
Il sufit de chercher une représentation sous forme de "planning en barre" des présences au château des neuf suspectes, où chacune est représentée par une barre unique. D'après l'énoncé (la coupable est venue plusieurs fois) ceci doit être impossible. Par contre si on élimine cette coupable (elle est unique), et seulement celle-là, le reste doit pouvoir constituer un planning valable. On peut ainsi chercher la coupable par "essais et erreurs".
En éliminant Ann, le reste donne un planning valable mais il est impossible de glisser Ann en un seul intervalle dans ce planning :

Ann est donc la coupable.

Par la théorie des graphes

La méthode précédente nécessite de nombreux essais si on n'a pas la chance d'éliminer d'emblée la coupable.
Une méthode plus efficace utilise la théorie des graphes.
D'ailleurs le problème a été posé à l'origine par un théoricien des graphes : C. Berge en 1980.

Représentons le graphe de la relation "X et Y se sont rencontrées".
Si chaque personne n'est venue qu'une seule fois (dans un seul intervalle), ce graphe doit être un "graphe d'intervalles" c'est à dire représentant une famille d'intervalles, deux sommets étant joints si les intervalles correspondants ont une partie commune.

Un théorème (Gilmore et Hoffman) affirme qu'un graphe est un graphe d'intervalles si et seulement si :
- Il est "triangulé" (c'est à dire que tout cyle de longueur >3 admet une corde)
- Et son complémentaire est un "graphe de comparabilité".

Le graphe ci-dessus n'est pas triangulé : il comporte les cycles AFHG, AGHB et AFEC, tous trois de longueur 4 et tous trois sans corde. C'est à dire que ni l'arc AH ni FG n'existent pour le cycle AFHG, de même ni AH ni BG pour AGHB, et ni AE ni FC pour AFEC.

L'énoncé affirme qu'il y a une seule coupable, il faut chercher à supprimer un sommet unique suffisant à rendre le graphe restant triangulé. Ce sommet appartient à l'intersection des cycles de longueur >3 sans corde, c'est donc A.

Le sous-graphe obtenu en supprimant A est alors un graphe d'intervalles.
Il faut ajouter au moins trois images de A pour supprimer les trois cycles de longueur 4 et Ann est donc venue au château au moins trois fois.

Un cas plus compliqué

Soit le graphe

Il y a deux cycles de longueur 4 sans corde ABEC et BECD, mais sans pouvoir décider simplement lequel des points communs B, C ou E il faut dédoubler.
Il faut étudier le graphe complémentaire, pour savoir dans chaque cas si c'est un graphe de comparabilité.

   Suppression du sommet B, le graphe complémentaire restant :

Ce n'est pas un graphe de comparabilité :
Au sens près, on peut imposer C > F
L'absence des arcs CD, CH et CE impose le sens des arcs D > F, H > F et E > F
L'absence d'arc GF impose E > G
L'absence d'arc AF impose H > A et E > A
L'absence d'arc GH impose E > H
L'absence d'arc DA impose E > D et H > D
l'absence des arcs GH et GF rend alors impossible le choix du sens de GD

   Suppression du sommet E, le graphe complémentaire restant :

Ce n'est pas non plus un graphe de comparabilité
Après les arcs forcés comme ci-dessus, il est impossible de définir l'orientation de CF

   Suppression du sommet C, le graphe complémentaire restant :

est bien un graphe de comparabilité
En partant d'une orientation arbitraire A > E, on impose de proche en proche toutes les orientations,
et la procédure aboutit cette fois.
On peut alors envisager la construction d'un planning en barres.
L'étude précédente des graphes complémentaires était juste pour éviter de chercher en vain.

Il est alors "facile" de réaliser un planning en barres avec tous sauf C
On ajoute alors autant de copies de C qu'il faut pour satisfaire l'énoncé, soit 3 copies.