Los cubos de Fibonacci o redes de Fibonacci son una familia de gráficos no dirigidos con ricas propiedades recursivas derivadas de su origen en la teoría de números . Matemáticamente son similares a los gráficos de hipercubo , 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 se puede definir en términos de códigos de Fibonacci y distancia de Hamming , conjuntos independientes de vértices en gráficos de trayectoria o mediante retículas distributivas .
Definición
Al igual que el gráfico de 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 1 bits consecutivos. Hay posibles etiquetas F n + 2 , 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 números 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]
Estructura algebraica
El cubo de Fibonacci de orden n es el gráfico simplex del gráfico de complemento de un gráfico de trayectoria de n -vértices. [2] Es decir, cada vértice en el cubo de Fibonacci representa una camarilla en el gráfico de complemento de camino, o equivalentemente un conjunto independiente en el camino mismo; dos vértices de 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 gráficos simplex, los cubos de Fibonacci son gráficos medianos y, en general, cubos parciales . [3] La mediana de cualesquiera tres vértices en un cubo de Fibonacci se puede encontrar calculando la función mayoritaria bit a bit de las tres etiquetas; si cada una de las tres etiquetas no tiene dos bits 1 consecutivos, lo mismo ocurre con 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 poset en zigzag , un conjunto parcialmente ordenado definido por una secuencia alterna de relaciones de orden a < b > c < d > e < f > .. . [4] También hay una descripción teórica de grafos alternativa de la misma celosía: 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 al eliminar elementos de un lado de la bipartición y la adición de elementos al otro lado de la bipartición; con este orden, los conjuntos independientes forman un retículo distributivo, [5] y la aplicación de esta construcción a un gráfico de trayectoria da como resultado el retículo asociado con el cubo de Fibonacci.
Propiedades y algoritmos
El cubo de Fibonacci de orden n puede dividirse 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 una ruta que obedece a 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, la ruta se puede construir de forma recursiva por la misma regla, uniendo las dos subsecuencias al final de las subsecuencias en las que el segundo bit es 0. Por lo tanto, por ejemplo, en el cubo de Fibonacci de orden 4, la secuencia construida en de esta manera es (0100-0101-0001-0000-0010) - (1010-1000-1001), donde los paréntesis marcan 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 gráficos 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 el gráfico completo, redondeado al número 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 número entero más cercano). [9]
Taranenko y Vesel (2007) demostraron que es posible probar si una gráfica es un cubo de Fibonacci en el tiempo casi lineal en su tamaño.
Aplicaciones
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 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 dividirse en redes más pequeñas del mismo tipo permite dividirla entre múltiples tareas de cálculo en paralelo. [7] Los cubos de Fibonacci también admiten protocolos eficientes para enrutamiento y transmisió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 gráficos moleculares. Para una estructura molecular descrita por un gráfico plano G , el gráfico de resonancia o ( gráfico de transformación Z ) de G es un gráfico 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 subgrafías de un mosaico hexagonal del plano, y el gráfico 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, enlazados de borde a borde sin tres hexágonos adyacentes en una línea, tienen gráficos de resonancia que son exactamente los gráficos de Fibonacci. De manera más general , Zhang, Ou y Yao (2009) describieron la clase de gráficos bipartitos planos que tienen cubos de Fibonacci como gráficos de resonancia. [2]
Gráficos relacionados
Los cubos de Fibonacci generalizados fueron presentados por Hsu y Chung (1993) basados en los números de Fibonacci de orden k-ésimo, que luego fueron extendidos a una clase más grande de redes llamadas Redes recursivas lineales por Hsu, Chung y Das (1997) basado en más formas 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 1 bit tanto en la primera como en la última posición de cada cadena de bits; Dedó, Torri y Salvi (2002) investigaron las propiedades colorantes tanto de los cubos de Fibonacci como de los cubos de Lucas.
Notas
- ^ Klavžar (2011) , págs. 3-4.
- ↑ a b Klavžar (2011) , p.3.
- ^ Klavžar (2005) ; Klavžar (2011) , Teorema 5.1, p.10.
- ↑ Gansner (1982) llama al hecho de que esta celosía tiene un número de elementos de Fibonacci un "hecho bien conocido", mientras que Stanley (1986) pide una descripción de la misma en un ejercicio. Véase también Höft y Höft (1985) , Beck (1990) y Salvi y Salvi (2008) .
- ^ Propp (1997) .
- ^ Klavžar (2011) , págs. 4-5.
- ↑ a b Cong, Zheng y Sharma (1993) .
- ↑ Klavžar (2011) , p.6.
- ↑ Klavžar (2011) , p. 9.
- ^ Hsu (1993) ; Stojmenovic 1998 .
Referencias
- Beck, István (1990), "Órdenes parciales y los números de Fibonacci", Fibonacci Quarterly , 28 (2): 172-174, MR 1051291.
- Cong, B .; Zheng, SQ; Sharma, S. (1993), "Sobre simulaciones de matrices lineales, anillos y mallas 2D en redes de cubos de Fibonacci", Proc. 7º Int. Simposio de procesamiento paralelo , págs. 748–751, doi : 10.1109 / IPPS.1993.262788.
- Dedó, Ernesto; Torri, Damiano; Salvi, Norma Zagaglia (2002), "La observabilidad de los cubos de Fibonacci y Lucas", Matemáticas discretas , 255 (1-3): 55-63, doi : 10.1016 / S0012-365X (01) 00387-9.
- Gansner, Emden R. (1982), "Sobre el entramado de los ideales de orden de un poset de arriba hacia abajo", Discrete Mathematics , 39 (2): 113-122, doi : 10.1016 / 0012-365X (82) 90134-0 , Señor 0675856.
- Höft, Hartmut; Höft, Margret (1985), "Una secuencia de Fibonacci de celosías distributivas", Fibonacci Quarterly , 23 (3): 232-237, MR 0806293.
- Hsu, W.-J. (1993), "Cubos de Fibonacci: una nueva topología de interconexión", IEEE Transactions on Parallel and Distributed Systems , 4 (1): 3-12, doi : 10.1109 / 71.205649.
- Hsu, W.-J .; Chung, MJ (1993), "Cubos de Fibonacci generalizados", Conferencia internacional de 1993 sobre procesamiento paralelo - ICPP'93 , 1 , págs. 299-302, doi : 10.1109 / ICPP.1993.95.
- Hsu, W.-J .; Página, CV; Liu, J.-S. (1993), "Cubos de Fibonacci: una clase de gráficos auto-similares", Fibonacci Quarterly , 31 (1): 65-72.
- Hsu, W.-J .; Chung, MJ; Das, A. (1997), "Redes recursivas lineales y sus aplicaciones en sistemas distribuidos", IEEE Transactions on Parallel and Distributed Systems , 8 (7): 673–680, doi : 10.1109 / 71.598343.
- Klavžar, Sandi (2005), "Sobre la naturaleza mediana y las propiedades enumerativas de los cubos similares a Fibonacci", Matemáticas discretas , 299 (1-3): 145-153, doi : 10.1016 / j.disc.2004.02.023.
- Klavžar, Sandi (2011), "Estructura de los cubos de Fibonacci: una encuesta" (PDF) , Serie IMFM Preprint , Ljubljana, Eslovenia: Instituto de Matemáticas, Física y Mecánica, 49 (1150).
- Klavžar, Sandi; Žigert, Petra (2005), "Los cubos de Fibonacci son los gráficos de resonancia de los Fibonaccenes" , Fibonacci Quarterly , 43 (3): 269–276, archivado desde el original el 2007-02-08.
- Munarini, Emanuele; Salvi, Norma Zagaglia (2002), "Propiedades estructurales y enumerativas de los cubos de Fibonacci", Matemáticas discretas , 255 (1-3): 317-324, doi : 10.1016 / S0012-365X (01) 00407-1.
- Propp, James (1997), "Generación de elementos aleatorios de celosías distributivas finitas", Electronic Journal of Combinatorics , 4 (2): R15, arXiv : math.CO/9801066.
- Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), "Secuencias unimodales alternas de números de Whitney", Ars Combinatoria , 87 : 105-117, MR 2414008.
- Stanley, Richard P. (1986), Combinatoria enumerativa , Wadsworth, Inc. Ejercicio 3.23a, página 157.
- Stojmenovic, Ivan (1998), "Enrutamiento y transmisión óptimos sin interbloqueo en redes de cubo de Fibonacci" (PDF) , Utilitas Mathematica , 53 : 159–166, archivado desde el original (PDF) el 25 de julio de 2011.
- Taranenko, A .; Vesel, A. (2007), "Reconocimiento rápido de cubos de Fibonacci", Algorithmica , 49 (2): 81–93, doi : 10.1007 / s00453-007-9026-5.
- Wu, Jie (1997), "Extended Fibonacci cubes", IEEE Transactions on Parallel and Distributed Systems , 8 (12): 1203-1210, doi : 10.1109 / 71.640012.
- Zhang, Heping; Ou, Lifeng; Yao, Haiyuan (2009), "Cubos similares a Fibonacci como gráficos de transformación Z ", Matemáticas discretas , 309 (6): 1284-1293, doi : 10.1016 / j.disc.2008.01.053 , MR 2510538.