Metagramas y teoría de grafos

Ilustración de Gregory Nemec
http://www.gregorynemec.com/

Lewis Carroll es el creador del juego de palabras denominado dobletes o metagrama, que consiste en unir dos vocablos, mediante una cadena de palabras, cambiando en cada paso una única letra -y preservando el orden original-, como en este ejemplo en inglés:

APE / APT / OPT / OAT / MAT / MAN

Carroll introdujo este juego en su libro Doublets, a word-puzzle, en 1879. En él proporciona listados de palabras válidas en inglés para realizar las transiciones entre vocablos.

El objetivo del juego consiste encontrar cadenas lo más cortas posibles uniendo dos palabras dadas: éstas se llaman escalas.

El experto en ciencias de la computación Donald Knuth -el inventor del sistema de tipografía TeX– se interesó por este juego para palabras inglesas de cinco letras. Construyó un grafo en el que cada una de las 5.757 palabras de cinco letras estaba representada por un vértice: dos de ellos estaban unidos por una arista si diferían en una letra según las reglas establecidas por Carroll. Este grafo estaba formado por 14.135 aristas. Después escribió un programa que permitía encontrar escalas entre dos palabras dadas a priori.

Didier Müller -responsable de Le blog-notes mathématique du coyote– repite este ejercicio en su artículo Une application des graphes : les échelles de mots, con palabras en francés de cuatro letras. Y muestra además un programa para poder jugar con palabras de seis letras.

Nicolas Graner tiene un programa en línea -para palabras en francés- en el que se pueden encontrar las escalas entre palabras dadas.

Un juego que puede ‘ganarse’ -con el programa adecuado mucho más deprisa- usando la teoría matemática de grafos…

Visto en Le blog-notes mathématique du coyote

PD: Esta entrada participa en la edición 3.14159265 del Carnaval de Matemáticas cuyo blog anfitrión es pimedios-la aventura de las matemáticas