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

Граф изометричен подграфу гиперкуба

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

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

Признание

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

Измерение

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

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

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

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

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

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

Примечания

1. Овчинников (2011), Определение 5.1, с. 127.
2. Овчинников (2011), с. 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).

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

• Боду, Лоран; Гравье, Сильвен; Меслем, Кахина (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), «Размерность решетки графа», Европейский журнал комбинаторики , 26 (6): 585–592, arXiv : cs.DS/0402028 , doi : 10.1016/j.ejc.2004.05.001, S2CID  7482443.
• Эппштейн, Дэвид (2006), «Кубические частичные кубы из симплициальных расположений», Electronic Journal of Combinatorics , 13 (1), R79, arXiv : math.CO/0510263 , doi : 10.37236/1105, S2CID  8608953.
• Эппштейн, Дэвид (2008), «Распознавание частичных кубов за квадратичное время», Proc. 19-й симпозиум ACM-SIAM по дискретным алгоритмам , стр. 1258–1266, arXiv : 0705.1025 , Bibcode : 2007arXiv0705.1025E.
• Эппштейн, Дэвид (2009), «Изометрические ромбовидные подграфы», Proc. 16-й Международный симпозиум по рисованию графов, Ираклион, Крит, 2008 г. , Конспекты лекций по информатике, том. 5417, Springer-Verlag, стр. 384–389, arXiv : 0807.2218 , doi : 10.1007/978-3-642-00219-9_37, S2CID  14066610.
• Фальмань, Ж.-К. ; Дуаньон, Ж.-П. (1997), «Стохастическая эволюция рациональности» (PDF) , Theory and Decision , 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) , Journal of Chemical Information and Computer Sciences , 35 (3): 590–593, doi : 10.1021/ci00025a030.
• Кузьмин В.; Овчинников С. (1975), «Геометрия пространств предпочтений I», Автоматика и телемеханика , 36 : 2059–2063.. Цитируется Овчинниковым (2011).
• Овчинников, Сергей (2011), Графы и кубы , Universitext, Springer. См. особенно главу 5, «Частичные кубы», стр. 127–181.
• Винклер, Питер М. (1984), «Изометрическое вложение в произведения полных графов», Discrete Applied Mathematics , 7 (2): 221–225, doi : 10.1016/0166-218X(84)90069-6 , MR  0727925.