Ce projet présente 3 cas solutionnés par la théorie des graphes. Le premier cas est directement issu d’une histoire vraie…
Durant un été des années 70, le duc de Densmore ainsi que son majordome sont retrouvés morts dans la propriété du duc sur l’île de Watt. Une charge explosive a été branchée sur l’un des disjoncteurs présent dans le labyrinthe. La conception d’une telle bombe demande de très nombreux préparatifs et le coupable a nécessairement dû passer du temps sur l’île caché dans les labyrinthes pour la mettre au point. En plus du duc et de son majordome, huit femmes sont venues passer du temps sur l’île. Les analyses laissent à penser que le coupable a agi seul. Les pêcheurs ont témoigné que chaque suspecte n’est venue qu’une seule fois et qu’aucune autre personne n’a été vue à l’embarquement. Mais qui a tué le duc de Densmore ? Les faits remontant à plus d’un an au moment de l’enquête, aucune d’entre elles ne se souvient exactement des dates de leur venue. Elles se rappellent cependant les personnes rencontrées sur place.
Miss Felcia Wynn, mannequin rencontrée par le duc au cours d’une croisière en Méditerranée, a rencontré : Ann Layburn, Emily Healey
Lady Cynthia Mansfield, joueuse professionnelle au Casino de Monte-Carlo, a rencontré : Ann Layburn, Betty Townsend, Diana Macleod, Emily Healey, Helen Grimshaw
Mrs Georgia Blake, théosophe végétarienne et spirite, a rencontré : Ann Layburn, Helen Grimshaw
Miss Diana Macleod, traductrice du livre de Georges Perec « Les choses », a rencontré : Cynthia Mansfield, Emily Healey
Miss Emily Healey, lépidoptérologiste rousse, a rencontré : Ann Layburn, Cynthia Mansfield, Diana Macleod, Felicia Wynn
Miss Ann Layburn, joueuse d’échecs avec un ELO à 2075, a rencontré : Betty Townsend, Cynthia Mansfield, Emily Healey, Felicia Wynn, Georgia Blake
Miss Betty Townsend, pianiste, a rencontré : Ann Layburn, Cynthia Mansfield, Helen Grimshaw
Miss Helen Grimshaw, jeune comédienne ayant joué à treize ans le rôle de Zazie à Nottingham, a rencontré : Betty Townsend, Cynthia Mansfiled, Georgia Blake
Et conclue alors à la culpabilité du majordome et classe l’affaire.
Quelques semaines plus tard, le détective Ratson rencontre son ami le professeur Torder Smith et ne tarde pas à lui détailler l’affaire. Très intéressé, Torder Smith sort un calepin et griffonne un graphe. Chaque sommet du graphe correspond à une des témoins (A pour Ann, B pour Betty, C pour Cynthia, …). Deux sommets sont reliés par des arêtes si les deux femmes se sont rencontrées sur l’île. Torder Smith scrute alors le graphe et annonce que le majordome est innocent, et qu’il connait l’identité de la coupable. Mais qui est-ce ?
Ce projet Java vise à résoudre de manière programmatique ce problème. L'algo se base sur la solution commentée dans cette vidéo.
Ce projet montre également comment utiliser les graphes pour déterminer l’organisation des tâches en gestion de projet (réseau PERT), ou encore comment déterminer le chemin le plus court entre deux points d’un graphe (comme le font les GPS de nos voitures) grâce à l’algorithme de Djikstra.