Альтернативные подходы к описанию классов изоморфных графов | ПДМ. 2014. № 3 (25).

Альтернативные подходы к описанию классов изоморфных графов

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

Alternative approaches to the description of classes of isomorphic graphs.pdf Введение Графом G принято называть пару G = (V, E), где V - множество вершин, а E С V х V - множество рёбер, которые задают связи между вершинами. Поскольку основным предметом теории графов является абстрактная структура связей, то названия вершин V и рёбер E, а также их природа в общем случае не играют принципиальной роли. Данный факт находит своё отражение в определении понятия изоморфизма графов (подробнее см. [1-3]). Определение 1. Два графа G и H называются изоморфными, если существует биекция : V(G) ^ V(H), такая, что Vu,v Е V(G) (u,v) Е E(G) ^ (p(u),p(v)) Е E(H). Два изоморфных графа с точки зрения теории графов считаются неразличимыми, так как имеют одинаковую структуру связей между вершинами. Поскольку отношение изоморфизма разбивает множество4 всех графов на классы, то можно отождествить класс изоморфных графов [G] с уникальной структурой связей (рис. 1). G = (V,E) V = {a,b,c,d,e,/,g} Е = {(a,b), (a,c),(a,/), (a,g), (b, c),(b,d),(b, g), (c,d), (c,/), (d,/), (d, g), (/,g)} Рис. 1. Переход от обычного графа G к классу изоморфных [G] С понятием изоморфизма графов связано понятие инварианта - некоторого набора множеств, которые являются характеристиками структуры графа. У двух изоморфных графов значения инвариантов должны обязательно совпадать, но обратное в общем случае не верно. Поэтому дополнительно вводится понятие полного инварианта, который совпадает у графов тогда и только тогда, когда они изоморфны (подробнее об инвариантах см. [1, 3]). Если изоморфизм - отображает граф G сам на себя, то такое отображение называется автоморфизмом. Две вершины u,v Е V(G) графа G, которые могут быть переведены одна в другую некоторым автоморфизмом u = - (v), будем называть автоморфно эквивалентными (или симметричными) и обозначать u ~ v. При этом граф G можно изобразить так, что две вершины u ~ v переводятся друг в друга геометрической симметрией (на рис. 1 все вершины могут быть переведены друг в друга симметрия-ми, а значит, они все попарно автоморфно эквивалентны). Аналогично определяется отношение автоморфной эквивалентности и для рёбер графа: (u1,u2) ~ (v1,v2), если найдётся рёберный автоморфизм - : E(G) ^ E(G), такой, что (u1,u2) = -(v1 ,v2). Рёберный автоморфизм сохраняет вершины: рёбра e1 и e2 имеют общую вершину тогда и только тогда, когда общая вершина есть у рёбер -(e1) и -(e2). Отметим, что вопрос об автоморфизмах и симметриях интересен не только с теоретической точки зрения, но и с точки зрения приложений теории графов. О роли автоморфизмов графов в теории алгоритмов см. [5, 6]. Дополнительно к этому можно ознакомиться с химическими приложениями графов, а также их автоморфизмов в работах [7-9]. Отношения автоморфной эквивалентности разбивают множества вершин V(G) и рёбер E(G) любого графа G на классы симметрии v и (u, v) соответственно. Несмотря на широкий круг приложений для симметрий и автоморфизмов графов, непосредственно изучению классов симметрии вершин v посвящено относительно небольшое количество работ. В первую очередь стоит отметить работу М. Спэрроу [10] 1993 г., в которой рассматриваются быстрые алгоритмы поиска классов симметрии, а также диссертационную работу Р. Саутвелла [11] 2006 г. В данной работе мы демонстрируем, что каждому классу автоморфной эквивалентности вершин v произвольного графа G можно однозначным образом присвоить порядковый номер I(v) на основе полного числового инварианта графа - макси-кода. Аналогичное верно и для классов автоморфной эквивалентности рёбер (u, v): каждому классу можно поставить в соответствие уникальный порядковый номер I(u, v). Идентификаторы I(v) и I(u,v), в свою очередь, задействованы для построения полного инварианта I[G] - линейной нотации абстрактного графа [G]. В работе демонстрируется, что полный инвариант I [G] обладает всеми свойствами обычных графов G и, в частности, может быть использован для определения таких классических понятий, как раскраски, подграфы, а также элементарных операций на графах. При построении инварианта I [G] используется подход, аналогичный алгоритмам построения канонических форм графа (подробнее об этом см. [12]). Можно провести также некоторую аналогию между итоговым инвариантом I [G] и линейной нотацией для молекулярных графов стандарта SMILES [13]. Отметим, что ключевым преимуществом инварианта I [G] по отношению к существующим методам хранения графов является полное описание всех симметрий графа. В частности, это позволяет эффективно реализовать процедуру визуализации графа G с учётом всех возможных сим-метрий этого графа на плоскости или в пространстве. 1. Построение индексации для классов симметрии Определение 2. Пусть дан произвольный конечный граф G = (V, E), у которого число вершин | V | = n. Тогда, если выбрать некоторый порядок для множества вершин a = (vi,... , vn), то можно поставить в соответствие графу G матрицу смежности A по стандартному правилу: A(i,j) = 1 ^ (Vi,Vj) е E Л A(i,j) = 0 ^ (vi,v,-) е E. На рис. 2 представлен пример двух матриц смежности, которые построены для разных порядков на множестве вершин графа. d d G c a A2 c e b d a c 0 1 1 1 0 e 1 0 1 1 0 b 1 1 0 0 1 d 1 1 0 0 0 a 0 0 1 0 0 e A а b c d e а 0 1 0 0 0 b 1 0 1 0 1 c 0 1 0 1 1 d 0 0 1 0 1 e 0 1 1 1 0 Рис. 2. Пример двух разных матриц смежности Ai и A2 для одного графа Отметим, что матрицы смежности будут совпадать для тех перестановок вершин, которые задают автоморфизмы графа. В пределе максимально возможное число разных матриц смежности равно n! - числу всех перестановок из n элементов и достигается только у асимметричных графов. Определение 3. Для произвольного графа G определим рёберный граф L{G} как граф, чьими вершинами являются рёбра E(G), а связи устанавливаются между теми из них, которые имеют ровно одну общую вершину из V(G): L{G} : V(L{G}) = E(G), E(L{G}) = {((ui,u2), (vi,V2)) : 3i, j е {1, 2} : u = Vj Л Uj = v}. Пример перехода от графа G к рёберному графу L{G} представлен на рис. 3. d (d (c d) (d , e) (b ,e) a a (a b) Рис. 3. Переход от G к рёберному графу L{G} c Замечание 1. Отметим, что любой автоморфизм ф : V(L{G})^V(L{G}) рёберного графа L{G} одновременно является рёберными автоморфизмом ф : E(G)^E(G) для исходного графа G. Определение 4. Кодом матрицы смежности A конечного графа G будем называть такое число ^(A), которое получается в результате перевода матрицы смежности в бинарное число A(1,1)A(1, 2)... A(1, n)A(2,1)... A(n, n). На практике для представления числа ^(A) обычно используются десятичная или шестнадцатеричная системы счисления. Определение 5. Наибольший из всех возможных кодов матриц смежности графа G назовём макси-кодом ^max(G). Если для некоторого порядка a вершин код матрицы смежности ^(A) = ^max(G), то будем говорить, что порядок a соответствует макси-коду. Макси-код является полным инвариантом графа, так как по нему можно однозначно восстановить матрицу смежности. Важно отметить, что порядков следования вершин а, которые соответствуют макси-коду, может быть несколько при условии, что у графа есть хотя бы один нетривиальный автоморфизм. Определение 6. Наибольший из всех возможных кодов матриц смежности рёберного графа L{G} назовём рёберным макси-кодом ^max(G). Утверждение 1. Если два порядка вершин а1 = (г»1,... , v^) и а2 = (v2,... , v^) соответствуют макси-коду ^max(G) графа G, то вершины в этих порядках попарно автоморфны: v1 ~ vj2 для всех k = 1,..., n. Доказательство. Совпадение для двух порядков вершин значения кода ^(A) возможно лишь в том случае, если совпадают сами матрицы смежности для этих порядков. Это, в свою очередь, означает, что перестановка вершин - = (2 vn2 Vv1 ... vn является автоморфизмом графа G. ■ Утверждение 2. Если два порядка рёбер в1 = (е1,..., ) и в2 = (e2,... , е1) соответствуют рёберному макси-коду ^max(G) графа G, то рёбра в этих порядках попарно автоморфны: e1 ~ e2 для всех i = 1,..., k. Доказательство. Данное утверждение является очевидным следствием утверждения 1, если учесть, что любой автоморфизм рёберного графа L{G} является рёберным автоморфизмом графа G. ■ Будем использовать для последовательностей вершин а = (v1,...,vn) стандартное индексное обозначение элементов v = a(i). Для последовательности рёбер в = = (e1,..., en) будем использовать аналогичное обозначение ei = в(i). Определение 7. Пусть макси-коду графа G соответствует некоторый порядок следования вершин а. Назовём индексом класса симметрии вершин v натуральное число I(v), равное первому вхождению в порядок а вершины из класса v. Формально это можно записать так: I(v) = min i. i: v~a(i) Корректность определения индексов для классов симметрии вершин непосредственно следует из утверждения 1. Действительно, если макси-коду графа соответствуют два варианта последовательностей вершин а1 = (v^ ... , v^) и а2 = (vj2,... , v^), то v1 ~ v| для всех k = 1,... , n. Как следствие, индекс первого вхождения вершины из класса v одинаков в а 1 и а2. Определение 8. Пусть рёберному макси-коду ^max(G) графа G соответствует некоторый порядок следования рёбер в. Назовём индексом класса симметрии рёбер (u,v) натуральное число I(u,v), равное первому вхождению в в ребра из класса (u,v), т.е. I(u,v) = min i. i: (u,v)~e(i) По аналогии с вершинами, корректность определения индексов для классов симметрии рёбер есть прямое следствие утверждения 2. Теорема 1. Если G = H, то для двух вершин u Е V(G), v Е V(H) условие I(u) = I(v) выполняется тогда и только тогда, когда существует изоморфизм : V(G) ^ V(H), такой, что

Ключевые слова

изоморфизм графов, классы симметрии вершин, классы симметрии рёбер, инварианты графов

Авторы

ФИООрганизацияДополнительноE-mail
Назаров Максим НиколаевичНациональный исследовательский университет «МИЭТ» (Московский институт электронной техники) (г. Москва)ассистент кафедры ВМ-1Nazarov-Maximilian@yandex.ru
Всего: 1

Ссылки

Diestel R. Graph Theory. 3rd edition. Heidelberg: Springer Verlag, 2005. 451 p.
Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. М.: Высшая школа, 1976. 391 с.
Зыков А. А. Основы теории графов. М.: Наука, 1987. 383с.
Holmes M. R. Elementary Set Theory with a Universal Set. Louvain-la-Neuve: Academia, 1998. 241 p.
Aloul F. A., Ramani A., Markov I. L., and Sakallah K. A. Solving difficult instances of Boolean satisfiability in the presence of symmetry // IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems. 2003. V.22. No. 9, P. 1117-1137.
Darga P., Sakallah K., and Markov I. L. Faster symmetry discovery using sparsity of symmetries // Proc. 45st Design Automation Conference. N.Y.: ACM, 2008. P. 149-154.
Фларри Р. Группы симметрии. Теория и химические приложения. М.: Мир, 1983. 400 с.
Bonchev D. and Rouvray D. H. Chemical Graph Theory: Introduction and Fundamentals. N.Y.: Gordon and Breach science publishers, 1991. 300 p.
Кинг Р. Химические приложения топологии и теории графов. М.: Мир, 1987. 560 с.
Sparrow M. K. A linear algorithm for computing automorphic equivalence classes: the numerical signatures approach // Social Networks. 1993. V. 15. P. 151-170.
Southwell R. Finding Symmetries in Graphs. Ph.D. thesis. University of York, UK, 2006. 109 p.
Katebi H., Sakallah K., and Markov I. L. Graph symmetry detection and canonical labelling: differences and synergies // Proc. Turing-100, EPIC 2012. V. 10. P. 181-195.
Weininger D., Weininger A., and Weininger J. SMILES. 2. Algorithm for generation of unique SMILES notation // J. Chem. Inf. Comput. Sci. 1989. V.29. No. 2, P. 97-101.
Харари Ф. Теория графов. М.: КомКнига, 2006. 296 с.
Kobler J., Schoning U., and Toran J. The Graph Isomorphism Problem: its Structural Complexity. Berlin: Birkhauser, 1993. 160 p.
Harary F. A survey of the reconstruction conjecture // Graphs and Combinatorics. Lecture Notes in Mathematics. 1974. V. 406. P. 18-28.
 Альтернативные подходы к описанию классов изоморфных графов | ПДМ. 2014. № 3 (25).

Альтернативные подходы к описанию классов изоморфных графов | ПДМ. 2014. № 3 (25).