cubo de Fibonacci

En el campo matemático de la teoría de grafos , los cubos de Fibonacci o redes de Fibonacci son una familia de grafos no dirigidos con ricas propiedades recursivas derivadas de su origen en la teoría de números . Matemáticamente, son similares a los grafos hipercubo , pero con un número de vértices de Fibonacci . Los cubos de Fibonacci fueron definidos explícitamente por primera vez en Hsu (1993) en el contexto de topologías de interconexión para conectar sistemas paralelos o distribuidos. También se han aplicado en la teoría de grafos químicos .

El cubo de Fibonacci se puede definir en términos de códigos de Fibonacci y distancia de Hamming , conjuntos independientes de vértices en grafos de caminos o mediante retículos distributivos .

Al igual que el grafo hipercubo, los vértices del cubo de Fibonacci de orden n pueden etiquetarse con cadenas de bits de longitud n , de tal manera que dos vértices son adyacentes siempre que sus etiquetas difieran en un solo bit. Sin embargo, en un cubo de Fibonacci, las únicas etiquetas permitidas son cadenas de bits sin dos bits 1 consecutivos. Si las etiquetas del hipercubo se interpretan como números binarios , las etiquetas en el cubo de Fibonacci son un subconjunto, los números fibinos . Hay F _{n  +  2} etiquetas posibles, donde F _n denota el n- ésimo número de Fibonacci, y por lo tanto hay F _{n  +  2} vértices en el cubo de Fibonacci de orden n .

A los nodos de dicha red se les pueden asignar enteros consecutivos de 0 a F _{n  +  2} − 1; las cadenas de bits correspondientes a estos números vienen dadas por sus representaciones de Zeckendorf . ^{[ 1 ]}  

El cubo de Fibonacci de orden n es el grafo simplex del grafo complemento de un grafo de camino de n vértices. ^{[ 2 ]} Es decir, cada vértice en el cubo de Fibonacci representa una camarilla en el grafo complemento del camino, o equivalentemente un conjunto independiente en el propio camino; dos vértices del cubo de Fibonacci son adyacentes si las camarillas o conjuntos independientes que representan difieren en la adición o eliminación de un solo elemento. Por lo tanto, como otros grafos simplex, los cubos de Fibonacci son grafos medianos y, más generalmente, cubos parciales . ^{[ 3 ]} La mediana de cualesquiera tres vértices en un cubo de Fibonacci se puede encontrar calculando la función de mayoría bit a bit de las tres etiquetas; si cada una de las tres etiquetas no tiene dos bits 1 consecutivos, lo mismo es cierto para su mayoría.

El cubo de Fibonacci es también el grafo de un retículo distributivo que se puede obtener mediante el teorema de representación de Birkhoff a partir de un poset en zigzag , un conjunto parcialmente ordenado definido por una secuencia alternada de relaciones de orden a < b > c < d > e < f > ... ^{[ 4 ]} También hay una descripción alternativa en teoría de grafos del mismo retículo: a los conjuntos independientes de cualquier grafo bipartito se les puede dar un orden parcial en el que un conjunto independiente es menor que otro si difieren quitando elementos de un lado de la bipartición y agregando elementos al otro lado de la bipartición; con este orden, los conjuntos independientes forman un retículo distributivo, ^{[ 5 ]} y aplicando esta construcción a un grafo de caminos se obtiene el retículo asociado con el cubo de Fibonacci.

El cubo de Fibonacci de orden n puede particionarse en un cubo de Fibonacci de orden n − 1 (los nodos con etiquetas que comienzan con un bit 0) y un cubo de Fibonacci de orden n − 2 (los nodos con etiquetas que comienzan con un bit 1). ^{[ 6 ]}    

