Граф свернутого куба - Википедия - Folded cube graph

Граф свернутого куба
Clebsch hypercube.svg
Граф свернутого куба порядка 5 (т. Е. Граф Клебша ).
Вершины2п−1
Края2п−2п
Диаметрэтаж(п/2)
Хроматическое число2 (для четных п) или 4 (если нечетное).
ХарактеристикиРегулярный график
Гамильтониан
Дистанционно-транзитивный.
Таблица графиков и параметров

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

Строительство

Сложенный куб-граф порядка k (содержащий 2k − 1 вершины) могут быть сформированы путем добавления ребер между противоположными парами вершин в графе гиперкуба порядка k - 1. (В гиперкубе с 2п вершины, пара вершин противоположный если кратчайший путь между ними имеет длину п.) Он может быть образован из графа гиперкуба (также) порядка k, у которого вдвое больше вершин, идентификация вместе (или сжимая) каждую противоположную пару вершин.

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

Заказ-k граф свернутого куба k-обычный с 2k − 1 вершины и 2k − 2k края.

В хроматическое число порядка-k свернутый куб граф равен двум, когда k четный (то есть в данном случае график двудольный ) и четыре, когда k странно.[1] В странный обхват свернутого куба нечетного порядка есть kтак что для нечетных k больше трех, свернутые кубические графы предоставляют класс графы без треугольников с хроматическим числом четыре и произвольно большим нечетным обхватом. Как дистанционно регулярный граф со странным обхватом k и диаметр (k - 1) / 2, свернутые кубики нечетного порядка являются примерами обобщенные нечетные графы.[2]

Когда k странно, двусторонняя двойная обложка порядка-k сложенный куб - это порядок-k куб, из которого он образовался. Однако когда k четный, порядок-k куб это двойная крышка но не двудольный двойная крышка. В этом случае сложенный куб уже сам двудольный. Свернутые кубические графы наследуют от своих подграфов гиперкуба свойство иметь Гамильтонов цикл, а из гиперкубов, которые их дважды покрывают, свойство быть дистанционно-транзитивный граф.[3]

Когда k нечетный, порядок-k свернутый куб содержит в качестве подграфа a полное двоичное дерево с 2k - 1 узел. Однако когда k четное, это невозможно, потому что в этом случае свернутый куб представляет собой двудольный граф с равным числом вершин по обе стороны от двудольного дерева, что сильно отличается от отношения почти два к одному для двудольного разбиения полного двоичного дерева. .[4]

Примеры

Приложения

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

Смотрите также

Примечания

  1. ^ Годсил (2004) предоставляет доказательство и приписывает результат Насерасру и Тардифу.
  2. ^ Ван Дам и Хемерс (2010).
  3. ^ ван Бон (2007).
  4. ^ Чоудам и Нандини (2004).
  5. ^ Эль-Амави и Латифи (1991); Варваригос (1995).

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

  • Ван Бон, Джон (2007), "Конечные примитивные дистанционно-транзитивные графы", Европейский журнал комбинаторики, 28 (2): 517–532, Дои:10.1016 / j.ejc.2005.04.014.
  • Choudam, S.A .; Нандини, Р. Уша (2004), «Полные бинарные деревья в свернутых и расширенных кубах», Сети, 43 (4): 266–272, Дои:10.1002 / нетто.20002.
  • Ван Дам, Эдвин; Хемерс, Виллем Х. (2010), Нечетная характеристика обобщенных нечетных графов, CentER Discussion Paper Series No. 2010-47, SSRN  1596575.
  • Эль-Амави, А .; Латифи, С. (1991), "Свойства и характеристики свернутых гиперкубов", IEEE Trans. Параллельный дистриб. Syst., 2 (1): 31–42, Дои:10.1109/71.80187.
  • Годсил, Крис (2004), Интересные графики и их раскраски, CiteSeerX  10.1.1.91.6390.
  • Варваригос, Э. (1995), "Эффективные алгоритмы маршрутизации для сетей со свернутыми кубами", Proc. 14-й Int. Phoenix Conf. по компьютерам и связи, IEEE, стр. 143–151, Дои:10.1109 / PCCC.1995.472498.

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