Nicolaas de Bruijn, del “BEST theorem” al confirmador de teorías matemáticas

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:

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

6 Comentarios

  1. Perdona mi ignoracia, pero la sucesion 00010111 y 11101000 no serian una misma sucesion? no veo porque son sucesiones diferentes, en ese caso esta sucesion (10100011) no seria tambien una sucesion de bruijn ?

    Publica una respuesta
  2. Julián, no, no son la misma, pero la que tú propones sí es igual a una de ellas (a la segunda). Ten en cuenta que la sucesión de elementos es cíclica, por lo que cuando llegamos al último elemento tenemos que seguir por el principio. Lo mejor para verlo es escribir los números en círculo:

    Comenzando por el círculo rojo de arriba tenemos las siguientes ternas de números:

    000, 001, 010, 101, 011, 111, 110, 100

    Todas exactamente una vez.

    Si colocas las otras en círculo, puedes ver que la que tú propones y la segunda que yo escribí son exactamente la misma.

    Publica una respuesta
  3. DIAMOND

    Si nació en la Haya ¿era alemán u Holandés?

    Publica una respuesta
  4. Nicolaas de Bruijn, del “BEST theorem” al confirmador de teorías matemáticas – Gaussianos | Gaussianos, me ha parecido muy insteresante, me hubiera gustado que fuese más largo pero ya saeis si lo bueno es breve es dos veces bueno. Enhorabuena por vuestra web. Besotes.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Cuando uno se encuentra con un resultado matemático cuyo nombre es the BEST theorem…
  2. Gaussianos cumple 7 años de vida - Gaussianos | Gaussianos - [...] ya en julio hemos reflexionado sobre la trisección del ángulo, hemos presentado a Nicolaas de Bruijn y, entre otras…
  3. (Lo que yo considero) Lo mejor de 2013 en Gaussianos | Matemáticas Secundaria - […] ¿Cuál es la manera más efectiva de construir un triángulo equilátero en la práctica? Nicolaas de Bruijn, del “BEST…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *