Una bonita relación entre grafos y números binarios | Ciclos de De Bruijn

Hace mil años, los músicos indios idearon un método para memorizar patrones rítmicos. Hoy sabemos que el mismo principio sirve para decodificar mensajes en binario y recomponer textos electrónicos. ¡Un viaje que nadie esperaba!

INFORMACIÓN ADICIONAL
https://lemnismath.org/2023/06/secuen...

REDES SOCIALES
  / telecorenta  
  / telecorenta  
   / @telecorenta  
  / lemnismath  
  / lemnismath  

Pequeño índice:
00:00 - Introducción
01:45 - El teorema de Euler
04:22 - La ciudad imaginaria
9:29 - El telégrafo de Baudot

Una ciudad siempre tiene un número par de «zonas con puentes impares». O sea: o no tiene zonas impares, o tiene dos, o tiene cuatro, o tiene un número par. Es fácil demostrar por qué, pero eso te lo dejo como reto. En consecuencia, las ciudades formadas por dos o tres zonas siempre tienen una ruta que cruza todos los puentes sin repeticiones, porque estas ciudades siempre admiten una ruta abierta o cerrada (como mucho tienen dos zonas impares). Lo digo porque lo normal es que las ciudades con río solo tengan dos zonas (como Londres) o tres (como Roma), y es razonable que los vecinos no se hagan preguntas sobre los puentes. Hacía falta una ciudad con al menos cuatro zonas para que alguien se planteara el problema que dio inicio a la teoría de grafos.

------------- Bibliografía y referencias ---------------

[1] Basado en S. K. Stein: Mathematics, the Man-Made Universe (1963). El capítulo 10 lo dedica a las «Memory wheels», los ciclos de De Bruijn.

[2] A. H. Fox Strangways, «The Music of Hindostan». Oxford at the Clarendon Press, 1914.

[3] Telégrafo de Baudot.
https://museotelecomvlc.webs.upv.es/t...

[4] T. E. Stern y B. Friedland, «Application of Modular Sequential Circuits to Single
Error-Correcting P-Nary Codes», 1959.

[5] L. Euler, «Solutio problematis ad geometriam situs pertinentis» (1741). Versión traducida en «Graph Theory: 1736-1936».

[6] Sobre la pronunciación de Euler: Mucha gente lo pronuncia como se escribe en español, /euler/. La pronunciación alemana es parecida a /oilah/, pero el acento Suizo la aproxima más a /oiler/. También está la versión latinizada del nombre: Eulero.

[7] Cartas que muestran las impresiones de Euler:
H. Sachs, M. Stiebitz y R. J. Wilson, «An Historical Note: Euler‘s Konigsberg Letters», 1988.

[8] En el vídeo solo consideramos grafos conexos: aquellos en que puedes ir a cualquier zona de la ciudad cruzando puentes. No hay zonas aisladas.

[9] «Graphs and Digraphs», de G. Chartrand y L. Lesniak (1986). En él, también consideran la versión del teorema con grafos dirigidos.

[10] SOLO PARA GRAFOS CONEXOS, COMPADRE.

[11] La mesa está expuesta en el Museo de las Matemáticas de Huesca.
https://planetariodearagon.com/museo-...

[12] I. J. Good, «Normal Recurring Decimals». 1946.

[13] Considero que este es el mismo teorema de Euler, como comento en [9]. La demostración es análoga en el caso de grafos y digrafos.

[14] El artículo explica el método para secuencias de cualquier longitud, y solo da el caso de los tríos como un ejemplo.

[15] Varias cosas sobre N. G. de Bruijn.
- Secuencias de De Bruijn: https://mathworld.wolfram.com/deBruij...
- En «A combinatorial problem» (1946) calcula cuántas soluciones distintas tiene el problema. https://dwc.knaw.nl/DL/publications/P...
- En «Acknowledgement of priority to C. Flye Sainte-Marie...» (1975) explica que ya habían calculado lo mismo en 1894 (ay, ¡qué faena!).
http://alexandria.tue.nl/repository/b...
- El nombre, hasta donde he podido averiguar viendo la televisión holandesa por Internet, se pronuncia de forma similar a como lo digo.

[16] La patente americana es de 1888.
https://patents.google.com/patent/US3...
La directora del museo de las telecomunicaciones me pasó un «Tratado de telegrafía eléctrica», de H. Thomas, 1903, que es una delicia.

[17] Todo lenguaje necesita un código.

[18] Le he quitado algunos dientes que servían para tareas de control.

[19] «The Evolution of Character Codes, 1874-1968» de Eric Fischer https://ia800606.us.archive.org/17/it...

[20] ¿Usamos secuencias de De Bruijn para la corrección de errores en 2023? Es difícil contestar, porque nunca se han usado directamente. Lo que usamos son propiedades de grupos finitos para codificar y decodificar mensajes de forma eficiente. Muchas de estas propiedades son equivalentes, después de varios pasos lógicos, a los ciclos de De Bruijn. La tecnología avanza y la corrección de errores es cada vez más elaborada; en consecuencia, más alejada de algo que se pueda reconocer como secuencias de De Bruijn.