Введение
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
список литературы
