Ciclos conectados por cubos

En teoría de grafos , el ciclo cúbico conexo es un grafo cúbico no dirigido , formado al reemplazar cada vértice de un grafo hipercubo por un ciclo . Fue introducido por Preparata y Vuillemin (1981) para su uso como topología de red en computación paralela .

Los ciclos conectados por cubos de orden n (denotados CCC _n ) se pueden definir como un grafo formado a partir de un conjunto de n 2 ⁿ nodos, indexados por pares de números ( x , y ) donde 0 ≤ x < 2 ⁿ y 0 ≤ y < n . Cada uno de estos nodos está conectado a tres vecinos: ( x , ( y + 1) mod n ) , ( x , ( y − 1) mod n ) , y ( x ⊕ 2 ^y , y ) , donde "⊕" denota la operación OR exclusiva bit a bit en números binarios.

Este gráfico también puede interpretarse como el resultado de reemplazar cada vértice de un grafo hipercubo n- dimensional por un ciclo de n vértices. Los vértices del grafo hipercubo están indexados por los números x , y las posiciones dentro de cada ciclo por los números y .

El ciclo cúbico conectado de orden n es el grafo de Cayley de un grupo que actúa sobre palabras binarias de longitud n mediante rotación e inversión de bits de la palabra. ^{[ 1 ]} Los generadores utilizados para formar este grafo de Cayley a partir del grupo son los elementos del grupo que actúan rotando la palabra una posición a la izquierda, rotándola una posición a la derecha o invirtiendo su primer bit. Debido a que es un grafo de Cayley, es transitivo en vértices : existe una simetría del grafo que mapea cualquier vértice a cualquier otro vértice.

El diámetro de los ciclos conectados por cubos de orden n es 2 n + ⌊n/2⌋ − 2 para cualquier n  ≥  4; el punto más alejado de ( x , y ) es (2 ⁿ − x − 1, ( y + n /2) mod n ). ^{[ 2 ]} Sýkora y Vrťo (1993) demostraron que el número de cruces de CCC _n es ((1/20) + o(1)) 4 ⁿ .            

Según la conjetura de Lovász , el grafo de ciclos conexos de cubos siempre debería contener un ciclo hamiltoniano , y ahora se sabe que esto es cierto. De forma más general, aunque estos grafos no son pancíclicos , contienen ciclos de todas las longitudes pares posibles, excepto un número limitado, y cuando n es impar, también contienen muchas de las longitudes impares posibles de ciclos. ^{[ 3 ]}

Preparata y Vuillemin (1981) investigaron los ciclos conectados por cubos y los aplicaron como patrón de interconexión de una red que conecta los procesadores en una computadora paralela . En esta aplicación, los ciclos conectados por cubos ofrecen las ventajas de conectividad de los hipercubos, requiriendo solo tres conexiones por procesador. Preparata y Vuillemin demostraron que una disposición planar basada en esta red tiene una complejidad óptima de área ^×  tiempo²  para muchas tareas de procesamiento paralelo.

• Akers, Sheldon B.; Krishnamurthy, Balakrishnan (1989), "Un modelo de teoría de grupos para redes de interconexión simétricas", IEEE Transactions on Computers , 38 (4): 555– 566, Bibcode : 1989ITCmp..38..555A , doi : 10.1109/12.21148.
• Annexstein, Fred; Baumslag, Marc; Rosenberg, Arnold L. (1990), "Grafos de acción de grupo y arquitecturas paralelas", SIAM Journal on Computing , 19 (3): 544– 569, doi : 10.1137/0219037.
• Friš, Ivan; Havel, Ivan; Liebl, Petr (1997), "El diámetro de los ciclos conectados por cubos", Information Processing Letters , 61 (3): 157– 160, doi : 10.1016/S0020-0190(97)00013-6.
• Germa, Anne; Heydemann, Marie-Claude; Sotteau, Dominique (1998), "Ciclos en el grafo de ciclos conectados por cubos", Matemáticas Aplicadas Discretas , 83 ( 1–3 ): 135–155 , doi : 10.1016/S0166-218X(98)80001-2 , MR 1622968 .
• Preparata, Franco P.; Vuillemin , Jean (1981), "Los ciclos conectados por cubos: una red versátil para la computación paralela", Communications of the ACM , 24 (5): 300–309 , doi : 10.1145/358645.358660 , hdl : 2142/74219 , S2CID 8538576 .
• Sýkora, Ondrej; Vrťo, Imrich (1993), "Sobre los números de cruce de hipercubos y ciclos conectados por cubos", BIT Numerical Mathematics , 33 (2): 232– 237, doi : 10.1007/BF01989746 , hdl : 11858/00-001M-0000-002D-92E4-9 , S2CID 15913153 .