Граф гиперкуба¶

Граф гиперкуба (гиперкубический граф, кубический граф, \(n\)-куб, \(Q_n\)) — это регулярный граф, вершины которого соответствуют двоичным векторам длины \(n\), а рёбра соединяют вершины, различающиеся ровно в одной координате (то есть имеющие расстояние Хэмминга, равное 1). Граф гиперкуба является одним из классических объектов теории графов, комбинаторики, информатики и параллельных вычислений.

¶Определение и обозначения

Граф гиперкуба размерности \(n\) (обозначается \(Q_n\)) строится на множестве вершин \(V = \{0,1\}^n\), то есть на множестве всех двоичных строк длины \(n\). Две вершины \(u\) и \(v\) соединены ребром тогда и только тогда, когда их двоичные представления различаются ровно в одном бите. Таким образом, степень каждой вершины равна \(n\), а общее число вершин составляет \(2^n\). Число рёбер в \(Q_n\) равно \(n \cdot 2^{n-1}\).

Граф \(Q_n\) является \(n\)-регулярным, двудольным, гамильтоновым и эйлеровым (при \(n \ge 2\)). Он также является дистанционно-регулярным графом.

¶История

Понятие гиперкуба как геометрической фигуры известно с античности (трёхмерный куб). В математике графы, соответствующие гиперкубам, начали систематически изучаться в середине XX века. Важную роль сыграли работы по теории кодирования (коды Хэмминга), где гиперкуб естественным образом возникает как пространство двоичных векторов. В 1960-х годах гиперкубические графы стали рассматриваться как топология для многопроцессорных вычислительных систем (гиперкубовая архитектура). В 1980-е годы компания Intel (признана в РФ организацией, деятельность которой нежелательна) выпустила суперкомпьютер iPSC/1 с топологией гиперкуба. С тех пор граф гиперкуба остаётся одной из базовых моделей для параллельных алгоритмов.

¶Свойства

¶Основные характеристики

• Диаметр: \(n\) (максимальное расстояние между вершинами равно числу координат, в которых они различаются).
• Обхват: 4 (минимальный цикл имеет длину 4, за исключением \(Q_1\) и \(Q_2\)).
• Хроматическое число: 2 (граф двудолен, одна доля — вершины с чётным числом единиц, другая — с нечётным).
• Хроматический индекс: \(n\) (по теореме Визинга, так как степень равна \(n\)).
• Число вершинной связности: \(n\) (граф \(n\)-связен).
• Число рёберной связности: \(n\).

¶Симметрия

Граф гиперкуба обладает высокой степенью симметрии. Он является вершинно-транзитивным и рёберно-транзитивным. Его группа автоморфизмов изоморфна полупрямому произведению симметрической группы \(S_n\) и группы \((Z_2)^n\), что соответствует перестановкам координат и инвертированию битов в каждой координате. Порядок группы автоморфизмов равен \(2^n \cdot n!\).

¶Двудольность

Граф \(Q_n\) является двудольным. Разбиение на доли производится по чётности числа единиц в двоичном представлении вершины. Вершины с чётным весом (числом единиц) образуют одну долю, с нечётным — другую. Размеры долей равны \(2^{n-1}\) (при \(n \ge 1\)).

¶Гамильтоновость

Для всех \(n \ge 2\) граф \(Q_n\) содержит гамильтонов цикл. Более того, существует гамильтонов цикл, который обходит все вершины ровно один раз. Для \(n=1\) граф \(Q_1\) представляет собой ребро, которое не является циклом.

¶Эйлеровость

Граф \(Q_n\) является эйлеровым (содержит эйлеров цикл) тогда и только тогда, когда степень каждой вершины чётна, то есть когда \(n\) чётно. Для нечётных \(n\) граф не является эйлеровым, но содержит эйлерову цепь.

¶Рекурсивная структура

