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

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

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

Граф гиперкуба Qn _также может быть построен путем создания вершины для каждого подмножества набора из n -элементов с двумя смежными вершинами, когда их подмножества различаются в одном элементе, или путем создания вершины для каждого n -значного двоичного числа , с две вершины смежны, если их двоичные представления отличаются на одну цифру. Это n -кратное декартово произведение полного двухвершинного графа , которое можно разложить на две копии Q _{n – 1} , соединенные друг с другом идеальным паросочетанием .

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

Строительство

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

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

Альтернативно, Q _n может быть построен из непересекающегося объединения двух гиперкубов Q _{n - 1} путем добавления ребра из каждой вершины в одной копии Q _{n - 1} к соответствующей вершине в другой копии, как показано на рисунке. Соединяющиеся края образуют идеальное соответствие .

рекурсивный алгоритм построения матрицы смежности гиперкуба An _{Приведенная выше конструкция дает} . Копирование осуществляется с помощью произведения Кронекера , так что две копии Q _{n − 1} имеют матрицу смежности. $\mathrm {1} _{2}\otimes _{K}A_{n-1}$ ,где $1_{d}$ является единичной матрицей в $d$ размеры. При этом соединяющиеся ребра имеют матрицу смежности $A_{1}\otimes _{K}1_{2^{n-1}}$. Сумма этих двух слагаемых дает рекурсивную функцию для матрицы смежности гиперкуба:

$A_{n}={\begin{cases}1_{2}\otimes _{K}A_{n-1}+A_{1}\otimes _{K}1_{2^{n-1}}&{\text{if }}n>1\\{\begin{bmatrix}0&1\\1&0\end{bmatrix}}&{\text{if }}n=1\end{cases}}$

Другая конструкция Q _n представляет собой произведение n декартово двухвершинных полных графов K ₂ . В более общем плане декартово произведение копий полного графа называется графом Хэмминга ; графы гиперкубов являются примерами графов Хэмминга.

Примеры

Граф Q ₀ состоит из одной вершины, а Q ₁ представляет собой полный граф из двух вершин.

Q ₂ — цикл длины 4 .

Граф Q3 _{представляет} собой 1-скелет куба и представляет собой плоский граф с восемью вершинами и двенадцатью ребрами .

Граф Q ₄ является графом Леви конфигурации Мёбиуса . Это также график Найта для тороидального $4\times 4$ шахматная доска .

Свойства

Двусторонность

Любой граф гиперкуба двудольный : его можно раскрасить только двумя цветами. Два цвета этой раскраски можно найти при построении подмножеств графов гиперкубов, придав один цвет подмножествам с четным числом элементов, а другой цвет — подмножествам с нечетным числом элементов.

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

Гамильтонов цикл на тессеракте с вершинами, помеченными 4-битным циклическим кодом Грея.

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

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

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

Другая недвижимость

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

• — диаграмма Хассе конечной булевой алгебры .
• представляет собой медианный график . Каждый медианный граф является изометрическим подграфом гиперкуба и может быть сформирован как сокращение гиперкуба.
• имеет более 2 ^{2 n-2} идеальные совпадения. (это еще одно следствие, которое легко следует из индуктивной конструкции.)
• является дуготранзитивным и симметричным . Симметрии графов гиперкубов можно представить в виде знаковых перестановок .
• содержит все циклы длины 4, 6, ..., 2 ^н и, таким образом, является бипанциклическим графом .
• может быть нарисован как граф единичных расстояний на евклидовой плоскости, используя построение графа гиперкуба из подмножеств набора из n элементов, выбирая отдельный единичный вектор для каждого элемента набора и помещая вершину, соответствующую множеству S, в сумма векторов в S .
• является n- вершинно-связным графом по теореме Балинского .
• планарна n (может быть нарисована без пересечений) тогда и только тогда, когда ≤ 3 . Для больших значений n гиперкуб имеет род ( n − 4)2 ^{п - 3} + 1 .
• имеет точно $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$ охватывающие деревья .
• имеет пропускную способность ровно $\sum _{i=0}^{n-1}{\binom {i}{\lfloor i/2\rfloor }}$.
• имеет ахроматическое число, пропорциональное ${\sqrt {n2^{n}}}$, но константа пропорциональности точно не известна.
• имеет в качестве собственных значений своей матрицы смежности числа (− n , − n + 2, − n + 4, ... , n − 4, n − 2, n ), а в качестве собственных значений своей матрицы Лапласа числа (0 , 2, ..., 2 н ) . k - е собственное значение имеет кратность ${\binom {n}{k}}$ в обоих случаях.
• имеет изопериметрический номер час ( G ) знак равно 1 .

Семейство Qn _{является} для всех n > 1 семейством графов Леви .

Проблемы

Максимальные длины змей ( L _s ) и витков ( L _c ) в задаче «змеи в коробке» для размерностей n от 1 до 4

Проблема поиска самого длинного пути или цикла, который является индуцированным подграфом данного графа гиперкуба, известна как проблема «змеи в ящике» .

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

См. также

• граф де Брёйна
• Кубосвязные циклы
• Куб Фибоначчи
• График сложенного куба
• Граф Франкла – Рёдля
• Граф половинного куба
• Топология объединенной сети гиперкуба
• Частичный куб

Ссылки

• Харари, Ф .; Хейс, JP; Ву, Х.-Дж. (1988), «Обзор теории графов гиперкубов», Computers & Mathematics with Applications , 15 (4): 277–289, doi : 10.1016/0898-1221(88)90213-1 , hdl : 2027.42/27522 .