Jump to content

Частичный куб

В теории графов частичный куб — ​​это граф который является изометрическим подграфом гиперкуба , . [1] Другими словами, частичный куб можно отождествить с подграфом гиперкуба таким образом, чтобы расстояние между любыми двумя вершинами в частичном кубе было таким же, как расстояние между этими вершинами в гиперкубе. Эквивалентно, частичный куб — ​​это граф, вершины которого могут быть помечены битовыми строками одинаковой длины таким образом, что расстояние между двумя вершинами в графе равно расстоянию Хэмминга между их метками. Такая разметка называется разметкой Хэмминга ; он представляет собой изометрическое вложение частичного куба в гиперкуб.

Фирсов (1965) первым изучил изометрические вложения графов в гиперкубы. Графы, допускающие такие вложения, были охарактеризованы Джоковичем (1973) и Винклером (1984) и позже были названы частичными кубами. Отдельному направлению исследований тех же структур, в терминологии семейств множеств , а не гиперкубических разметок графов, следовали, среди прочих, Кузьмин и Овчинников (1975) и Фальмань и Дуаньон (1997) . [2]

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

Каждое дерево представляет собой частичный куб. Действительно, предположим, что дерево T имеет m ребер и пронумеруем эти ребра (произвольно) от 0 до m – 1 . Выберите корневую вершину r для дерева произвольно и пометьте каждую вершину v строкой из m битов, которая имеет 1 в позиции i всякий раз, когда ребро i лежит на пути от r до v в T . Например, у самого r будет метка, состоящая из нулевых битов, у его соседей будут метки с одним 1-битом и т. д. Тогда расстояние Хэмминга между любыми двумя метками — это расстояние между двумя вершинами в дереве, так что это разметка показывает, что T — частичный куб.

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

Более сложные примеры включают следующее:

  • Рассмотрим граф, метки вершин которого состоят из всех возможных (2 n + 1) -значных цепочек битов, имеющих либо n , либо n + 1 ненулевых бит, где две вершины являются смежными, если их метки отличаются на один бит. Эта маркировка определяет встраивание этих графов в гиперкуб (граф всех битовых строк заданной длины с одинаковым условием смежности), который оказывается сохраняющим расстояние. Полученный граф представляет собой двудольный граф Кнезера ; образованный таким образом граф с n = 2 имеет 20 вершин и 30 ребер и называется графом Дезарга .
  • Все медианные графы представляют собой частичные кубы. [3] Деревья и графы гиперкубов являются примерами медианных графов. Поскольку медианные графы включают в себя квадратные графы , симплекс-графы и кубы Фибоначчи , а также графы покрытия конечных дистрибутивных решеток , все они являются частичными кубами.
  • Плоский двойственный граф расположения прямых на евклидовой плоскости представляет собой частичный куб. В более общем смысле, для любого расположения гиперплоскостей в евклидовом пространстве любого числа измерений граф, имеющий вершину для каждой ячейки расположения и ребро для каждых двух соседних ячеек, является частичным кубом. [4]
  • Частичный куб, в котором каждая вершина имеет ровно три соседа, называется кубическим частичным кубом. Хотя известно несколько бесконечных семейств кубических частичных кубов, а также множество других спорадических примеров, единственным известным кубическим частичным кубом, который не является плоским графом, является граф Дезарга. [5]
  • Базовый граф любого антиматроида , имеющий вершину для каждого множества в антиматроиде и ребро для каждых двух наборов, отличающихся одним элементом, всегда является частичным кубом.
  • Декартово произведение любого конечного набора частичных кубов является еще одним частичным кубом. [6]
  • Подразделение частичным кубом тогда и только тогда, когда либо каждое полное ребро графа разделено на путь из является полного графа двух ребер, либо существует одна полная вершина графа, все инцидентные ребра которой не разделены, а все неинцидентные ребра разделены. на пути четной длины. [7]

Отношение Джоковича – Винклера

[ редактировать ]

Многие теоремы о частичных кубах прямо или косвенно основаны на определенном бинарном отношении, определенном на ребрах графа. Это соотношение, впервые описанное Джоковичем (1973) и получившее эквивалентное определение в терминах расстояний Винклером (1984) , обозначается как . Два края и определяются как находящиеся в отношении , написано , если . Это отношение рефлексивно и симметрично , но, вообще говоря, не транзитивно .

