Граф гиперкуба - Hypercube graph
Граф гиперкуба | |
---|---|
![]() Граф гиперкуба Q4 | |
Вершины | 2п |
Края | 2п−1п |
Диаметр | п |
Обхват | 4 если п ≥ 2 |
Автоморфизмы | п! 2п |
Хроматическое число | 2 |
Спектр | |
Характеристики | Симметричный Расстояние регулярное Единичное расстояние Гамильтониан Двудольный |
Обозначение | Qп |
Таблица графиков и параметров |
В теория графов, то граф гиперкуба Qп граф, образованный из вершин и ребер п-размерный гиперкуб. Например, кубический график Q3 это граф, образованный 8 вершинами и 12 ребрами трехмерного куба.Qп имеет 2п вершины, 2п−1п рёбер и является регулярный граф с п ребра, соприкасающиеся с каждой вершиной.
Граф гиперкуба Qп также могут быть построены путем создания вершины для каждого подмножество из п-элементный набор, с двумя смежными вершинами, когда их подмножества отличаются в одном элементе, или путем создания вершины для каждого п-цифра двоичное число, с двумя смежными вершинами, когда их двоичные представления отличаются одной цифрой. Это п-складывать Декартово произведение двувершины полный график, и может быть разложен на две копии Qп − 1 связаны друг с другом идеальное соответствие.
Графы гиперкуба не следует путать с кубические графы - графы, каждая вершина которых касается ровно трех ребер. Единственный граф гиперкуба Qп то есть кубический граф это кубический граф Q3.
Строительство
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Hypercubeconstruction.png/241px-Hypercubeconstruction.png)
Граф гиперкуба Qп может быть построен из семьи подмножества из набор с п элементов, создавая вершину для каждого возможного подмножества и соединяя две вершины ребром всякий раз, когда соответствующие подмножества отличаются одним элементом. Эквивалентно, он может быть построен с использованием 2п вершины, помеченные п-кусочек двоичные числа и соединяя две вершины ребром, когда Расстояние Хэмминга их лейблов одна. Эти две конструкции тесно связаны: двоичное число можно интерпретировать как набор (набор позиций, где у него есть 1 цифра), и два таких набора отличаются одним элементом, если два соответствующих двоичных числа имеют расстояние Хэмминга один.
В качестве альтернативы, Qп может быть построен из несвязный союз двух гиперкубов Qп − 1, добавив ребро из каждой вершины в одну копию Qп − 1 к соответствующей вершине в другой копии, как показано на рисунке. Соединяющиеся кромки образуют идеальное соответствие.
Еще одна конструкция Qп это Декартово произведение из п двухвершинные полные графы K2. В более общем смысле декартово произведение копий полного графа называется Граф Хэмминга; графы гиперкуба являются примерами графов Хэмминга.
Примеры
График Q0 состоит из одной вершины, а Q1 это полный график на двух вершинах и Q2 это цикл длины4.
График Q3 это 1-скелет из куб, а кубический график, планарный граф с восемью вершины и двенадцать края.
График Q4 это Граф Леви из Конфигурация Мебиуса. Это также граф рыцаря для тороидальный шахматная доска.[1]
Характеристики
Двудольность
Каждый граф гиперкуба двудольный: может быть цветной всего с двумя цветами. Два цвета этой раскраски можно найти из конструкции подмножества графов гиперкуба, задав один цвет подмножествам с четным числом элементов, а другой цвет - подмножествам с нечетным числом элементов.
Гамильтоничность
Каждый гиперкуб Qп с п > 1 имеет Гамильтонов цикл, цикл, который посещает каждую вершину ровно один раз. Кроме того, Гамильтонов путь существует между двумя вершинами ты и v тогда и только тогда, когда они имеют разные цвета в 2-раскраска графика. Оба факта легко доказать, используя принцип индукция на размерность гиперкуба и построение графа гиперкуба путем соединения двух меньших гиперкубов с сопоставлением.
Гамильтоничность гиперкуба тесно связана с теорией Коды Грея. Точнее есть биективный соответствие между набором п-битовые циклические коды Грея и множество гамильтоновых циклов в гиперкубе Qп.[2] Аналогичное свойство имеет место для ациклических п-битовые коды Грея и гамильтоновы пути.
Менее известен тот факт, что каждое совершенное паросочетание в гиперкубе продолжается до гамильтонова цикла.[3] Вопрос о том, продолжается ли каждое паросочетание до гамильтонова цикла, остается открытым.[4]
Другие свойства
Граф гиперкуба Qп (за п > 1) :
- это Диаграмма Хассе конечного Булева алгебра.
- это медианный график. Каждый медианный граф представляет собой изометрический подграф гиперкуба, и может быть сформирован как ретракция гиперкуба.
- имеет более чем 22п-2 идеальное соответствие. (это еще одно следствие, которое легко следует из индуктивного построения.)
- является переходная дуга и симметричный. Симметрии графов гиперкубов можно представить в виде подписанные перестановки.
- содержит все циклы длины 4, 6, ..., 2п и, таким образом, бипанциклический граф.
- возможно нарисованный как график единичного расстояния в евклидовой плоскости, используя построение графа гиперкуба из подмножеств множества п элементы, выбирая отличные единичный вектор для каждого элемента набора, и размещение вершины, соответствующей набору S при сумме векторов в S.
- это п-связный граф, к Теорема Балинского
- является планарный (возможно нарисованный без переходов) тогда и только тогда, когда п ≤ 3. Для больших значений п, гиперкуб имеет род (п − 4)2п − 3 + 1.[5][6]
- точно остовные деревья.[6]
- имеет пропускная способность точно .[7]
- имеет ахроматическое число пропорционально , но точная величина пропорциональности неизвестна.[8]
- имеет в качестве собственных значений своей матрицы смежности числа (−п, −п + 2, −п + 4, ... , п − 4, п − 2, п) а в качестве собственных значений его матрицы Лапласа числа (0, 2, ..., 2п). В kсобственное значение имеет кратность в обоих случаях.
- имеет изопериметрическое число час(грамм) = 1.
Семья Qп для всех п > 1 это Семейство графов Леви
Проблемы
Проблема поиска самый длинный путь или цикл, который является индуцированный подграф данного графа гиперкуба известен как змея в коробке проблема.
Гипотеза Шиманского касается пригодности гиперкуба в качестве топология сети для связи. В нем говорится, что независимо от того, как выбрать перестановка соединяя каждую вершину гиперкуба с другой вершиной, с которой она должна быть связана, всегда есть способ соединить эти пары вершин с помощью пути которые не имеют общего направленного края.[9]
Смотрите также
- граф де Брейна
- Циклы, связанные кубом
- Куб Фибоначчи
- Граф свернутого куба
- График Франкла – Рёдля
- График куба, разделенного на два
- Топология межсетевого взаимодействия Hypercube
Примечания
- ^ Уоткинс, Джон Дж. (2004), Через доску: математика задач на шахматной доске, Princeton University Press, стр. 68, ISBN 978-0-691-15498-5.
- ^ Миллс, У. Х. (1963), "Некоторые полные циклы на п-куб », Труды Американского математического общества, Американское математическое общество, 14 (4): 640–643, Дои:10.2307/2034292, JSTOR 2034292.
- ^ Финк, Дж. (2007), "Совершенное паросочетание распространяется на гамильтоновы циклы в гиперкубах", Журнал комбинаторной теории, серия B, 97 (6): 1074–1076, Дои:10.1016 / j.jctb.2007.02.007.
- ^ Раски, Ф. и Сэвидж, К. Сочетания распространяются на гамильтоновы циклы в гиперкубах на открытом проблемном саду. 2007 г.
- ^ Рингель, Г. (1955 г.), "Убер дрей комбинаторные проблемы ам" п-dimensionalen Wiirfel und Wiirfelgitter ", Abh. Математика. Сем. Univ. Гамбург, 20: 10–19, МИСТЕР 0949280
- ^ а б Харари, Фрэнк; Hayes, John P .; Ву, Хорнг-Джих (1988), «Обзор теории графов гиперкубов» (PDF), Компьютеры и математика с приложениями, 15 (4): 277–289, Дои:10.1016/0898-1221(88)90213-1, МИСТЕР 0949280.
- ^ Оптимальные нумерации и изопериметрические задачи на графах, Л.Х. Харпер, Журнал комбинаторной теории, 1, 385–393, Дои:10.1016 / S0021-9800 (66) 80059-5
- ^ Ройхман Ю. (2000), "Об ахроматическом числе гиперкубов", Журнал комбинаторной теории, серия B, 79 (2): 177–182, Дои:10.1006 / jctb.2000.1955.
- ^ Шимански, Тед Х. (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.