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

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

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

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

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

Строительство [ править ]

Построение

Q 3

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

Q 2

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

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

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

Примеры [ править ]

Граф $Q 0$ состоит из одной вершины, $Q 1$ - полный граф с двумя вершинами, а $Q 2$ - цикл длины $4$ .

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

График , $Q 4$ представляет собой график , Леви от конфигурации Мёбиуса . Это также граф коня для тороидальной шахматной доски . ^[1] ${\ displaystyle 4 \ times 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$ и, таким образом, является бипанциклическим графом .
может быть нарисован как граф единичных расстояний на евклидовой плоскости, используя построение графа гиперкуба из подмножеств набора из $n$ элементов, выбирая отдельный единичный вектор для каждого элемента набора и помещая вершину, соответствующую набору $S,$ в точку сумма векторов в $S$ .
является n- вершинно-связным графом по теореме Балинского
является плоской (может быть обращено без каких - либо пересечений) тогда и только тогда , когда $п \leq 3$ . Для больших значений $n$ гиперкуб имеет род $(n - 4) 2 n - 3 + 1$ . ^[5]^[6]
имеет ровно остовные деревья . ^[6] ${\ displaystyle 2 ^ {2 ^ {n} -n-1} \ prod _ {k = 2} ^ {n} k ^ {n \ select k}}$
имеет пропускную способность точно . ^[7] ${\ Displaystyle \ сумма _ {я = 0} ^ {п-1} {\ binom {я} {\ lfloor i / 2 \ rfloor}}}$
имеет ахроматическое число, пропорциональное , но коэффициент пропорциональности точно не известен. ^[8] ${\ displaystyle {\ sqrt {n2 ^ {n}}}}$
имеет в качестве собственных значений своей матрицы смежности числа $(- n, - n + 2, - n + 4, ..., n - 4, n - 2, n),$ а в качестве собственных значений своей матрицы Лапласа - числа $(0 , 2, ..., 2 п)$ . В обоих случаях $k-$ е собственное значение имеет кратность . ${\ displaystyle {\ binom {n} {k}}}$
имеет изопериметрический номер $h (G) = 1$ .

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

Проблемы [ править ]

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

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

См. Также [ править ]

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

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

Заметки [ править ]

Перейти ↑ Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, p. 68, ISBN 978-0-691-15498-5.
^ Миллс, WH (1963), "Некоторые полные циклы на $п$ -куба", Труды Американского математического общества , Американского математического общества, 14 (4): 640-643, DOI : 10,2307 / 2034292 , JSTOR 2034292 .
^ Финк, Дж. (2007), «Идеальные паросочетания распространяются на гамильтоновы циклы в гиперкубах», Журнал комбинаторной теории, серия B , 97 (6): 1074–1076, doi : 10.1016 / j.jctb.2007.02.007.
^ Рэски, Ф. и Сэвидж, С. Сопоставления распространяются на гамильтоновы циклы в гиперкубах на Open Problem Garden. 2007 г.
^ Рингель, Г. (1955), "Убер drei kombinatorische Probleme am $n$ -dimensionalen Wiirfel und Wiirfelgitter", Abh. Математика. Сем. Univ. Гамбург , 20 : 10–19, MR 0949280
^ a b Харари, Фрэнк ; Hayes, John P .; В, Horng-JYH (1988), "Исследование теории графов гиперкуба" (PDF) , компьютеры и математика с приложениями , 15 (4): 277-289, да : 10,1016 / 0898-1221 (88) 90213- 1 , Руководство по ремонту 0949280 .
^ Оптимальных нумерации и Изопериметрические проблемы на графах, LH Harper, Журнал комбинаторной теории , 1, 385-393, DOI : 10.1016 / S0021-9800 (66) 80059-5
^ Ройхман, Y. (2000), "О ахроматических Количество Гиперкубы", Журнал комбинаторной теории, серии B , 79 (2): 177-182, DOI : 10,1006 / jctb.2000.1955.
^ Шимански, Тед Х. (1989), "О перестановочной способности гиперкуба с коммутацией каналов", Proc. Междунар. Конф. on Parallel Processing , 1 , Silver Spring, MD: IEEE Computer Society Press, стр. 103–110.

Ссылки [ править ]

Harary, F .; Hayes, JP; Ву, Х.-Дж. (1988), "Исследование теории графов гиперкуба", компьютеры и математика с приложениями , 15 (4): 277-289, да : 10,1016 / 0898-1221 (88) 90213-1 , ЛВП : 2027,42 / 27522.

[1] Перейти ↑ Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, p. 68, ISBN 978-0-691-15498-5.

[2] Миллс, WH (1963), "Некоторые полные циклы на $п$ -куба", Труды Американского математического общества , Американского математического общества, 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 г.

[ringel-5] Рингель, Г. (1955), "Убер drei kombinatorische Probleme am $n$ -dimensionalen Wiirfel und Wiirfelgitter", Abh. Математика. Сем. Univ. Гамбург , 20 : 10–19, MR 0949280

[hhw-6] Харари, Фрэнк ; Hayes, John P .; В, Horng-JYH (1988), "Исследование теории графов гиперкуба" (PDF) , компьютеры и математика с приложениями , 15 (4): 277-289, да : 10,1016 / 0898-1221 (88) 90213- 1 , Руководство по ремонту 0949280 .

[7] Оптимальных нумерации и Изопериметрические проблемы на графах, LH Harper, Журнал комбинаторной теории , 1, 385-393, DOI : 10.1016 / S0021-9800 (66) 80059-5

[8] Ройхман, Y. (2000), "О ахроматических Количество Гиперкубы", Журнал комбинаторной теории, серии B , 79 (2): 177-182, DOI : 10,1006 / jctb.2000.1955.

[9] Шимански, Тед Х. (1989), "О перестановочной способности гиперкуба с коммутацией каналов", Proc. Междунар. Конф. on Parallel Processing , 1 , Silver Spring, MD: IEEE Computer Society Press, стр. 103–110.