Entender una expresión relacionada con los árboles binarios completos

Question

Soy bastante nuevo en las matemáticas discretas. Estaba revisando el gráfico y encontré esta expresión que era para el árbol binario completo, donde $B_h$ representa el gráfico, es decir, el árbol binario completo de longitud/altura h $B_h := ([2]^{h}, \{\{u,ux\} \ such\ that\ u\epsilon [2]^{<h}, x\epsilon [2]\})$

Me he confundido aquí. ¿Qué es lo que $[2]^{h}$ y $[2]^{<h}$ significa aquí, estoy bastante seguro de que [2] significa {1,2}. Pero ese exponente en el conjunto no me queda muy claro. ¿significa producto cartesiano? Agradecería cualquier tipo de ayuda. ¡gracias!

Answer 1

Si me permite, me siento más cómodo pensando en $[2]$ como $\{0,1\}$ .

$[2]^h$ es el producto cartesiano de $[2]$ con ella misma $[h]$ tiempos: $$ [2]^h=[2]\times[2]\times\dots\times[2]\cong\{(b_1,b_2,\dots,b_h)\mid b_i\in [2]\text{ for }1\le i\le h\} $$

En otras palabras, $[2]^h$ consiste en secuencias binarias de longitud $h$ . Entonces, $$ [2]^{\le h}=[2]^0\cup [2]^1\cup \dots\cup [2]^h $$ es el conjunto de secuencias binarias de longitud máxima $h$ . Es decir, $2^{\le [h]}$ no es un producto cartesiano, sino una unión de productos cartesianos. Seguramente ya se puede imaginar lo que $[2]^{<h}$ es; consiste en secuencias binarias cuyas longitudes son estrictamente menores que $h$ .

El conjunto de aristas es de la forma $\{u,ux\}$ , donde $u$ es una secuencia binaria de longitud inferior a $h$ y $x\in \{0,1\}$ . La multiplicación aquí es la concatenación. Por ejemplo, dejando que $u=(0,1,0)$ y $x=0$ hay una arista entre $(0,1,0)$ y $(0,1,0,0)$ ; añadimos un $0$ hasta el final de $u$ para conseguir a su vecino.