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

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

Построение

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

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

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

Примеры

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

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

• графа Q _n в точности равна ${\displaystyle \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. // Computers & Mathematics with Applications . — 1988. — Т. 15 , вып. 4 . — С. 277–289 . — doi : . .