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

Графы, образованные ребрами и вершинами гиперкуба

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

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

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

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

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

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

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

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

${\displaystyle 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 .

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

Граф Q ₄ — это граф Леви конфигурации Мёбиуса . Он также является графом коня для тороидальной шахматной доски . ^[1] ${\displaystyle 4\times 4}$

Характеристики

Двупартийность

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

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

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

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

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

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

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

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

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

Семейство Q _n для всех n > 1 является семейством графов Леви .

Проблемы

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

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

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

Смотрите также

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

Примечания

1. Уоткинс, Джон Дж. (2004), По всей доске: Математика шахматных задач , Princeton University Press, стр. 68, ISBN 978-0-691-15498-5.
2. Миллс, WH (1963), «Некоторые полные циклы на n -кубе», Труды Американского математического общества , 14 (4), Американское математическое общество: 640–643, doi :10.2307/2034292, JSTOR  2034292.
3. Финк, Дж. (2007), «Идеальные паросочетания распространяются на гамильтоновы циклы в гиперкубах», Журнал комбинаторной теории, Серия B , 97 (6): 1074–1076, doi : 10.1016/j.jctb.2007.02.007.
4. Раски, Ф. и Сэвидж, К. Сопоставления распространяются на гамильтоновы циклы в гиперкубах в Open Problem Garden. 2007.
5. Рингель, Г. (1955), "Über drei kombinatorische Issuee am n- Dimensionen Wiirfel und Wiirfelgitter", Abh. Математика. Сем. унив. Гамбург , 20 : 10–19, MR  0949280
6. Harary, Frank ; Hayes, John P.; Wu, Horng-Jyh (1988), "Обзор теории графов гиперкуба" (PDF) , Computers & Mathematics with Applications , 15 (4): 277–289, doi :10.1016/0898-1221(88)90213-1, hdl : 2027.42/27522 , MR  0949280.
7. Оптимальные нумерации и изопериметрические задачи на графах, LH Harper, Журнал комбинаторной теории , 1, 385–393, doi :10.1016/S0021-9800(66)80059-5
8. Ройхман, Ю. (2000), «Об ахроматическом числе гиперкубов», Журнал комбинаторной теории, Серия B , 79 (2): 177–182, doi : 10.1006/jctb.2000.1955.
9. Шимански, Тед Х. (1989), «О возможности перестановки гиперкуба с коммутацией каналов», Труды Международной конференции по параллельной обработке , т. 1, Силвер-Спринг, Мэриленд: IEEE Computer Society Press, стр. 103–110.

Ссылки

• Харари, Ф.; Хейс, Дж. П.; Ву, Х.-Дж. (1988), «Обзор теории графов гиперкуба», Компьютеры и математика с приложениями , 15 (4): 277–289, doi : 10.1016/0898-1221(88)90213-1, hdl : 2027.42/27522.