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

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

История

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

Примеры

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

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

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

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

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

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

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

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

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

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

Размерность

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

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

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья Как процитировано в Шаблон:Harv.
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга. См. главу 5, «Partial Cubes», стр. 127–181.
• Шаблон:Статья