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

Граф гиперкуба
Вершин	2n
Рёбер	2n−1n
Диаметр	n
Обхват	4 if n≥2
Автоморфизмы	n! 2n
Хроматическое число	2
Спектр	$\{(n-2k)^{\binom {n}{k}};k=0,\ldots ,n\}$
Свойства	Симметричный клетка Граф Мура дистанционно-регулярный дистанционно-транзитивный единичных расстояний гамильтонов двудольный
Обозначение	Qn
Медиафайлы на Викискладе

В теории графов графом гиперкуба Q_n называется регулярный граф с 2ⁿ вершинами, 2ⁿ⁻¹n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q₃ — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом.

Графы гиперкубов не следует путать с кубическими графами, в которых в каждую вершину сходится ровно три ребра. Единственный гиперкуб, граф которого кубический — это Q₃.

Построение

Построение Q₃ путём соединения пар соответствующих вершин двух копий Q₂

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

Q_n+1 можно построить из несвязного объединения двух гиперкубов Q_n путём добавления рёбер от каждой вершины одной копии Q_n до соответствующей вершины другой копии, как показано на рисунке. Соединяющие рёбра образуют паросочетание.

Ещё одно определение Q_n — прямое произведение n полных графов K₂, содержащих две вершины.

Примеры

Граф Q₀ состоит из единственной вершины, граф Q₁ является полным графом с двумя вершинами, а Q₂ — цикл длины 4.

Граф Q₃ — это 1-скелет куба, планарный граф с восемью вершинами и двенадцатью рёбрами.

Граф Q₄ — это граф Леви конфигурации Мёбиуса.

Свойства

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

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

Гамильтоновы циклы

Любой гиперкуб Q_n с n > 1 имеет гамильтонов цикл, проходящий через каждую вершину ровно один раз. Вдобавок, гамильтонов путь между вершинами u, v существует тогда и только тогда, когда u и v имеют различные цвета в двухцветной раскраске графа. Оба факта легко проверить по индукции по размерности гиперграфа с построением графа гиперкуба путём соединения двух меньших гиперкубов.

Вышеописанные свойства гиперкуба тесно связаны с теорией кодов Грея. Более точно, существует биективное соответствие между множеством n-битных циклических кодов Грея и множеством гамильтоновых циклов в гиперкубе Q_n. Аналогичное свойство имеет место для ацикличных n-битных кодов Грея и гамильтоновых путей.

Меньше известен факт, что любое совершенное паросочетание в гиперкубе можно расширить до гамильтонова цикла. Вопрос, можно ли любое паросочетание расширить до гамильтонова цикла, остаётся открытым.

Другие свойства

Граф гиперкуба Q_n (n > 1) :

• является диаграммой Хассе конечной булевой алгебры;
• является медианным графом. Любой медианный граф является изометричным подграфом гиперкуба и может быть образован путём усечения гиперкуба;
• имеет более чем 2^2n-2 совершенных паросочетаний (это другое следствие, следующее из индуктивного построения);
• является транзитивным относительно дуг и симметричным. Симметрии графов гиперкубов можно представить как знаковые перестановки, группа автоморфизмов изоморфна $S_{n}\wr \mathbb {Z} _{2}$;
• содержит все циклы длины 4, 6, …, 2ⁿ и поэтому является бипанциклическим графом;
• может быть нарисован как граф единичных расстояний на евклидовой плоскости путём выбора единичного вектора для каждого элемента множества и размещения каждой вершины, соответствующей множеству S, в точке, соответствующей сумме векторов из S;
• является вершинно n-связным графом по теореме Балинского;
• является планарным (может быть нарисован без пересечений) в том и только в том случае, когда n ≤ 3. Для больших значений n гиперкуб имеет род $(n-4)2^{n-3}+1$;

• имеет в точности $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$ остовных дерева;
• семейство Q_n (n > 1) является семейством графов Леви;
• известно, что ахроматическое число графа Q_n пропорционально ${\sqrt {n2^{n}}}$, но точная константа пропорциональности неизвестна;

• ширина полосы графа Q_n в точности равна $\sum _{i=0}^{n}{\binom {n}{\lfloor n/2\rfloor }}$.;
• собственные значения матрицы инцидентности равны (-n,-n+2,-n+4,…,n-4,n-2,n), а собственные значения матрицы Кирхгофа графа равны (0,2,…,2n);
• изопериметрическое число равно h(G)=1.

Задачи

Задача поиска самого длинного пути или цикла, являющегося порождённым подграфом заданного графа гиперкуба, известна как задача о змее в коробке.

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

См. также

• Кубически соединённые циклы
• Куб Фибоначчи
• Сложенный граф куба
• Уполовиненный граф куба

Ссылки

• F. Harary, J. P. Hayes, H.-J. Wu. A survey of the theory of hypercube graphs // Computers & Mathematics with Applications. — 1988. — Т. 15, вып. 4. — С. 277–289. — doi:10.1016/0898-1221(88)90213-1..