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

В теории графов частичный куб — это граф , который является изометрическим подграфом гиперкуба . ^[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), обозначается как . Два ребра и определяются как находящиеся в отношении , записанном , если . Это отношение рефлексивно и симметрично , но в общем случае оно не транзитивно . $\Тета$ $e=\{x,y\}$ $f=\{u,v\}$ $\Тета$ $е{\mathrel {\Theta }}f$ $d(x,u)+d(y,v)\not =d(x,v)+d(y,u)$

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

Признание

Частичные кубы могут быть распознаны, и маркировка Хэмминга построена за время, где - число вершин в графе. ^[9] При наличии частичного куба легко построить классы эквивалентности отношения Джоковича-Винклера, выполнив поиск в ширину из каждой вершины за общее время ; алгоритм распознавания во времени ускоряет этот процесс, используя параллелизм на уровне битов для выполнения нескольких поисков в ширину за один проход по графу, а затем применяет отдельный алгоритм для проверки того, что результатом этого вычисления является допустимая частичная маркировка куба. $O(n^{2})$ $n$ $O(нм)$ $O(n^{2})$

Измерение

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

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

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

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

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

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

Примечания

^ Овчинников (2011), Определение 5.1, с. 127.
^ Овчинников (2011), стр. 174.
^ Овчинников (2011), Раздел 5.11, «Медианные графики», стр. 163–165.
^ Овчинников (2011), Глава 7, «Гиперплоскостные конфигурации», стр. 207–235.
^ Эппштейн (2006).
^ Овчинников (2011), Раздел 5.7, «Декартовы произведения частичных кубов», стр. 144–145.
^ Боду, Гравье и Меслем (2008).
^ Винклер (1984), Теорема 4. См. также Овчинников (2011), Определение 2.13, стр. 29, и Теорема 5.19, стр. 136.
^ Эппштейн (2008).
^ Овчинников (2011), Раздел 5.6, «Изометрическое измерение», стр. 142–144, и Раздел 5.10, «Уникальность изометрических вложений», стр. 157–162.
^ Хэдлок и Хоффман (1978); Эппштейн (2005); Овчинников (2011), Глава 6, «Решеточные вложения», стр. 183–205.
^ Эппштейн (2009); Кабельо, Эппштейн и Клавжар (2011).
^ Клавжар, Гутман и Мохар (1995), предложения 2.1 и 3.1; Имрих и Клавжар (2000), с. 60; Овчинников (2011), раздел 5.12, «Средняя длина и индекс Винера», стр. 165–168.
^ Эппштейн (2009).

Ссылки

Боду, Лоран; Гравье, Сильвен; Меслем, Кахина (2008), «Изометрические вложения подразделенных полных графов в гиперкуб» (PDF) , SIAM Journal on Discrete Mathematics , 22 (3): 1226–1238, doi :10.1137/070681909, MR 2424849, S2CID 6332951
Кабельо, С.; Эппштейн, Д .; Клавжар, С. (2011), «Размерность графа Фибоначчи», Электронный журнал комбинаторики , 18 (1), P55, arXiv : 0903.2507 , Bibcode : 2009arXiv0903.2507C, doi : 10.37236/542, S2CID 9363180.
Джокович, Драгомир Ж. (1973), «Подграфы гиперкубов, сохраняющие расстояние», Журнал комбинаторной теории , Серия B, 14 (3): 263–267, doi : 10.1016/0095-8956(73)90010-5 , MR 0314669.
Эппштейн, Дэвид (2005), «Размерность решетки графа», European Journal of Combinatorics , 26 (6): 585–592, arXiv : cs.DS/0402028 , doi : 10.1016/j.ejc.2004.05.001, S2CID 7482443.
Эппштейн, Дэвид (2006), «Кубические частичные кубы из симплициальных расположений», Электронный журнал комбинаторики , 13 (1), R79, arXiv : math.CO/0510263 , doi : 10.37236/1105, S2CID 8608953.
Эппштейн, Дэвид (2008), «Распознавание частичных кубов за квадратичное время», Труды 19-го симпозиума ACM-SIAM по дискретным алгоритмам , стр. 1258–1266, arXiv : 0705.1025 , Bibcode : 2007arXiv0705.1025E.
Эппштейн, Дэвид (2009), «Изометрические ромбовидные подграфы», Труды 16-го Международного симпозиума по рисованию графов, Ираклион, Крит, 2008 г. , Lecture Notes in Computer Science, т. 5417, Springer-Verlag, стр. 384–389, arXiv : 0807.2218 , doi : 10.1007/978-3-642-00219-9_37, S2CID 14066610.
Фалмань, Ж.-К. ; Дуаньон, Ж.-П. (1997), "Стохастическая эволюция рациональности" (PDF) , Теория и решения , 43 (2): 107–138, doi :10.1023/A:1004981430688, S2CID 117983644.
Фирсов, В.В. (1965), «Об изометрической вложенности графа в булев куб», Кибернетика , 1 : 112–113, doi :10.1007/bf01074705, S2CID 121572742. Цитируется Овчинниковым (2011).
Хэдлок, Ф.; Хоффман, Ф. (1978), «Манхэттенские деревья», Utilitas Mathematica , 13 : 55–67. Цитируется Овчинниковым (2011).
Имрих, Вильфрид; Клавжар, Сэнди (2000), Графы продуктов: структура и распознавание , серия Wiley-Interscience по дискретной математике и оптимизации, Нью-Йорк: John Wiley & Sons, ISBN 978-0-471-37039-0, г-н 1788124.
Клавжар, Санди; Гутман, Иван; Мохар, Боян (1995), «Маркировка бензоидных систем, отражающая соотношения вершин и расстояний» (PDF) , Журнал химической информации и компьютерных наук , 35 (3): 590–593, doi :10.1021/ci00025a030.
Кузьмин, В.; Овчинников, С. (1975), «Геометрия пространств предпочтений I», Автоматика и телемеханика , 36 : 2059–2063. Цитируется Овчинниковым (2011).
Овчинников, Сергей (2011), Графы и кубы , Universitext, Springer. См. особенно главу 5 «Частичные кубы», стр. 127–181.
Винклер, Питер М. (1984), «Изометрическое вложение в произведения полных графов», Дискретная прикладная математика , 7 (2): 221–225, doi : 10.1016/0166-218X(84)90069-6 , MR 0727925.