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 hipercubos , pero con un número de vértices de Fibonacci . Los cubos de Fibonacci se definieron 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 puede definirse en términos de códigos de Fibonacci y distancia de Hamming , conjuntos independientes de vértices en gráficos de trayectorias o mediante redes distributivas .
Al igual que el grafo del 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 sean adyacentes siempre que sus etiquetas difieran en un solo bit. Sin embargo, en un cubo de Fibonacci, las únicas etiquetas que se permiten 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 fibinarios . Hay F n + 2 etiquetas posibles, donde F n denota el n º 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 números enteros consecutivos de 0 a F n + 2 − 1; las cadenas de bits correspondientes a estos números se dan mediante sus representaciones Zeckendorf . [1]
El cubo de Fibonacci de orden n es el grafo símplex del grafo complementario 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 de complemento de camino, o equivalentemente un conjunto independiente en el camino mismo; dos vértices del cubo de Fibonacci son adyacentes si las camarillas o conjuntos independientes que representan difieren por la adición o eliminación de un solo elemento. Por lo tanto, al igual que otros grafos símplex, los cubos de Fibonacci son grafos medianos y, más generalmente, cubos parciales . [3] La mediana de tres vértices cualesquiera 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 gráfico de una red distributiva que puede obtenerse mediante el teorema de representación de Birkhoff a partir de un conjunto 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 de la misma red en teoría de grafos: 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 eliminando elementos de un lado de la bipartición y añadiendo elementos al otro lado de la bipartición; con este orden, los conjuntos independientes forman una red distributiva, [5] y la aplicación de esta construcción a un grafo de trayectoria da como resultado la red asociada con el cubo de Fibonacci.
El cubo de Fibonacci de orden n se puede dividir 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]
Todo cubo de Fibonacci tiene un camino hamiltoniano . Más específicamente, existe un camino que obedece a la partición descrita anteriormente: visita los nodos con primer bit 0 y los nodos con primer bit 1 en dos subsecuencias contiguas. Dentro de estas dos subsecuencias, el camino puede construirse recursivamente por la misma regla, uniendo las dos subsecuencias en los extremos de las subsecuencias en las que el segundo bit es 0. Así, por ejemplo, en el cubo de Fibonacci de orden 4, la sucesión 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 que es 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 (de nuevo, redondeado al entero más cercano). [9]
Taranenko y Vesel (2007) demostraron que es posible probar si un gráfico es un cubo de Fibonacci en el tiempo casi lineal en su tamaño.
Hsu (1993) y Hsu, Page y Liu (1993) sugirieron utilizar cubos de Fibonacci como una topología de red en computación paralela . Como red de comunicaciones, el cubo de Fibonacci tiene 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 cálculos distribuidos. [10]
Klavžar y Žigert (2005) aplican los cubos de Fibonacci en la teoría de grafos químicos como una descripción de 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 cuyos bordes 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 mosaico 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 borde con borde sin 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 gráficos bipartitos planares que tienen cubos de Fibonacci como sus gráficos de resonancia. [2]
Los cubos de Fibonacci generalizados fueron presentados por Hsu y Chung (1993) basándose en los números de Fibonacci de orden k, que luego fueron ampliados a una clase más grande de redes llamadas Redes Recursivas Lineales por Hsu, Chung y Das (1997) basadas 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 gráfico relacionado es el cubo de Lucas, un gráfico 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 tanto de los cubos de Fibonacci como de los cubos de Lucas.