Chi ha ucciso il Duca di Densmore?
Sherlock Holmes e la teoria dei grafi
Un grafo G è una struttura matematica costituita da un insieme di elementi detti vertici o nodi collegati fra loro da archi o spigoli. I vertici sono in genere trattati come oggetti senza caratteristiche e indivisibili.
Un arco che ha due estremi coincidenti si dice cappio, mentre più archi che connettono gli stessi due estremi costituiscono un multiarco. Un grafo sprovvisto di cappi e di multiarchi si dice grafo semplice. In caso contrario si parla di multigrafo.
Un arco orientato è un arco caratterizzato da una direzione, indicata da una freccia che esce da un vertice e entra in un altro. A seconda della presenza o meno di archi orientati, si distinguono i grafi orientati (o digrafi, grafi diretti) e i grafi non orientati. Un grafo semplice non contiene archi orientati.
Un percorso di lunghezza n in G è dato da una sequenza di vertici v0, v1,…, vn (non necessariamente tutti distinti) e da una sequenza di archi che li collegano. I vertici v0 e vn si dicono estremi del percorso. Un percorso con gli spigoli a due a due distinti tra loro prende il nome di cammino. Un cammino chiuso (v0 = vn) si chiama circuito o ciclo. Un cammino in un grafo (orientato o non orientato) è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una sola volta. Un cammino viene invece detto euleriano quando tocca tutti gli archi del multigrafo una e una volta sola.
Un sottografo G’ è un grafo composto da un sottoinsieme dei nodi e degli archi di un grafo G più grande (ad esempio qui sopra ABC è un sottografo di ABCDE).
Esistono grafi nei quali sono presenti coppie di archi che si intersecano. Essi non possono essere disegnati nel piano senza evitare incroci tra gli archi. Questi grafi sono detti non planari, come ad esempio il grafo completo con 5 nodi, k5 e il grafo bipartito completo con 3 + 3 nodi, k3,3. Si tratta dei due grafi che il matematico polacco Kazimierz Kuratowski dimostrò nel 1929 essere i più semplici grafi non planari: un grafo è planare se, e solo se, non contiene alcun sottografo che sia omeomorfo a questi due. Il secondo grafo è abbastanza noto, perché rappresenta il gioco in cui viene chiesto di collegare le tre case (i vertici in alto) con ciascuno dei tre pozzi (i vertici in basso) con sentieri che si scopre non è possibile disegnare senza intersezioni.
I grafi oggi sono tra i modelli più diffusi per rappresentare strutture sia naturali sia umane. Essi possono essere usati per costruire modelli di molti tipi di dinamiche delle relazioni e dei processi nei sistemi fisici, biologici e sociali. Molti problemi di interesse pratico possono essere affrontati mediante i grafi.
Nell'informatica e nelle telecomunicazioni, i grafi sono usati per rappresentare e ottimizzare reti di comunicazione, l'organizzazione di dati, sistemi e algoritmi di calcolo, la struttura dei siti web, i motori di ricerca, ecc. La teoria dei grafi costituisce un’importante parte della combinatoria e trova largo utilizzo in topologia, nella teoria degli automi, nella geometria dei poliedri, ecc. Essa è alla base di modelli di sistemi e processi studiati nell’ingegneria, nella fisica della materia condensata, nella chimica, nella biologia molecolare, nell’organizzazione aziendale, nella sociologia, nell’urbanistica, nello studio delle reti di traffico, nella linguistica strutturale, nella storia e nella filologia.
Nelle scuole e università francofone circola da tempo un problema, ispirato dal racconto poliziesco Qui a tué le Duc de Densmore? (1994) del matematico Claude Berge (foto sotto), membro fondatore dell’OuLiPo, uno dei membri più autorevoli del gruppo francese e teorico della teoria dei grafi. Nell’opera originale, il detective Ralston di Scotland Yard indaga sulla morte, scoperta con un anno di ritardo, del duca di Densmore e del suo maggiordomo, avvenuta sull’isola di Wight a causa di un’esplosione. Raccolte le testimonianze delle otto persone che per ultime hanno visto in vita il duca, Ralston risolve il caso grazie all’aiuto di un suo vecchio amico, Cedric Turner-Smith, professore di Matematica al Merton College di Oxford.
Il caso viene risolto grazie alla conoscenza degli studi effettuati dal matematico ungherese György Hajòs (1912–1972) nel campo della teoria dei grafi.
In questo adattamento, del tutto privo di valore letterario, il protagonista è Sherlock Holmes e, per individuare il colpevole, è necessario l’utilizzo di un grafo degli intervalli.
Nella teoria dei grafi, un grafo degli intervalli è un grafo non orientato che rappresenta le intersezioni di un insieme di intervalli sulla retta dei numeri reali (più o meno come quando si rappresenta la soluzione di un sistema di disequazioni o si costruisce un diagramma di Gannt). Esso possiede un vertice per ogni intervallo dell’insieme e un arco tra ogni coppia di vertici che corrispondono a intervalli che si intersecano. Ad esempio, all’insieme di intervalli [1 ; 4], [3 ; 7], [3 ; 5], [6 ; 9] si può associare il grafo più sotto:
Dove i vertici A e D (e C e D) non sono collegati perché gli intervalli corrispondenti non si intersecano. È evidente che tale grafo esiste se, e solo se, esiste almeno un’intersezione.
Una proprietà di questi grafi degli intervalli è che è impossibile un grafo che presenti un ciclo senza diagonale come quello qui rappresentato:
Dove A non può essere collegato a D senza esserlo a C (chi non ci crede provi a disegnare gli intervalli corrispondenti, con estremi a piacere). Esiste infatti un teorema (di Gilmore e Hoffman) che afferma che un grafo è un grafo degli intervalli se, e solo se, è “triangolato”, vale a dire che ogni ciclo di lunghezza maggiore di 3 deve possedere una diagonale.
________________________________________
Un giorno, Sherlock Holmes ricevette la visita dell’amico Watson, che era stato incaricato di condurre un’indagine su un misterioso assassinio avvenuto tre anni prima, quando il vecchio Duca di Densmore era morto a causa dell’esplosione di una bomba che aveva completamente distrutto il castello in cui si era ritirato.
I giornali del tempo avevano riferito che il testamento, distrutto anch’esso nell’esplosione, aveva tutti gli elementi per dispiacere a una delle sue sette ex-mogli. Ora, prima di morire, il Duca le aveva invitate tutte a trascorrere qualche giorno nella sua tenuta scozzese.
Holmes: Mi ricordo di questa vicenda. Ciò che mi sembra strano è che la bomba era stata costruita appositamente per essere nascosta nella struttura della camera da letto, il che implica che l’assassino ha necessariamente effettuato diverse visite al castello!
Watson: Di sicuro, e per questo motivo ho interrogato ciascuna delle donne: Ann, Betty, Charlotte, Edith, Felicia, Georgia e Helen. Tutte hanno giurato di essere state una sola volta nella loro vita al castello di Densmore.
Holmes: Uhm… Avete chiesto loro in quale periodo vi hanno soggiornato?
Watson: Ahimè! Nessuna ricordava la data esatta, dopo più di tre anni! Tuttavia ho chiesto loro chi avessero incontrato. Ecco, ho fatto questo elenco:
Ann ha incontrato Betty, Charlotte, Felicia e Georgia.
Betty ha incontrato Ann, Charlotte, Edith, Felicia e Helen.
Charlotte ha incontrato Ann, Betty e Edith.
Edith ha incontrato Betty, Charlotte e Felicia.
Felicia ha incontrato Ann, Betty, Edith e Helen.
Georgia ha incontrato Ann e Helen.
Helen ha incontrato Betty, Felicia e Georgia.
Come vedete, caro Holmes, le risposte sono concordanti!
Holmes, senza dir parola, prese una matita e tracciò uno strano schema, con dei punti indicati con A, B, C, E, F, G, H e delle linee che univano alcuni di questi punti. Lo guardò attentamente per un paio di minuti, poi disse:
Holmes: Bene, bene. Ciò che mi avete appena detto individua la colpevole in modo univoco!
Chi è l’assassina?
________________________________________
Come Holmes, disegniamo un grafo degli intervalli con i vertici. A, B, C, E, F, G e H. In questo caso gli intervalli considerati sono intervalli di tempo. Nel grafo colleghiamo i vertici corrispondenti all’iniziale del nome se le sospettate si sono incontrate al castello per un certo intervallo di tempo.
Per scoprire quale delle sette donne è stata più di una volta al castello, bisogna cercare nel grafo dei cammini chiusi che collegano quattro vertici, senza diagonale. Ora, A è vertice di tre cicli senza diagonale (AFHG, ABHG e ACEF). Non ci sono l’arco AH e l’FG per il ciclo AFHG, così come. non ci sono AH e BG in ABHG e non ci sono AE e FC in ACEF. Il grafo degli intervalli è perciò difettoso.
Il problema dice che c’è solo un’assassina. Cerchiamo allora di scartare solo un vertice, in modo che il grafo restante diventi triangolato. Tale vertice è all’intersezione di tutti i cicli con lunghezza maggiore di 3 senza corda, AFHG, ABHG e ACEF, cioè A, mentre quando vengono cancellati gli altri tre vertici di ogni ciclo, il grafico rimane difettoso. Così facendo, il subgrafo rimanente è infatti un grafo degli intervalli “triangolato”, cioè regolare.
Si dovrebbero aggiungere almeno tre copie di A per eliminare i tre cicli di lunghezza 4 e ottenere un grafo degli intervalli corretto. Ciò significa che Ann è stata al castello almeno tre volte!
Per essere sicuri, costruiamo lo schema degli intervalli temporali, che corrisponde alle dichiarazioni delle donne. L’unica maniera che rispetti le intersezioni tra gli intervalli è illustrata qui sotto:
Dunque si può concludere che è Ann l’assassina.
Tutti i grafi sono stati disegnati con Graph Creator.