Cada cubo de Fibonacci tiene un camino hamiltoniano . Más específicamente, existe un camino que obedece la partición descrita anteriormente: visita los nodos con el primer bit 0 y los nodos con el primer bit 1 en dos subsecuencias contiguas. Dentro de estas dos subsecuencias, el camino se puede construir recursivamente mediante la misma regla, uniendo las dos subsecuencias en los extremos de las subsecuencias donde el segundo bit es 0. Así, por ejemplo, en el cubo de Fibonacci de orden 4, la secuencia construida de esta manera es (0100-0101-0001-0000-0010)-(1010-1000-1001), donde los paréntesis delimitan las subsecuencias dentro de los dos subgrafos de la partición. Los cubos de Fibonacci con un número par de nodos mayor que dos tienen un ciclo hamiltoniano . ^{[ 7 ]}

Munarini y Salvi (2002) investigan el radio y el número de independencia de los cubos de Fibonacci. Debido a que estos grafos son bipartitos y tienen caminos hamiltonianos, sus conjuntos independientes máximos tienen un número de vértices igual a la mitad del número de vértices en todo el grafo, redondeado al entero más cercano. ^{[ 8 ]} El diámetro de un cubo de Fibonacci de orden n es n , y su radio es n /2 (nuevamente, redondeado al entero más cercano). ^{[ 9 ]}

Taranenko y Vesel (2007) demostraron que es posible comprobar si un gráfico es un cubo de Fibonacci en un tiempo casi lineal en su tamaño.

Hsu (1993) y Hsu, Page y Liu (1993) sugirieron el uso de cubos de Fibonacci como topología de red en computación paralela . Como red de comunicaciones, el cubo de Fibonacci posee propiedades beneficiosas similares a las del hipercubo: el número de aristas incidentes por vértice es como máximo n /2 y el diámetro de la red es como máximo n , ambos proporcionales al logaritmo del número de vértices, y la capacidad de la red para ser particionada en redes más pequeñas del mismo tipo permite dividirla entre múltiples tareas de computación paralela. ^{[ 7 ]} Los cubos de Fibonacci también admiten protocolos eficientes para enrutamiento y difusión en computaciones distribuidas. ^{[ 10 ]}

Klavžar y Žigert (2005) aplican los cubos de Fibonacci en la teoría de grafos químicos para describir la familia de emparejamientos perfectos de ciertos grafos moleculares. Para una estructura molecular descrita por un grafo planar G , el grafo de resonancia (o grafo de transformación Z ) de G es un grafo cuyos vértices describen emparejamientos perfectos de G y cuyas aristas conectan pares de emparejamientos perfectos cuya diferencia simétrica es una cara interior de G. Los hidrocarburos aromáticos policíclicos pueden describirse como subgrafos de un teselado hexagonal del plano, y el grafo de resonancia describe posibles estructuras de doble enlace de estas moléculas. Como muestran Klavžar y Žigert (2005) , los hidrocarburos formados por cadenas de hexágonos, unidos arista con arista sin que haya tres hexágonos adyacentes en una línea, tienen grafos de resonancia que son exactamente los grafos de Fibonacci. De manera más general, Zhang, Ou y Yao (2009) describieron la clase de grafos bipartitos planares que tienen cubos de Fibonacci como sus grafos de resonancia. ^{[ 2 ]}

Hsu y Chung (1993) presentaron cubos de Fibonacci generalizados basados ​​en los números de Fibonacci de orden k, que posteriormente fueron extendidos a una clase mayor de redes denominada Redes Recursivas Lineales por Hsu, Chung y Das (1997) basándose en formas más generales de recursiones lineales. Wu (1997) modificó los cubos de Fibonacci de segundo orden basándose en diferentes condiciones iniciales. Otro grafo relacionado es el cubo de Lucas , un grafo con un número de vértices de Lucas definido a partir del cubo de Fibonacci al prohibir un bit 1 tanto en la primera como en la última posición de cada cadena de bits; Dedó, Torri y Salvi (2002) investigaron las propiedades de coloración de los cubos de Fibonacci y los cubos de Lucas.