En teoría de grafos , los ciclos cúbicos conectados son un gráfico cúbico no dirigido , formado al reemplazar cada vértice de un gráfico de 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 cúbicos conectados 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 de n dimensiones por un ciclo de n vértices. Los vértices del gráfico de hipercubo están indexados por los números x y las posiciones dentro de cada ciclo por los números y .
Los ciclos de cubos conectados 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 a partir 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 transitivo por vértices : hay una simetría en el gráfico que asigna cualquier vértice a cualquier otro vértice.
El diámetro de los ciclos cúbicos conectados 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) demostraron que el número de cruce de CCC n es ((1/20) + o(1)) 4 n .
Según la conjetura de Lovász , el gráfico de ciclos cuboconexos siempre debería 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 todas las longitudes pares posibles excepto un número limitado, y cuando n es impar también contienen muchas de las posibles longitudes impares de ciclos. [3]
Los ciclos de cubos conectados 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 a cubos tienen las ventajas de conectividad de los hipercubos y 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 paralelo.