Винклер показал, что связный граф является частичным кубом тогда и только тогда, когда он двудольный и выполняется соотношение является транзитивным. [8] В этом случае он образует отношение эквивалентности , и каждый класс эквивалентности отделяет два связных подграфа графа друг от друга. Маркировку Хэмминга можно получить, присвоив один бит каждой метки каждому из классов эквивалентности отношения Джоковича – Винклера; в одном из двух связных подграфов, разделенных классом эквивалентности ребер, все вершины имеют 0 в этой позиции своих меток, а в другом связном подграфе все вершины имеют 1 в той же позиции.

Признание

[ редактировать ]

Частичные кубы можно распознать и построить разметку Хэмминга в время, где — количество вершин в графе. [9] Учитывая частичный куб, легко построить классы эквивалентности отношения Джоковича – Винклера, выполняя поиск в ширину из каждой вершины за общее время. ; тот Алгоритм распознавания по времени ускоряет это, используя параллелизм на уровне битов для выполнения нескольких поисков в ширину за один проход по графу, а затем применяет отдельный алгоритм для проверки того, что результат этого вычисления является допустимой частичной маркировкой куба.

Измерение

[ редактировать ]

Изометрическая размерность частичного куба - это минимальная размерность гиперкуба, в которую он может быть изометрически вложен, и равна количеству классов эквивалентности отношения Джоковича-Винклера. Например, изометрический размер -вершинное дерево — это количество его ребер, . Вложение частичного куба в гиперкуб этой размерности однозначно с точностью до симметрии гиперкуба. [10]

Каждый гиперкуб и, следовательно, каждый частичный куб можно изометрически вложить в целочисленную решетку . Размерность решетки графа — это минимальная размерность целочисленной решетки, в которую граф может быть изометрически вложен. Размер решетки может быть значительно меньше изометрического размера; например, для дерева это половина количества листьев в дереве (округляется до ближайшего целого числа). Размерность решетки любого графа и вложение решетки минимальной размерности могут быть найдены за полиномиальное время с помощью алгоритма, основанного на максимальном сопоставлении во вспомогательном графе. [11]

Также были определены другие типы размерностей частичных кубов на основе вложений в более специализированные структуры. [12]

Приложение к теории химических графов

[ редактировать ]

Изометрические вложения графов в гиперкубы имеют важное применение в химической теории графов . Бензеноидный граф — это граф, состоящий из всех вершин и ребер, лежащих на и внутри цикла в гексагональной решетке . Такие графики представляют собой молекулярные графики бензоидных углеводородов , большого класса органических молекул. Каждый такой граф является частичным кубом. Разметку Хэмминга такого графа можно использовать для вычисления индекса Винера соответствующей молекулы, который затем можно использовать для предсказания некоторых ее химических свойств. [13]

Другая молекулярная структура, образованная из углерода, алмазный куб , также образует частичные кубические графы. [14]

Примечания

[ редактировать ]
  1. ^ Ovchinnikov (2011) , Definition 5.1, p. 127.
  2. ^ Ovchinnikov (2011) , p. 174.
  3. ^ Овчинников (2011) , Раздел 5.11, «Медианные графики», стр. 163–165.
  4. ^ Овчинников (2011) , Глава 7, «Устройства гиперплоскости», стр. 207–235.
  5. ^ Эппштейн (2006) .
  6. ^ Овчинников (2011) , Раздел 5.7, «Декартовы произведения частичных кубов», стр. 144–145.
  7. ^ Боду, Гравье и Меслем (2008) .
  8. ^ Винклер (1984) , Теорема 4. См. также Овчинников (2011) , Определение 2.13, стр. 29 и Теорему 5.19, стр. 29. 136.
  9. ^ Эппштейн (2008) .
  10. ^ Овчинников (2011) , Раздел 5.6, «Изометрическая размерность», стр. 142–144, и Раздел 5.10, «Уникальность изометрических вложений», стр. 157–162.
  11. ^ Хэдлок и Хоффман (1978) ; Эппштейн (2005) ; Овчинников (2011) , Глава 6, «Решеточные вложения», стр. 183–205.
  12. ^ Эппштейн (2009) ; Кабельо, Эппштейн и Клавжар (2011) .
  13. ^ Клавжар, Гутман и Мохар (1995) , предложения 2.1 и 3.1; Имрих и Клавжар (2000) , с. 60; Овчинников (2011) , раздел 5.12, «Средняя длина и индекс Винера», стр. 165–168.
  14. ^ Эппштейн (2009) .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: adb53f167bd1e89479a00b797dfd1528__1711783380
URL1:https://arc.ask3.ru/arc/aa/ad/28/adb53f167bd1e89479a00b797dfd1528.html
Заголовок, (Title) документа по адресу, URL1:
Partial cube - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)