stringtranslate.com

Ciclos cúbicos conexos

Los ciclos cúbicos conexos de orden 3, dispuestos geométricamente en los vértices de un cubo truncado .

En teoría de grafos , los ciclos cúbicos conexos son grafos cúbicos no dirigidos , formados al reemplazar cada vértice de un grafo hipercubico por un ciclo . Fue introducido por Preparata y Vuillemin (1981) para su uso como topología de red en computación paralela .

Definición

Los ciclos cúbicos conexos de orden n (denotados como CCC n ) se pueden definir como un grafo 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 la operación exclusiva bit a bit o sobre números binarios.

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

Propiedades

Los ciclos cúbicos conexos de orden n son el gráfico 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 gráfico 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 gráfico de Cayley, es transitivo de vértice : existe una simetría del gráfico que asigna cualquier vértice a cualquier otro vértice.

El diámetro de los ciclos conexos al cubo de orden n es 2 n + ⌊n/2⌋ − 2 para cualquier n ≥ 4; el punto más alejado de ( xy ) es (2 n  −  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 n .

Según la conjetura de Lovász , el gráfico de ciclo conexo al cubo siempre debería contener un ciclo hamiltoniano , y ahora se sabe que esto es cierto. En términos más generales, aunque estos gráficos no son pancíclicos , contienen ciclos de todas las longitudes pares posibles, excepto un número acotado, y cuando n es impar, también contienen muchas de las longitudes impares posibles de los ciclos. [3]

Aplicación de procesamiento paralelo

Preparata y Vuillemin (1981) investigaron los ciclos conexos en cubos y aplicaron estos gráficos como patrón de interconexión de una red que conecta los procesadores en una computadora paralela . En esta aplicación, los ciclos conexos en cubos tienen las ventajas de conectividad de los hipercubos, pero 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

  1. ^ Akers y Krishnamurthy (1989); Annexstein, Baumslag y Rosenberg (1990).
  2. ^ Friš, Havel y Liebl (1997).
  3. ^ Germa, Heydemann y Sotteau (1998).

Referencias