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

Не путать с кубический граф.

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

История

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

Примеры

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

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

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

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

• Рассмотрим граф, метки вершин которого состоят из всех возможных (2п + 1)-цифровые битовые строки, которые имеют либо п или же п + 1 ненулевые биты, где две вершины смежны, если их метки отличаются на один бит. Эта разметка определяет вложение этих графов в гиперкуб (граф всех битовых цепочек заданной длины с одним и тем же условием смежности), который, оказывается, сохраняет расстояние. Полученный граф представляет собой двудольный граф Кнезера; сформированный таким образом граф с п = 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)}$. Это отношение рефлексивный и симметричный, но в целом это не так переходный.

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

Признание

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

Измерение

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

Каждый гиперкуб и, следовательно, каждый частичный куб можно изометрически вложить в целочисленная решетка. В размер решетки графа - это минимальная размерность целочисленной решетки, в которую граф может быть изометрически вложен. Размер решетки может быть значительно меньше изометрического размера; например, для дерева это половина количества листьев в дереве (округлено до ближайшего целого числа). Размерность решетки любого графа и вложение в решетку минимальной размерности можно найти в полиномиальное время по алгоритму, основанному на максимальное соответствие во вспомогательном графе.^[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, стр. 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 по дискретной математике, 22 (3): 1226–1238, Дои:10.1137/070681909, МИСТЕР  2424849
• Cabello, S .; Эппштейн, Д.; Клавжар, С. (2011), "Размерность Фибоначчи графа", Электронный журнал комбинаторики, 18 (1), P55, arXiv:0903.2507, Bibcode:2009arXiv0903.2507C.
• Джокович, Драгомир Ž. (1973), "Сохраняющие расстояние подграфы гиперкубов", Журнал комбинаторной теории, Серия B, 14 (3): 263–267, Дои:10.1016/0095-8956(73)90010-5, МИСТЕР  0314669.
• Эппштейн, Дэвид (2005), "Решетчатая размерность графа", Европейский журнал комбинаторики, 26 (6): 585–592, arXiv:cs.DS / 0402028, Дои:10.1016 / j.ejc.2004.05.001.
• Эппштейн, Дэвид (2006), «Кубические частичные кубы из симплициальных расположений», Электронный журнал комбинаторики, 13 (1), R79, arXiv:math.CO/0510263.
• Эппштейн, Дэвид (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, Дои:10.1007/978-3-642-00219-9_37.
• Фальмань, Ж.-К.; Дуаньон, Ж.-П. (1997), "Стохастическая эволюция рациональности", Теория и решение, 43: 107–138, Дои:10.1023 / А: 1004981430688.
• Фирсов, В.В. (1965), «Об изометрическом вложении графа в булев куб», Кибернетика, 1: 112–113, Дои:10.1007 / bf01074705. Как цитирует Овчинников (2011).
• Hadlock, F .; Хоффман Ф. (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, Дои:10.1021 / ci00025a030.
• Кузьмин, В .; Овчинников, С. (1975), "Геометрия пространств предпочтений I", Автоматизация и дистанционное управление, 36: 2059–2063. Как цитирует Овчинников (2011).
• Овчинников, Сергей (2011), Графики и кубики, Universitext, Springer. См. Особенно главу 5, «Частичные кубы», стр. 127–181.
• Винклер, Питер М. (1984), "Изометрические вложения в произведения полных графов", Дискретная прикладная математика, 7 (2): 221–225, Дои:10.1016 / 0166-218X (84) 90069-6, МИСТЕР  0727925.