Граф гиперкуба - Hypercube graph

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

Граф гиперкуба Q_п (за п > 1) :

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

Семья Q_п для всех п > 1 это Семейство графов Леви

Проблемы

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

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

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

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

Примечания

1. Уоткинс, Джон Дж. (2004), Через доску: математика задач на шахматной доске, Princeton University Press, стр. 68, ISBN  978-0-691-15498-5.
2. Миллс, У. Х. (1963), "Некоторые полные циклы на п-куб », Труды Американского математического общества, Американское математическое общество, 14 (4): 640–643, Дои:10.2307/2034292, JSTOR  2034292.
3. Финк, Дж. (2007), "Совершенное паросочетание распространяется на гамильтоновы циклы в гиперкубах", Журнал комбинаторной теории, серия B, 97 (6): 1074–1076, Дои:10.1016 / j.jctb.2007.02.007.
4. Раски, Ф. и Сэвидж, К. Сочетания распространяются на гамильтоновы циклы в гиперкубах на открытом проблемном саду. 2007 г.
5. Рингель, Г. (1955 г.), "Убер дрей комбинаторные проблемы ам" п-dimensionalen Wiirfel und Wiirfelgitter ", Abh. Математика. Сем. Univ. Гамбург, 20: 10–19, МИСТЕР  0949280
6. Харари, Фрэнк; Hayes, John P .; Ву, Хорнг-Джих (1988), «Обзор теории графов гиперкубов» (PDF), Компьютеры и математика с приложениями, 15 (4): 277–289, Дои:10.1016/0898-1221(88)90213-1, МИСТЕР  0949280.
7. Оптимальные нумерации и изопериметрические задачи на графах, Л.Х. Харпер, Журнал комбинаторной теории, 1, 385–393, Дои:10.1016 / S0021-9800 (66) 80059-5
8. Ройхман Ю. (2000), "Об ахроматическом числе гиперкубов", Журнал комбинаторной теории, серия B, 79 (2): 177–182, Дои:10.1006 / jctb.2000.1955.
9. Шимански, Тед Х. (1989), "О перестановочной способности гиперкуба с коммутацией каналов", Proc. Междунар. Конф. по параллельной обработке, 1, Silver Spring, MD: IEEE Computer Society Press, стр. 103–110..

Рекомендации

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