Содержание к диссертации
Введение
1. Различение расположения фрагментов как новый уровень задач различения графов 13
1.1. Эквивалентность и толерантность графов и расположения их фрагментов 13
1.2. Графы, фрагменты и помеченные фрагменты 14
1.3. Группы автоморфизмов, индуцированные вершинной группой автоморфизмов (An/(G)) 18
1.3.1. Пример t-группы 19
1.4. Задачи различения расположения фрагментов в графе 21
1.4.1. Задачи различения расположения однотипных фрагментов 21
1.4.2. Задачи различения расположения произвольных фрагментов 22
1.4.3. Обсуждение постановок задач различения расположения фрагментов 23
1.4.4. Сведение задач различения графов к задачам различения расположения фрагментов 23
1.4.5. Сводная таблица основных задач различения 24
1.4.6. Инвариантное ядро задач различения №1 (ИЯЗР1) в СС-анализе 24
1.4.7. Инвариантное ядро задач различения №2 (ИЯЗР2) в СС-анализе 24
1.4.8. ,- и т-эквивалентность 25
1.4.9. Задачи различения т-э кв и валентности расположения фрагментов 26
1.5. Подходы к решению задач изИЯЗРІ и ИЯЗР2 26
1.5.1. Систематизация подходов к решению задач из И.ЯЗР1 27
1.5.2. Сложность и методы решения задач из ИЯЗР1 28
1.5.3. Систематизация подходов к решению задач из И.ЯЗР2 29
Выводы и результаты по главе 32
2. Переборно-групповой подход к решению задач различения расположения фрагментов 33
2.1. Базовые задачи 33
2.1.1. Представление фрагментов в памяти компьютера 33
2.1.2. Построение порождающего множеств а группы автоморфизмов графа 33
2.1.3. Вид порождающего множества, используемый в данной работе 34
2.1.4. Представление порождающего множества, описанного выше 35
2.1.5. Канонизация представления помеченного фрагмента на основе порождающего множества
группы автоморфизмов фрагмента 36
2.1.6. Построение порождающего множества фиксатора/стабилизатора подмножества вершин графа 38
2.2. Построение и исследование /-групп 41
2.2.1. Представление порождающего множества t-группы 44
2.2.2. Поиск помеченного фрагмента в базе фрагментов 44
2.2.3. Построение порождающего множества t-группы 45
2.2.4. Поиск орбит t-группы без построения порождающего множества t-группы 46
2.3. Решение задач из класса задач различения расположения фрагментов 49
2.3.1. Решение задач различения расположения однотипных фрагментов 49
2.3.2. Решение задач различения расположения произвольных фрагментов 49
2.3.3. Построение и анализ матрицы пересечения орбит помеченных фрагментов 49
2.3.4. Пример хар акте риз а ци и расположения фрагментов в графе 51
2.4. Экспериментальная оценка вычислительной сложности алгоритмов 52
2.5. Перспективы дальнейшего развития методов переборно-группового подхода 54
Выводы и результаты по главе 55
3. Структурно-характеристический подход к решению задач различения расположения фрагментов 56
3.1. Использование структурных инвариантов 56
3.2. g-модели и ^-модели графа для визуализации и решения задач различения расположения фрагментов графа 57
3.3. Построение и исследование g-моделей и А-моделей , 59
3.3.1. Способы задания базисов структурных дескрипторов 60
3.3.2. Определение ребер и их весов : 62
3.3.3. Решение задач из класса задач различения расположения фрагментов на основе g-моделей 63
3.3.4. Решение задач из класса задач различения расположения фрагментов на основе b-моделей 64
3.3.5. Построение отношений эквивалентности и сходства графов на основе g- и b-моделей 64
3.4. Построение и исследование графов расположения цепей 65
3.4.1. g-модели с равными долями 65
3.4.2. Определение графа расположения цепей (ГРЦ) 66
3.4.3. Эффективный метод построения ГРЦ 66
3.4.4. Обозначения ГРЦ 67
3.4.5. Алгоритм построения ГРЦ 68
3.4.6. Доказательство корректности алгоритма 76
3.4.7. Некоторые свойства ГРЦ 78
3.4.8. Пример построения ГРЦ 79
3.4.9. Исследование симметрии цепей исходного графа с использованием ГРЦ S1
3.4.10. Обобщение ГРЦ для анализа фрагментов других типов 83
3.4. П. Результаты экспериментов 84
3.5. Усиление чувствительности структурных инвариантов 86
3.5.1. Итерационные методы усиления чувствительности 87
3.5.2. Итерационное уточнение разбиения множества вершин на классы эквивалентности по
g-модели 87
3.5.3. Параметризация процедуры построения матрицы структурных инвариантов и проведение
экспериментов по исследованию чувствительности инвариантов итерационного типа 96
3.6. Перспективы развития методов структурно-характеристического подхода 97
Выводы и результаты по главе 98
4. Подсистемы асни «graph model workshop» для исследования алгоритмов структурного спектрального анализа систем 99
4.1. История создания 99
4.2. Общая архитектура АСНИ и место авторских подсистем в ней 99
4.3. Программная реализация подсистем 101
4.4. Основные расширения АСНИ, реализованные автором 104
4.5. Учёт симметрии расположения фрагментов для повышения эффективности решения задач структурного спектрального анализа 107
4.5.1. Развитие методологии монотонного расширения частичных решений 107
4.5.2. Поиск всех канонических изоморфных вложений 107
4.5.3. Максимальное изоморфное пересечение с учётом симметрии 107
4.5.4. Декомпозиция графа на неизоморфные фрагменты 109
4.5.5. Интерактивный поиск гам ил ьто новых цепей и циклов 111
4.6. Система проведения экспериментов и «полигон» исследования эффективности алгоритмов 113
4.6.1. Схема эксперимента 113
4.6.2. Сохранение результатов 114
4.6.3. Анализ результатов 114
4.6.4. Пример многоэтапного вычислительного эксперимента 115
4.6.5. Вычислительные эксперименты, которые могут проводиться с использованием программных разработок автора 119
4.7. Исследование эффективности подходов к решению задач различения расположения
фрагментов 119
4.7.1. Используемые методики и тестовые данные 119
4.7.2. Результаты вычислительных экспериментов 121
4.7.3. Границы применимости 123
4.7.4. Выводы и рекомендации по применению 125
Выводы и результаты по главе 125
5. Применение разработанных методов и программных средств для решения теоретических и прикладных задач 127
5.1. Результаты теоретических исследований 127
5.1.1. Исследования, связанные с анализом симметрии графов 127
5.1.2. Исследования итерационных процедур уточнения разбиения фрагментов на классы эквивалентности 130
5.1.3. Исследование эквивалентных примарных фрагментов, полученных удалением неэквивалентных вершин и рёбер 136
5.1.4. Исследования отношения эквивалентности графов с учётом расположения орбит фрагментов 138
5.2. Результаты применения в учебном процессе 139
Результаты по главе 140
Заключение 142
Выводы 144
список литературы
- Группы автоморфизмов, индуцированные вершинной группой автоморфизмов (An/(G))
- Вид порождающего множества, используемый в данной работе
- Построение и исследование g-моделей и А-моделей
- Учёт симметрии расположения фрагментов для повышения эффективности решения задач структурного спектрального анализа
Введение к работе
Тема работы: методы и программные средства для различения расположения фрагментов графовых моделей систем.
Группы автоморфизмов, индуцированные вершинной группой автоморфизмов (An/(G))
Формализуем понятие группы ґ-автоморфизмов Aut (G), определяющей симметрию расположения фрагментов типа t в графе. Эта группа индуцируется группой вершинных автоморфизмов графа (ГАГ). Для определения Aut (G) введём следующие обозначения.
T-автоморфизмом графа G называется подстановка g на множестве помеченных фрагментов типа t графа G (или канонических изоморфных вложений) F (G), индуцированная некоторым вершинным автоморфизмом g графа G. В процессе индуцирования помеченный фрагмент / є F(l) (G), представленный каноническим изоморфным вложением (vb V2, ..., v„) графа G, переходит в помеченный фрагмент fl)tj є F l)t{G), каноническое представление которого получено канонизацией вложения (щ, U2, ..., ип), где щ = g(vl), і є [1,и], п - число вершин фрагмента. Приведённое определение /-автоморфизма не зависит от нумерации вершин графа и абстрактного типа фрагмента. Действительно, пусть перенумерация графа задаётся перестановкой номеров 6 и перенумерация типа фрагмента - перестановкой номеров у. Как известно, группы автоморфизмов исходного и перенумерованного графов идентичны: 5(u(v)) = u5(5(v)), где д. є Aut{G\ и y(A,(v)) = A7(y(v)), где X е Aut(t). Канонизация представления помеченного фрагмента по сути является применением некоторого автоморфизма из Autif) к неканоническому изоморфному вложению. Поэтому изменение нумерации будет приводить лишь к выбору других канонических представлений помеченных фрагментов [10].
Группой t-автоморфизмое графа G (Aid{G\ /-группа) называется группа подстановок, носителем которой является всё множество /-автоморфизмов для данного /, а групповой операцией - операция произведения (композиции) подстановок.
Тот факт, что множество /-автоморфизмов образует группу, непосредственно следует из свойств ГАГ. Степень /-группы равна числу канонических изоморфных вложений абстрактного типа / в граф G ( F l)t(G) \), а порядок меньше или равен порядку вершинной группы, так как два различных нетождественных вершинных автоморфизма могут индуцировать один и тот же /-автоморфизм. Все понятия, связанные с анализом Aui{G), определяются абсолютно аналогично понятиям, связанным с анализом Aut(G) (например, /-фиксатор, /-стабилизатор и т.д.). /-группа полностью характеризует симметрию фрагментов типа / в графе так же, как ГАГ характеризует симметрию вершин.
Заметим, что нестрого можно определить аетоморфные помеченные фрагменты без привлечения Aui{G), как помеченные фрагменты, переходящие друг в друга при автоморфизмах исследуемого графа. 1.3.1. Пример t-группы Рассмотрим группу /-автоморфизмов транзитивного графа 9-4-1, изображённого на рис. 1.3. Идентификационный тип / (цикл длины 3) изображён на рис. 1.4. Рис. 1.3. Граф Trans_9-4-l Рис. 1.4. Тип фрагмента (і) - цикл длины 3 (С3) Порядок группы вершинных автоморфизмов = 18. Граф содержит 3 цикла длины 3.
Порядок группы Сз-автоморфизмов AutCy(G) равен 6. Отметим тот факт, что порядок группы Сз-автоморфизмов меньше порядка вершинной группы - три различных вершинных автоморфизма индуцируют один и тот же Сз-автоморфизм.
Сз-автоморфизмы графа Trans 9-4-1 содержатся в таблице 1.1 (фрагменты представлены каноническими списками вершин; неподвижные точки выделены жирным шрифтом; автоморфизмы, входящие в сильное порождающее множество, залиты серым цветом).
Задача различения расположения двух однотипных помеченных фрагментов f() i,f(l)lj типа t в графе G определяется набором параметров [77]: РРОФ = &;/«",;/«";;? , где G - обыкновенный граф (G = {V,E),\ V\ =р, \E\=q); - множество всех помеченных фрагментов типа t, вкладываемых в G в некотором смысле или, что то же, множество всех канонических изоморфных вложений t в G в некотором смысле); - отношение принадлежности к одной орбите группы ґ-автоморфизмов (/-группы). Решением задачи РРОФ является ответ на вопрос, связаны ли f и fl)ij отношением ; , то есть, принадлежат ли f \ и f(l) j одной и той же орбите /-группы. В такой постановке РРОФ является задачей распознавания свойств {decision problem). Её расширением является задача автоморфного разбиения множества фрагментов типа t в графе G с набором параметров АРМОФ = G; i ; .
Задача различения расположения двух однотипных помеченных фрагментов j(i)t_j(i)t_ типа t относительно выделенного фрагмента f \ того же типа t в графе G определяется набором параметров: РРОФОВ = G; /WfifWjif 5% где fl)ti, f pf k є F(l)t {F(i)t - множество всех помеченных фрагментов типа t, вкладываемых в G в некотором смысле); , - отношение принадлежности к одной орбите /-фиксатора/ \.
Решением задачи РРОФОВ является ответ на вопрос, связаны ли/ ,- и fl)lj отношением , то есть, принадлежат ли/№,- и / у одной орбите фиксатора/ . В такой постановке РРОФОВ является задачей распознавания свойств. Её расширением является задача автоморфного разбиения множества однотипных фрагментов (типа і) относительно выделенного фрагмента fl)tk того же типа t с набором параметров
АРМОФОВ = G; Ґ9 ;/ ; .
Задачи различения расположения произвольных фрагментов
Обобщением задачи РРОФ является задача различения расположения двух помеченных фрагментов/"1,-, fmj типов t\ и tl в графе G. Она определяется следующим набором параметров: Т РФ = G;fmf,fmj;!l , где/-"1, є F l)t\ fmj є F !)a (&!] и F12 - множества всех помеченных фрагментов типов tl и tl, вкладываемых в G в некотором смысле); "-2 - отношение «некоторый элемент орбиты помеченного фрагмента/ "у изоморфно вкладывается в некоторый элемент орбиты помеченного фрагмента f(,)l2j», то есть У/""\ є QiAufiG),/ ",) (3f % є Q{Aui\G),f : (f""\ Є/%)), где (Aut!(G),f!)-орбита / -"относительно г-группы. Это отношение предложено Коховым В.А. и будет обобщаться далее. Расширением задачи РРФ является задача различения расположения всех фрагментов типа Я и tl в графе G с набором параметров РРМФ = С;2 а;$йза . Заметим, что для решения задач РРФ и РРМФ требуется сначала решить две задачи АРМОФ (для фрагментов типа tl и tl). Задача различения расположения двух помеченных фрагментов /№1,-,/№2/ типов t\ и tl относительно выделенного фрагмента/ типа tl в графе G определяется следующим набором параметров:
Вид порождающего множества, используемый в данной работе
Далее будем использовать конкретный вид ПМ, который описан в [22]. Причиной его выбора послужила возможность построения на его основе эффективных алгоритмов решения базовых задач, таких как канонизация представления помеченного фрагмента.
Пусть дан обыкновенный граф G = {V, Е). Обозначим через F{i, к) подмножество автоморфизмов Aut(G), оставляющих на месте вершины vb ..., V/.b и переводящих вершину Vj в vk (і к р). Ясно, что какие-то из F(i, к) могут быть пустыми. Если і к, то F{i, к) не содержит тождественного автоморфизма.
Через S обозначим подмножество Aut{G), в которое войдёт по одному представителю каждого непустого F(i, к), где г к. Пусть Sk - подмножество 5, в которое войдут автоморфизмы, оставляющие на месте вершины vb ...,vk-i и переводящие вершину vk в V/ (/ Ф к). Заметим, что »% (р-к), а некоторые из /с могут быть пустыми. Всего в S входит не более р(р-1)/2 автоморфизмов. Каждое подмножество Sk с добавлением к нему тождественного автоморфизма (5/;u {е}) назовём к-классом автоморфизмов ПМ. Нетривиальным k-классом назовём такой к-класс, мощность которого больше 1. Vg є Aut{G) {3!/i, ...,fp є (Я и {e}): {(fk є (&u {e}), к є [Up]) & (g=fi fp ))) то есть любой автоморфизм из Aut{G) может быть единственным образом представлен в виде произведения, включающего по одному представителю каждого -класса. Порождающее множество (S и {е}) обозначим через AGS{G). \Aiit(G)\ = (\Si\ +l)-...-{\Sp\ +1), то есть порядок ГАГ равен произведению мощностей -классов ПМ ГАГ.
Описанное ПМ ГАГ, включающее представителей каждого класса смежности, в англоязычной литературе получило название сильного ПМ {strong generator set). Отметим, что орбиты группы строятся по сильному ПМ за полиномиальное время [10].
Для удобства записи алгоритмов1 и передачи параметров введём класс TAGS, представляющий AGS{G) и имеющий следующие основные поля: VCount: integer - число вершин графа G. AutosOrder: integer - порядок ГАГ. FloatAutosOrder: real - порядок ГАГ, выраженный вещественным числом, если он не помещается в используемое для хранения AutosOrder целое (в настоящий момент - 64 бита). AGSOrder: integer - число автоморфизмов в ПМ ГАГ. AGS: array of array of integer - аВТОМОрфиЗМЫ ПМ (прЯМОуГОЛЬНаЯ матрица размером AGSOrder х VCount). ClassCount: integer - число нетривиальных -классов ПМ. ClassPowers: array of integer - мощности классов (массив размерностью ClassCount). Из определения нетривиального класса следует, что его мощность всегда 1.
Classlndices: array of array of integer - индексы автоморфизмов, входящих в классы (непрямоугольная матрица размером ClassCount х ClassPowers[ і ], і є [0, ClassCount-l]). Нулевой столбец заполнен индексами тождественного автоморфизма для удобства перечисления всех автоморфизмов группы. Таким образом автоморфизм с индексом Class-Indices[ г, 0 ] - тождественный. Классы отсортированы естественным образом - по номеру позиции первой вершины, перемещаемой нетривиальными автоморфизмами класса. OrbsCount: integer-ЧИСЛО орбит ГАГ. Orbs: array of integer - индексы орбит (массив размером VCount). Две вершины принадлежат одной орбите тогда и только тогда, когда их индексы орбит равны. Возможны два варианта присвоения индексов: 1. Последовательное присвоение индексов орбитам, начиная с 1. Замечания по стилю описания алгоритмов приведены в Приложении 1. . Присвоение орбите индекса, равного минимальному номеру вершины среди вершин, входящих в орбиту. Каждый из этих вариантов обладает преимуществами, проявляющимися в разных ситуациях. OrbsStruct; array of integer - структура орбит вершин (массив размером VCount). OrbsStruct[ і ] равно числу вхождений индекса z -ой орбиты в Orbs (что при первом варианте присвоения индексов орбитам равно числу вхождений индекса (i + 1) в Orbs).
Построение и исследование g-моделей и А-моделей
При построении g- и Ь-моделей задавать базисы (TL и 77?) можно по-разному. От способа задания базисов зависит предпочтительный вариант построения множества вершин (и весов вершин).
Если базис априори задаётся набором графов или достаточно узким семейством графов, то достаточно запустить процедуру поиска всех канонических изоморфных влолсений (ПВКИВ) для каждого элемента базиса.
При задании же базиса как подмножества собственных фрагментов графа, удобней воспользоваться декомпозицией графа на помеченные фрагменты (ДГПФ) с заданными параметрами. Причём, если мощность базиса много меньше числа всех собственных фрагментов графа, имеет смысл сначала найти фрагменты, вкладываемые в граф, с использованием декомпозиции графа на неизоморфные фрагменты (ДГНФ), а затем построить базы помеченных фрагментов с использованием ПВКИВ. В противном случае лучше использовать декомпозицию с одновременным получением помеченных фрагментов. Аналогично тому, как описано в разделе 2.2, этот этап структурно-характеристического подхода использует те же методы, что и переборно-групповой подход. Способ с использованием ПВКИВ позволяет обрабатывать намного более крупные структуры.
Автором реализован способ с использованием ПВКИВ, а коллегой по научной группе СВ. Ткаченко - способ с использованием декомпозиции на помеченные фрагменты. Выбор базиса реализован автором в наиболее полном виде (рис. 3.2, рис, 3.3), с возможностью для каждого элемента базиса задать свой тип вложения и индекс структурной сложности. На рис, 3.4 показан пример задания остальных параметров построения моделей (в основном относящихся к заданию свойств отношения sr). Базисы и параметры построения (профиль модели) можно сохранить для последующего использования.
Операция изоморфного пересечения помеченных фрагментов сводится к теоретико-множественному пересечению множеств вершин и рёбер фрагментов и, по сравнению с построением множеств вершин, имеет очень небольшую сложность. Вопрос теоретико-множественного пересечения помеченных фрагментов уже обсуждался в разделе 2.3.3. Единственное отличие - необходимость по множествам вершин и рёбер пересечения построить граф в тех случаях, когда g-модель содержит структурные веса рёбер или в отношении присутствуют структурные ограничения на результат пересечения (например, связность общего фрагмента). Если отношение построено на основе операции изоморфного вложения помеченных фрагментов, то этот граф совпадает с весом инцидентной вершины левой доли.
При решении многих задач из класса РРФТ не обязательно строить сразу все рёбра g- или Ь-модели. Можно уже в процессе характеризации расположения фрагментов строить только те рёбра (и их веса), которые необходимы данному алгоритму характеризации.
С использованием g-моделей можно построить стройную иерархическую систему характеристических инвариантов помеченных фрагментов различных видов: структурных, матричных, векторных и числовых - причём не только с целью решения задач различения, но и с целью развития методов анализа структурной сложности и сходства систем [72]. Причём отдельные уровни этой иерархии покрывают большинство из ранее известных характеристик, являющихся с позиций стратификации g-моделей частными случаями некоторых подмоделей.
Самый верхний уровень характеризации расположения фрагментов заключается в анализе окружения вершин левой доли g-модели, соответствующих исследуемым помеченным фрагментам. Если из g-модели по некоторому правилу выделить подграф, включающий помеченный фрагмент левой доли f\ (выбор ), то данный подграф, называемый g-моделью с выделенной вершиной ( -модель, GM(f /с, ...)), будет являться инвариантом фрагментау \, если веса вершин и рёбер в виде помеченных фрагментов поменять на веса в виде абстрактных типов. Правило построения g -модели может быть достаточно сложным, однако на практике в {GMif t, ...)) включают вершины, соответствующие фрагментам fl)txy, в которые вкладывается/
Набор {GM(f(l)t\, ...), ..., GM(f(l)tm, ...)) является важным спектром графа и определяет классы эквивалентности фрагментов (КЭФ) по отношению і1 - «иметь изоморфные g -модели», то есть помеченные фрагменты fl) i и fl)tj принадлежат одному КЭФ тогда и только тогда, когда GMtf i, ...) изоморфна GM(f(l)lj, ...) с учетом весов вершин и рёбер.
На основе строк матрицы g-модели можно уточнить полученное разбиение на КЭФ, используя универсальный метод, описанный в разделе 3.5.
Для решения задач различения расположения фрагментов относительно выделенного фрагмента предложен метод, основанный на введении дополнительно го целочисленного веса, присвоении уникальных значений этого веса вершинам и/или рёбрам выделенного фрагмента и рассмотрении исходного графа как взвешенного. При этом помеченные фрагменты также становятся взвешенными дополнительным весом.
Учёт симметрии расположения фрагментов для повышения эффективности решения задач структурного спектрального анализа
Методология монотонного расширения частичных решений (ММРЧР) - универсальная методология построения алгоритмов решения базовых задач СС-анализа, предложенная Коховым В.А. Первые алгоритмы по этой методологии были разработаны Коховым В.А. и Грызуновым А.Б. [52]. Автором развит один из аспектов методологии ММРЧР - учёт симметрии расположения фрагментов в графе для сокращения перебора при решении ЛГР-полных задач. Впервые учёт симметрии продемонстрирован Грызуновым А.Б. [51] при поиске изоморфного вложения и максимального изоморфного пересечения.
Поиск всех канонических изоморфных вложений
Алгоритм поиска всех канонических изоморфных вложений (ПВКИВ) является базовым при исследовании расположения фрагментов в графе. Но уже при его создании можно воспользоваться учётом симметрии расположения вершин. Однако главной особенностью реализованного автором алгоритма является использование эффективного алгоритма канонизации представления помеченного фрагмента для отсева неканонических представлений [100]. Алгоритм строит базу канонических представлений помеченных фрагментов, упорядоченную по лексикографическому возрастанию. Это позволяет затем использовать бинарный поиск в базе помеченных фрагментов.
Максимальное изоморфное пересечение с учётом симметрии
Задача поиска максимального общего фрагмента (МОФ) графов или поиска максимальных изоморфных пересечений (МИПГ) - одна из важнейших задач теории графов. Она является самой сложной из базовых задач, входящих в ИЯЗ СС-анализа. Автором реализован вариант алгоритма поиска МОФ в смысле подграфа, а также поиска всех типов МОФ и всех канонических МИПГ.
В алгоритме используется сокращение перебора на основе сравнения орбит стабилизатора вершин, входящих в частичное решение. Для наиболее эффектив ного использования оперативной памяти используется кэширование орбит стабилизаторов. Кэш построен на базе словаря, использующего для хранения пар ключ-значение чёрно-красное дерево. Ключом является список стабилизируемых вершин, а значением - массив индексов орбит вершин графа относительно стабилизатора вершин, содержащихся в ключе. Такой кэш оказался эффективней кэша на основе хэш-таблицы. Для графов с группами больших порядков или сложного строения (например, с большим числом тождественной стабильности) это даёт заметный рост производительности. В качестве примера рассмотрим следующие транзитивные графы степени 4 [105]: - первая пара-23-4-3, 24-4-44; \Aut{G) = 46и 98304, \[/-2и 12; - вторая пара- 25-4-4, 26-4-1; \Aut(G) - 200 и 11232, \/ = 2 и 4.
Таблица 4.3 показывает эффективность кэширования орбит стабилизаторов при поиске МОФ данных графов. Без учёта симметрии время работы выражается не миллисекундами, а часами.
С неограниченным кэшированием 306 8536
Рассмотрим также пример пересечения двух молекулярных графов из базы химических структур ВИНИТИ (рис. 4.3). Их пересечение (если рассматривать скелетные молекулярные графы) состоит из 28 вершин. Без учёта симметрии поиск МОФ занимает более 4 часов. Таблица 4.4 показывает эффективность кэширования орбит стабилизаторов.
Заметим, что для графов со слабой симметрией большую эффективность демонстрирует вариант ММРЧР, реализованный Ткаченко СВ.
Решение задачи декомпозиции графа на неизоморфные фрагменты (ДГНФ) заключается в построении всех попарно неизоморфных фрагментов, которые вкладываются в исследуемый граф. Задача имеет огромную временную и емкостную сложность. Граница реальной применимости ДГНФ в общем виде - 25-35 вершин графа небольшой степени. На практике задача ДГНФ решается с набором ограничений на тип вложения фрагментов в граф, связность фрагментов, размер фрагментов и др.
Автором реализована система исследования различных алгоритмов разборки графа с мощной параметризацией, включающая анализ эффективности [99] (рис. 4.4). Особенностью реализации является учёт симметрии для сокращения перебора, использование для отсева неизоморфных фрагментов сравнения канонических кодов, хранение фрагментов в базе на основе бинарного (чёрно-красного) дерева поиска в каноническом представлении.
