Граф, разделенный пополам

Граф, разделенный пополам
Граф, разделенный пополам
	Граф куба, разделенный пополам ⁠1/2⁠ Вопрос 3
Вершины	2 н –1
Края	н ( н – 1)2 н –3
Автоморфизмы	n ! 2 n –1 , для n > 4 ; n ! 2 n , для n = 4 ; (2 n –1 )! , для n < 4
Характеристики	Симметричный ; Расстояние регулярное
Обозначение	⁠1/2⁠ Q н
	Таблица графиков и параметров

Граф вершин и ребер полугиперкуба

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

Два показанных графа представляют собой симметричные D _n и B _n проекции многоугольников Петри (2( n − 1) и n диэдральная симметрия ) соответствующего многогранника, который может включать перекрывающиеся ребра и вершины.

н	Многогранник	Вершины	Края
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

Ссылки

^ А. Э. Брауэр , А. М. Коэн и А. Ноймайер (1989), Регулярные графы расстояний . Берлин, Нью-Йорк: Springer-Verlag, с. 265. ISBN 3-540-50619-5 , ISBN 0-387-50619-5.
^ Индик, Петр ; Матоушек, Йиржи (2010), «Вложения конечных метрических пространств с малыми искажениями», в Goodman, Jacob E .; O'Rourke, Joseph (ред.), Handbook of Discrete and Computational Geometry (2-е изд.), CRC Press, стр. 179, ISBN 9781420035315.
^ Чихара, Лора; Стэнтон, Деннис (1986), «Схемы ассоциации и квадратичные преобразования для ортогональных многочленов», Графы и комбинаторика , 2 (2): 101–112, doi :10.1007/BF01788084, MR 0932118 .
^ Деза, М.; Шпекторов, С. (1996), «Распознавание l ₁ -графов со сложностью O ( nm ), или футбол в гиперкубе», European Journal of Combinatorics , 17 (2–3): 279–289, doi : 10.1006/eujc.1996.0024 , MR 1379378.
^ Богстад, Билл; Коуэн, Ленор Дж. (2004), «Отличительное число гиперкуба», Дискретная математика , 283 (1–3): 29–35, doi : 10.1016/j.disc.2003.11.018 , MR 2061481.

Внешние ссылки

Вайсштейн, Эрик В. «Граф, разделенный пополам». MathWorld .

[Brouwer-1] А. Э. Брауэр , А. М. Коэн и А. Ноймайер (1989), Регулярные графы расстояний . Берлин, Нью-Йорк: Springer-Verlag, с. 265. ISBN 3-540-50619-5 , ISBN 0-387-50619-5.

[2] Индик, Петр ; Матоушек, Йиржи (2010), «Вложения конечных метрических пространств с малыми искажениями», в Goodman, Jacob E .; O'Rourke, Joseph (ред.), Handbook of Discrete and Computational Geometry (2-е изд.), CRC Press, стр. 179, ISBN 9781420035315.

[3] Чихара, Лора; Стэнтон, Деннис (1986), «Схемы ассоциации и квадратичные преобразования для ортогональных многочленов», Графы и комбинаторика , 2 (2): 101–112, doi :10.1007/BF01788084, MR 0932118 .

[4] Деза, М.; Шпекторов, С. (1996), «Распознавание l ₁ -графов со сложностью O ( nm ), или футбол в гиперкубе», European Journal of Combinatorics , 17 (2–3): 279–289, doi : 10.1006/eujc.1996.0024 , MR 1379378.

[5] Богстад, Билл; Коуэн, Ленор Дж. (2004), «Отличительное число гиперкуба», Дискретная математика , 283 (1–3): 29–35, doi : 10.1016/j.disc.2003.11.018 , MR 2061481.

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