Cuando uno se encuentra con un resultado matemático cuyo nombre es the BEST theorem (es decir, el mejor teorema, y encima en mayúsculas) se ilusiona, espera un resultado magnífico, maravilloso, útil ingenioso, en definitiva precisamente lo que su propio nombre indica, el mejor teorema. Cuando uno se entera de que BEST son las iniciales de las personas a las que debemos dicho resultado la ilusión baja, no nos engañemos. Pero la curiosidad por saber de qué trata dicho resultado puede más que esta bajada, ¿verdad?

Nicolaas de BruijnNicolaas de Bruijn (que, hablando de todo un poco, no sé si será familia de la excelente nadadora Inge de Bruijn) es quien aporta la B a este BEST theorem (los demás son Tatyana Pavlovna Ehrenfest, Cedric Smith y William Tutte). El protagonista de este post, matemático alemán holandés fallecido el pasado año 2012, nació tal día como hoy, 9 de julio, en 1918 en La Haya.

Antes de comentar otros avances realizados por de Bruijn, veamos de qué trata el BEST theorem. ¿Os acordáis del problema de los puentes de Königsberg? En él la cuestión era determinar si se podía encontrar un camino que pasara por los 7 puentes que había en la ciudad de Königsberg exactamente una vez y regresar al punto de partida. Es decir, lo que en teoría de grafos sería encontrar un circuito (o ciclo) euleriano. En este post dimos una caracterización de cuándo existe un circuito euleriano en un grafo no dirigido y también un algoritmo para encontrarlo.

El BEST theorem trata sobre esto, pero en grafos dirigido (es decir, en grafos cuyas aristas son flechas que indican el único sentido en el que puede ser recorridas). En 1736, Euler mostró que un grafo dirigido contiene un circuito euleriano si y sólo si es conexo y el grado de entrada de cada vértice (número de aristas que llegan al vértice) es igual a su grado de salida (número de aristas que salen de él), y por eso estos grafos se denominan grafos eulerianos. La cuestión que responde el BEST theorem es la siguiente: ¿cuántos circuitos eulerianos tiene un grafo euleriano dirigido G? La respuesta, ce(G), es:

ce(G)=t_w(G) \; \displaystyle{\prod_{v \in V} (deg(v)-1)!}

siendo deg(v) el grado de entrada (o de salida, al ser euleriano son iguales) del vértice v y t_w(G) el número de árboles (grafos sin ciclos) generadores (conteniendo todos los vértices) dirigidos cuya raíz (vértice desde el cual fluyen las aristas) es un vértice cualquiera del grafo. Quizás no es tan BEST como uno podría haber esperado en un principio, pero no se puede negar que es un gran teorema.

Las aportaciones matemáticas de Nicolaas de Bruijn no se quedan ahí, ni mucho menos. Comentaremos a partir de ahora algunas de ellas.

Fue el descubridor de lo que en la actualidad se conoce como sucesión de de Bruijn, que Pedro Alegría nos define muy claramente en ese artículo de DivulgaMAT:

Dado un alfabeto (o conjunto ordenado) A de tamaño k, una sucesión cíclica B(k,n) de elementos de A se llama sucesión de de Bruijn cuando toda subsucesión de n elementos de A aparece como máximo una vez en B(k,n) de forma consecutiva. La sucesión será maximal cuando todas las subsucesiones de longitud n aparezcan exactamente una vez en B(k,n).

Por ejemplo, dado el conjunto ordenado A=\{ 0,1 \}, hay dos sucesiones de de Bruijn de tamaño 3: 00010111 y 11101000. Recomiendo leer el artículo completo de Pedro Alegría para ver aplicaciones de este tipo de sucesiones.

También diseño Automath, un lenguaje formal mediante el cual se podían expresar teorías matemáticas completas de manera que un ordenador pudiera verificar su corrección. Algo así como un confirmador (o verificador) de teorías y demostraciones matemáticas. Automath fue el precursor de algunos otros sistemas de este tipo. Como curiosidad, L.S. Jutting, como parte de su tesis en 1976, tradujo el trabajo «Fundamentos de Análisis» de Edmund Landau a Automath y comprobó su corrección con él.

Otras aportaciones matemáticas de Nicolaas de Bruijn son la constante de de Bruijn-Newman, \Lambda, relacionada con la hipótesis de Riemann, los teoremas de de Bruijn-Erdös (uno de teoría de grafos y otro sobre líneas determinadas por puntos en un plano proyectivo) o su trabajo sobre teselaciones de Penrose. Aquí podéis ver algunas más.

Muy interesantes las aportaciones de Nicolaas de Bruijn a las matemáticas. Seguro que algunas de ellas seguirán dando pie a artículos en este blog. Y seguro que vosotros estaréis ahí para disfrutar de ellos y para comentarnos vuestra opinión y vuestras ideas.

Más información en:

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