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

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

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

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

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

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

Граф гиперкуба $Q n$ может быть построен из семейства подмножеств множества с n $элементами$ путем создания вершины для каждого возможного подмножества и соединения двух вершин ребром всякий раз, когда соответствующие подмножества различаются одним элементом. Эквивалентно, его можно построить, используя $2 n$ вершин, помеченных $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 2$ . В более общем плане декартово произведение копий полного графа называется графом Хэмминга ; графы гиперкубов являются примерами графов Хэмминга.

Примеры

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

$Q 2$ — цикл длины $4$ .

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

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

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

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

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

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

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

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

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

Другие объекты недвижимости

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

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

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

Проблемы

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

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

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

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

Примечания

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