De Bruijn toro
En matemática combinatoria , un toro De Bruijn , llamado así por Nicolaas Govert de Bruijn , es una matriz de símbolos de un alfabeto (a menudo solo 0 y 1) que contiene cada matriz m -por- n exactamente una vez. Es un toro porque los bordes se consideran envolventes con el propósito de encontrar matrices. Su nombre proviene de la secuencia de De Bruijn , que puede considerarse un caso especial donde n es 1 (una dimensión).
Una de las principales preguntas abiertas con respecto a De Bruijn tori es si se puede construir un toro de De Bruijn para un tamaño de alfabeto particular para una m y una n dadas . Se sabe que estos siempre existen cuando n = 1 , ya que entonces simplemente obtenemos las secuencias de De Bruijn, que siempre existen. También se sabe que existen toros "cuadrados" siempre que m = n e incluso (para el caso impar, los toros resultantes no pueden ser cuadrados). [1] [2] [3]
El "cuadrado" binario más pequeño posible de toro de Bruijn, representado arriba a la derecha, denotado como (4,4; 2,2) 2 toro de Bruijn (o simplemente como B 2 ), contiene todas las matrices binarias de 2 × 2 .
Aparte de la "traslación", la "inversión" (intercambiando ceros y unos) y la "rotación" (en 90 grados), no es posible ningún otro (4,4; 2,2) 2 de Bruijn tori; esto se puede demostrar mediante una inspección completa de las 2 16 matrices binarias (o subconjunto que cumplen restricciones como números iguales de 0 y 1). [4]
El toro puede desenrollarse repitiendo n -1 filas y columnas. Todas las submatrices n × n sin envolvente, como la que está sombreada en amarillo, forman el conjunto completo:
Se ha construido explícitamente un ejemplo del próximo "cuadrado" binario posible de toro de Bruijn, (256,256; 4,4) 2 (abreviado como B 4 ). [5]
_2_de_Bruijn_torus.svg)