Граф гиперкуба \(Q_n\) может быть построен рекурсивно из двух копий \(Q_{n-1}\). Для этого берутся два экземпляра \(Q_{n-1}\), и соответствующие вершины (с одинаковыми двоичными наборами) соединяются рёбрами. Полученный граф и есть \(Q_n\). Эта рекурсивная структура является основой для многих алгоритмов, работающих на гиперкубе.

¶Примеры для малых n

• \(Q_0\): граф с одной вершиной (без рёбер). Соответствует нульмерному гиперкубу (точке).
• \(Q_1\): граф с двумя вершинами и одним ребром. Соответствует одномерному гиперкубу (отрезку).
• \(Q_2\): цикл длины 4 (квадрат). Соответствует двумерному гиперкубу.
• \(Q_3\): трёхмерный куб (8 вершин, 12 рёбер). Известен как граф куба.
• \(Q_4\): четырёхмерный гиперкуб (16 вершин, 32 ребра). Его проекции часто изображаются в виде двух вложенных кубов.

¶Применение

¶Параллельные вычисления

Топология гиперкуба долгое время была одной из основных для многопроцессорных систем. В такой архитектуре процессоры размещаются в вершинах \(n\)-мерного куба, а связи между ними проходят по рёбрам. Это обеспечивает небольшие расстояния между любыми двумя процессорами (не более \(n\) шагов) и хорошую масштабируемость. Примеры суперкомпьютеров: Intel iPSC/1, nCUBE, Connection Machine CM-2.

¶Теория кодирования

Граф гиперкуба является графом расстояний для кода Хэмминга. В нём вершины — это кодовые слова, а рёбра соответствуют однократным ошибкам. Поиск кодов, исправляющих ошибки, сводится к поиску подмножеств вершин гиперкуба с заданным минимальным расстоянием.

¶Комбинаторика

Графы гиперкубов используются для изучения булевых функций, так как каждая булева функция от \(n\) переменных может быть представлена как подмножество вершин \(Q_n\) (наборов, на которых функция равна 1). Свойства функций (монотонность, самодвойственность, линейность) интерпретируются в терминах графа.

¶Алгоритмы и структуры данных

Гиперкуб применяется в алгоритмах сортировки (например, битонная сортировка на гиперкубе), в алгоритмах поиска кратчайших путей, в задачах маршрутизации. Также на основе гиперкуба строятся сети с малым диаметром (например, графы де Брёйна).

¶Вариации и обобщения

• Связанные графы: графы-циклы, графы-тороиды, графы-сетки.
• Обобщённые гиперкубы: графы, вершины которых — векторы над конечным алфавитом (не обязательно двоичным). Рёбра соединяют вершины, различающиеся в одной координате.
• Сложенные гиперкубы: графы, полученные склеиванием двух гиперкубов по определённым правилам (например, folded cube).
• Гиперкубы с перестановками: графы, в которых рёбра соединяют вершины, связанные перестановкой координат.

¶Интересные факты

• Граф \(Q_n\) является планарным только для \(n \le 3\). Для \(n=4\) и выше он содержит подграф, гомеоморфный \(K_{3,3}\) или \(K_5\), что делает его непланарным.
• Число остовных деревьев в \(Q_n\) равно \(2^{2^n - n - 1} \prod_{k=1}^n k^{C(n,k)}\), где \(C(n,k)\) — биномиальный коэффициент.
• Граф \(Q_n\) является графом единичных кубов в \(n\)-мерном пространстве.
• В \(Q_n\) существует ровно \(2^n\) различных гамильтоновых циклов (с точностью до изоморфизма).
• Гиперкуб \(Q_n\) является дистанционно-регулярным графом с массивом пересечений \(\{n, n-1, \dots, 1; 1, 2, \dots, n\}\).

¶Источники

• Харари Ф. Теория графов. — М.: Мир, 1973.
• Дистель Р. Теория графов. — Новосибирск: Изд-во Института математики, 2002.
• Bondy J. A., Murty U. S. R. Graph Theory. — Springer, 2008.
• Leighton F. T. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. — Morgan Kaufmann, 1992.
• Brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs. — Springer, 1989.