En la teoría de grafos , los ciclos conectados al cubo es un grafo cúbico no dirigido , formado al reemplazar cada vértice de un gráfico hipercubo por un ciclo . Fue introducido por Preparata & Vuillemin (1981) para su uso como topología de red en computación paralela .
Definición
Los ciclos conectados al cubo de orden n (denominados CCC n ) se pueden definir como un gráfico formado a partir de un conjunto de n 2 n nodos, indexados por pares de números ( x , y ) donde 0 ≤ x <2 n 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 el bit a bit. operación exclusiva o sobre números binarios.
Este gráfico también se puede interpretar como el resultado de reemplazar cada vértice de un gráfico de hipercubo n- dimensional por un ciclo de n- vértices. Los vértices del gráfico del hipercubo están indexados por los números x , y las posiciones dentro de cada ciclo por los números y .
Propiedades
Los ciclos conectados al cubo de orden n son el gráfico de Cayley de un grupo que actúa sobre palabras binarias de longitud n mediante rotación y volteo de bits de la palabra. [1] Los generadores utilizados para formar este gráfico de Cayley del grupo son los elementos del grupo que actúan girando la palabra una posición hacia la izquierda, girándola una posición hacia la derecha o volteando su primer bit. Debido a que es un gráfico de Cayley, es un vértice transitivo : hay una simetría del gráfico que asigna cualquier vértice a cualquier otro vértice.
El diámetro de los ciclos conectados al cubo de orden n es 2 n + ⌊n / 2⌋ - 2 para cualquier n ≥ 4; el punto más alejado de ( x , y ) es (2 n - x - 1, ( y + n / 2) mod n ). [2] Sýkora y Vrťo (1993) mostraron que el número de cruces de CCC n es ((1/20) + o (1)) 4 n .
De acuerdo con la conjetura de Lovász , el gráfico de ciclo conectado al cubo siempre debe contener un ciclo hamiltoniano , y ahora se sabe que esto es cierto. De manera más general, aunque estos gráficos no son pancíclicos , contienen ciclos de todos menos un número limitado de posibles longitudes pares, y cuando n es impar, también contienen muchas de las posibles longitudes impares de los ciclos. [3]
Aplicación de procesamiento paralelo
Los ciclos conectados por cubos fueron investigados por Preparata y Vuillemin (1981) , quienes aplicaron estos gráficos como el patrón de interconexión de una red que conecta los procesadores en una computadora paralela . En esta aplicación, los ciclos conectados al cubo tienen las ventajas de conectividad de los hipercubos, mientras que solo requieren tres conexiones por procesador. Preparata y Vuillemin demostraron que un diseño plano basado en esta red tiene una complejidad óptima de área × tiempo 2 para muchas tareas de procesamiento en paralelo.
Notas
Referencias
- Akers, Sheldon B .; Krishnamurthy, Balakrishnan (1989), "Un modelo teórico de grupos para redes de interconexión simétricas", IEEE Transactions on Computers , 38 (4): 555–566, doi : 10.1109 / 12.21148.
- Annexstein, Fred; Baumslag, Marc; Rosenberg, Arnold L. (1990), "Gráficos de acción grupal 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 al cubo", 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 gráfico de ciclos conectados al cubo", 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 al cubo: una red versátil para el cálculo en paralelo", Comunicaciones del ACM , 24 (5): 300–309, doi : 10.1145 / 358645.358660 , hdl : 2142/74219.
- Sýkora, Ondrej; Vrťo, Imrich (1993), "Sobre el cruce de números de hipercubos y ciclos conectados al cubo", BIT Numerical Mathematics , 33 (2): 232-237, doi : 10.1007 / BF01989746 , hdl : 11858 / 00-001M-0000-002D- 92E4-9.