Граф гиперкуба
-
Определение и свойства гиперкуба
- Гиперкуб — это граф, вершины которого соответствуют подмножествам из n элементов, а ребра соединяют вершины, если их подмножества отличаются ровно одним элементом.
- Граф гиперкуба Qn имеет 2n вершин и 2n-1 ребер, является правильным графом с n ребрами, касающимися каждой вершины.
- Гиперкуб может быть построен путем создания вершин для каждого подмножества множества из n элементов или путем создания вершин для каждого n-значного двоичного числа.
-
Построение и рекурсия
- Гиперкуб Qn может быть построен путем объединения двух копий Qn-1 с помощью идеального соответствия.
- Рекурсивный алгоритм для матрицы смежности гиперкуба основан на использовании продукта Kronecker.
-
Примеры и свойства
- Графы гиперкуба Q0, Q1, Q2, Q3 и Q4 имеют различные структуры и свойства.
- Гиперкубы являются двудольными, гамильтоновыми и имеют другие интересные свойства, включая диаграмму Хассе, медианный график и бипанциклические циклы.
-
Проблемы и гипотезы
- Задача о змее в коробке касается поиска самого длинного пути или цикла в гиперкубе.
- Гипотеза Шиманского касается возможности использования гиперкуба в качестве сетевой топологии для коммуникаций.
-
Связанные понятия
- В статье упоминаются другие связанные с кубом циклы, включая куб Фибоначчи и свернутый кубический график.