График куба, уменьшенного вдвое - Halved cube graph - Wikipedia

График куба, уменьшенного вдвое
График половинного куба ${\displaystyle {\tfrac {1}{2}}Q_{3}}$
Вершины	2п-1
Края	п(п-1)2п-3
Автоморфизмы	п! 2п-1, за п>4 п! 2п, за п=4 (2п-1)!, за п<4 [1]
Характеристики	Симметричный Расстояние регулярное
Обозначение	${\displaystyle {\tfrac {1}{2}}Q_{n}}$
Таблица графиков и параметров

Построение двух полукубов (правильных тетраэдров, образующих Stella Octangula ) из одного куба. Разделенный пополам граф куба третьего порядка - это граф вершин и ребер одного полукуба. Разделенный пополам граф куба четвертого порядка включает в себя все вершины и ребра куба, а также все ребра двух полукубов.

В теория графов, то вдвое кубический граф или же график половинного куба порядка п график полугиперкуб, образованный соединением пар вершин на расстоянии ровно два друг от друга в граф гиперкуба. То есть это полуквадрат гиперкуба. Этот шаблон связности создает два изоморфных графа, отсоединенных друг от друга, каждый из которых представляет собой разрезанный пополам кубический граф.

Эквивалентные конструкции

Построение деленного пополам графа куба можно переформулировать в терминах двоичные числа. Вершины гиперкуба могут быть помечены двоичными числами таким образом, чтобы две вершины были смежными именно тогда, когда они отличаются одним битом. Демикуб может быть построен из гиперкуба как выпуклый корпус подмножества двоичных чисел с четным числом ненулевых битов ( злые числа ), а его ребра соединяют пары чисел, Расстояние Хэмминга ровно два.^[2]

Также возможно построить разрезанный пополам граф куба из графа гиперкуба более низкого порядка, не взяв подмножество вершин:

${\displaystyle {\frac {1}{2}}Q_{n}=Q_{n-1}^{2}}$

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

Примеры

График половинного куба ${\displaystyle {\tfrac {1}{2}}Q_{3}}$ порядка 3 - это полный график K₄, график тетраэдр. График половинного куба ${\displaystyle {\tfrac {1}{2}}Q_{4}}$ порядка 4 K_2,2,2,2, график четырехмерный правильный многогранник, то 16 ячеек. График половинного куба ${\displaystyle {\tfrac {1}{2}}Q_{5}}$ пятого порядка иногда называют Граф Клебша, и является дополнением свернутый куб граф пятого порядка, который чаще называют графом Клебша. Он существует в 5-мерном равномерный 5-многогранник, то 5-полукуб.

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

Потому что это двудольная половина из дистанционно регулярный граф, разрезанный пополам куб-граф сам дистанционно регулярен.^[3] И поскольку он содержит гиперкуб как охватывающий подграф, он наследует от гиперкуба все свойства монотонного графа, такие как свойство содержать Гамильтонов цикл.

Как и в случае с графами гиперкуба, и их изометрический (сохраняющие расстояние) подграфы частичные кубики, половину кубического графа можно изометрически встроить в реальное векторное пространство с Манхэттенская метрика (L₁ функция расстояния). То же самое верно для изометрических подграфов половинчатых кубических графов, которые могут быть распознаны в полиномиальное время; это формирует ключевую подпрограмму для алгоритма, который проверяет, можно ли изометрически встроить данный граф в манхэттенскую метрику.^[4]

Для каждого разрезанного пополам кубического графа пятого или более порядка можно (неправильно) раскрасить вершины в два цвета таким образом, чтобы полученный цветной граф не имел нетривиальных симметрий. Для графов третьего и четвертого порядков необходимо четыре цвета, чтобы устранить все симметрии.^[5]

Последовательность

Два показанных графика симметричны D_п и B_п Многоугольник Петри проекции (2 (п - 1) и п двугранная симметрия ) связанного многогранника, который может включать перекрывающиеся ребра и вершины.

п	Многогранник	График	Вершины	Края
2	Отрезок		2	–
3	тетраэдр		4	6
4	16 ячеек		8	24
5	5-полукруглый		16	80
6	6-полукуб		32	240
7	7-полукуб		64	672
8	8-полукруглый		128	1792
9	9-полукуб		256	4608
10	10-полукуб		512	11520

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

1. А.Э. Брауэр, ЯВЛЯЮСЬ. Коэн и А. Ноймайер (1989), Регулярные графики расстояний. Берлин, Нью-Йорк: Springer-Verlag, стр. 265. ISBN  3-540-50619-5, ISBN  0-387-50619-5
2. Индик, Петр; Матушек, Иржи (2010), "Вложения конечных метрических пространств с малыми искажениями", в Гудман, Джейкоб Э.; О'Рурк, Джозеф (ред.), Справочник по дискретной и вычислительной геометрии (2-е изд.), CRC Press, стр. 179, г. ISBN  9781420035315.
3. Чихара, Лаура; Стэнтон, Деннис (1986), "Схемы ассоциации и квадратичные преобразования для ортогональных многочленов", Графики и комбинаторика, 2 (2): 101–112, Дои:10.1007 / BF01788084, МИСТЕР  0932118.
4. Деза, М.; Шпекторов, С. (1996), "Признание л₁-графы со сложностью О(нм), или футбол в гиперкубе », Европейский журнал комбинаторики, 17 (2–3): 279–289, Дои:10.1006 / eujc.1996.0024, МИСТЕР  1379378.
5. Богстад, Билл; Коуэн, Ленор Дж. (2004), «Отличительное число гиперкуба», Дискретная математика, 283 (1–3): 29–35, Дои:10.1016 / j.disc.2003.11.018, МИСТЕР  2061481.

внешняя ссылка

• Вайсштейн, Эрик В. «Разделенный пополам кубический график». MathWorld.