В теории графов кубосвязные циклы — это неориентированный кубический граф , образованный заменой каждой вершины графа гиперкуба циклом . Он был представлен Preparata & Vuillemin (1981) для использования в качестве топологии сети в параллельных вычислениях .
Кубосвязные циклы порядка n (обозначаемые CCC n ) можно определить как граф, сформированный из набора n 2 n узлов, индексированных парами чисел ( x , y ), где 0 ≤ x < 2 n и 0 ≤ y < н . Каждый такой узел соединен с тремя соседями: ( x , ( y + 1) mod n ) , ( x , ( y − 1) mod n ) и ( x ⊕ 2 y , y ) , где «⊕» обозначает побитовое число. исключительная или операция над двоичными числами.
Этот граф также можно интерпретировать как результат замены каждой вершины n -мерного графа гиперкуба на n -вершинный цикл. Вершины графа гиперкуба индексируются числами x , а позиции внутри каждого цикла — числами y .
Кубосвязные циклы порядка n — это граф Кэли группы , которая действует на двоичные слова длины n путем вращения и переворачивания битов слова. [1] Генераторы, используемые для формирования этого графа Кэли из группы, представляют собой элементы группы, которые действуют, поворачивая слово на одну позицию влево, поворачивая его на одну позицию вправо или переворачивая его первый бит. Поскольку это граф Кэли, он вершинно-транзитивен : существует симметрия графа, отображающая любую вершину в любую другую вершину.
Диаметр кубосвязных циклов порядка n равен 2 n + ⌊n/2⌋ − 2 для любого n ≥ 4 ; самая дальняя точка от ( x , y ) равна (2 n - x - 1, ( y + n /2) mod n ). [2] Сикора и Вртё (1993) показали, что число пересечений CCC n равно ((1/20) + o(1)) 4 n .
Согласно гипотезе Ловаса , граф кубически-связных циклов всегда должен содержать гамильтонов цикл , и теперь известно, что это верно. В более общем смысле, хотя эти графы не являются панциклическими , они содержат циклы всех возможных четных длин, кроме ограниченного числа, а когда n нечетно, они также содержат множество возможных нечетных длин циклов. [3]
Циклы, связанные с кубом, были исследованы Preparata и Vuillemin (1981), которые применили эти графики в качестве схемы соединения сети , соединяющей процессоры в параллельном компьютере . В этом приложении циклы, связанные с кубом, обладают преимуществами связности гиперкубов, но при этом требуют всего три соединения на процессор. Препарата и Вийемен показали, что планарная компоновка, основанная на этой сети, имеет оптимальную сложность площади × времени 2 для многих задач параллельной обработки.