В теории графов половинный кубический граф или полукубический граф размерности n — это граф полугиперкуба , образованный соединением пар вершин на расстоянии ровно двух друг от друга в гиперкубическом графе . То есть, это полуквадрат гиперкуба. Этот шаблон связности создает два изоморфных графа , отсоединенных друг от друга, каждый из которых является половинным кубическим графом.
Построение графа половинчатого куба можно переформулировать в терминах двоичных чисел . Вершины гиперкуба можно пометить двоичными числами таким образом, что две вершины являются смежными, когда они отличаются в одном бите. Полукуб может быть построен из гиперкуба как выпуклая оболочка подмножества двоичных чисел с четным числом ненулевых битов ( злые числа ), и его ребра соединяют пары чисел, расстояние Хэмминга которых равно ровно двум. [2]
Также возможно построить половинный кубический граф из гиперкубического графа меньшей размерности, не беря подмножество вершин:
где верхний индекс 2 обозначает квадрат гиперкубического графа Q n − 1 , графа, образованного путем соединения пар вершин, расстояние между которыми в исходном графе не превышает двух. Например, половинный кубический граф размерности четыре может быть образован из обычного трехмерного куба путем сохранения ребер куба и добавления ребер, соединяющих пары вершин, которые находятся на противоположных углах одной и той же квадратной грани.
Граф половинного куба размерности 3 — это полный граф K 4 , граф тетраэдра . Граф половинного куба размерности 4 — это K 2,2,2,2 , граф четырехмерного правильного многогранника , 16-ячейника . Граф половинного куба размерности пять иногда называют графом Клебша , и он является дополнением графа сложенного куба размерности пять, который чаще называют графом Клебша. Он существует в 5-мерном однородном 5-многограннике , 5-демикубе .
Поскольку он является двудольной половиной дистанционно регулярного графа , половинный кубический граф сам по себе дистанционно регулярно. [3] И поскольку он содержит гиперкуб в качестве остовного подграфа , он наследует от гиперкуба все свойства монотонного графа, такие как свойство содержать гамильтонов цикл .
Как и в случае с графами гиперкуба и их изометрическими (сохраняющими расстояние) подграфами частичных кубов , половинный кубический граф может быть изометрически вложен в действительное векторное пространство с метрикой Манхэттена ( функция расстояния L 1 ). То же самое верно для изометрических подграфов половинных кубических графов, которые могут быть распознаны за полиномиальное время ; это формирует ключевую подпрограмму для алгоритма, который проверяет, может ли данный граф быть изометрически вложен в метрику Манхэттена. [4]
Для каждого половинчатого кубического графа размерности пять или более возможно (неправильно) раскрасить вершины двумя цветами таким образом, что полученный цветной граф не будет иметь нетривиальных симметрий. Для графов размерности три и четыре для устранения всех симметрий требуется четыре цвета. [5]
Два показанных графа представляют собой симметричные D n и B n проекции многоугольников Петри (2( n − 1) и n диэдральная симметрия ) соответствующего многогранника, который может включать перекрывающиеся ребра и вершины.
