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

В теории графов части́чный куб — это подграф гиперкуба, сохраняющий расстояния (в терминах графов) — расстояние между любыми двумя вершинами подграфа то же самое, что и в исходном графе. Эквивалентно, частичный куб — это граф, вершины которого можно пометить битовыми строками одинаковой длины, так что расстояние между двумя вершинами в графе равно расстоянию Хэмминга между этими двумя метками. Такая разметка называется разметкой Хэмминга и она представляет изометричное вложение частичного куба в гиперкуб.

История

В. Фирсов первым исследовал изометрические вложения графов в гиперкубы. Графы, позволяющие такие вложения, были описаны Д. Джоковичем и П. Винклером и позднее получили название «частичные кубы». Самостоятельную линию исследований тех же структур в терминологии семейств множеств, а не разметки гиперкубов, развивали, среди прочих, В. Кузьмин и С. Овчинников, а также Фалмагне и Дойнон.

Примеры

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

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

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

Более сложные примеры:

• Рассмотрим граф, вершины которого состоят из всех возможных битовых строк длиной 2n + 1, которые имеют либо n, либо n + 1 ненулевых бит. Две вершины этого графа смежны, если их метки отличаются на единственный бит. Такая разметка определяет вложение этого графа в гиперкуб (граф всех битовых строк заданной длины с тем же условием смежности). Результирующий граф является двудольным кнезеровским графом. Граф, полученный таким образом с n = 2, имеет 20 вершин и 30 рёбер и называется графом Дезарга.
• Все медианные графы являются частичными кубами. Деревья и гиперкубы являются частными случаями медианных графов. Поскольку медианные графы включают рамочные графы, симплекс-графы и кубы Фибоначчи, а также покрывающие графы конечных дистрибутивных решёток, все они являются частичными кубами.
• Графы, двойственные конфигурациям прямых на евклидовой плоскости, являются частичными кубами. В более общем виде, для любой конфигурации гиперплоскостей в евклидовом пространстве любой размерности граф, имеющий вершину для каждой ячейки конфигурации и ребро для любых двух смежных ячеек, является частичным кубом.
• Частичный куб, в котором каждая вершина имеет в точности три соседа, известен как кубический частичный куб. Хотя некоторые бесконечные семейства кубических частичных кубов известны, вместе с другими спорадическими примерами, единственный известный кубический частичный куб, не являющийся планарным, — это граф Дезарга.
• Лежащий в основе любого антиматроида граф, имеющий вершину для каждого множества в антиматроиде и ребро для любых двух множеств, отличающихся единственным элементом, всегда является частичным кубом.
• Прямое произведение любого конечного множества частичных кубов является другим частичным кубом.

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

Множество теорем о частичных кубах опираются прямо или косвенно на некоторое бинарное отношение, определённое на рёбрах графа. Это отношение, впервые описанное Джоковичем, обозначается $\Theta$. Винклер дал эквивалентное определение соотношения в терминах расстояния. Два ребра $e=\{x,y\}$ и $f=\{u,v\}$ находятся в отношении $\Theta$ (записывается $e{\mathrel {\Theta }}f$), если $d(x,u)+d(y,v)\not =d(x,v)+d(y,u)$. Это отношение является рефлексивным и симметричным, но, в общем случае, не транзитивным.

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

Распознавание

Частичные кубы могут быть распознаны и разметка Хэмминга для них построена за время $O(n^{2})$, где $n$ — число вершин графа. Если задан частичный куб, можно напрямую построить классы эквивалентности отношения Джоковича – Винклера используя поиск в ширину от каждой вершины за общее время $O(nm)$. Алгоритм распознавания со временем работы $O(n^{2})$ ускоряет поиск, используя bit-level parallelism для осуществления множественных поисков в ширину за один проход графа, затем используется отдельный алгоритм для проверки, что в результате получилась правильная разметка частичного куба.

Размерность

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

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

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

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

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

Литература

• S. Cabello, D. Eppstein, S. Klavžar. The Fibonacci dimension of a graph // Electronic Journal of Combinatorics. — 2011. — Т. 18, вып. 1. — arXiv:0903.2507.
• D. Ž. Djoković. Distance-preserving subgraphs of hypercubes // Journal of Combinatorial Theory. — 1973. — Т. 14, вып. 3. — С. 263–267. — doi:10.1016/0095-8956(73)90010-5.
• David Eppstein. The lattice dimension of a graph // European Journal of Combinatorics. — 2005. — Т. 26, вып. 6. — С. 585–592. — doi:10.1016/j.ejc.2004.05.001. — arXiv:cs.DS/0402028.
• David Eppstein. Cubic partial cubes from simplicial arrangements // Electronic Journal of Combinatorics. — 2006. — Т. 13, вып. 1. — arXiv:math.CO/0510263.
• David Eppstein. Proc. 19th ACM-SIAM Symposium on Discrete Algorithms. — 2008. — С. 1258–1266.
• David Eppstein. Proc. 16th International Symposium on Graph Drawing, Heraklion, Crete, 2008. — Springer-Verlag, 2009. — Т. 5417. — С. 384–389. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-00219-9_37.
• J.-C. Falmagne, J.-P. Doignon. Stochastic evolution of rationality // Theory and Decision. — 1997. — Т. 43. — С. 107–138. — doi:10.1023/A:1004981430688.
• Фирсов В. В. Об изометрическом вложении графа в булевский куб // Кибернетика. — 1965. — Вып. 6. — С. 95-96.
• F. Hadlock, F. Hoffman. Manhattan trees // Utilitas Mathematica. — 1978. — Т. 13. — С. 55–67. Как процитировано в (Ovchinnikov 2011).
• Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — John Wiley & Sons, 2000. — (Wiley-Interscience Series in Discrete Mathematics and Optimization). — ISBN 978-0-471-37039-0.
• Sandi Klavžar, Ivan Gutman, Bojan Mohar. Labeling of benzenoid systems which reflects the vertex-distance relations // Journal of Chemical Information and Computer Sciences. — 1995. — Т. 35, вып. 3. — С. 590–593. — doi:10.1021/ci00025a030.
• В. Б. Кузьмин, С. В. Овчинников. Геометрия пространств предпочтений. I // Автоматика и телемеханика. — 1975. — Вып. 12. — С. 140-145.
• Sergei Ovchinnikov. Graphs and Cubes. — 2011.. См. главу 5, «Partial Cubes», стр. 127–181.
• Peter M. Winkler. Isometric embedding in products of complete graphs // Discrete Applied Mathematics. — 1984. — Т. 7, вып. 2. — С. 221–225. — doi:10.1016/0166-218X(84)90069-6.