Введение
1. Основные подходы к определению сходства графовых моделей систем
1.1. Задачи определения сходства графовых моделей систем и подходы к их решению 16
1.1.1. Подструктурный подход и его развитие 16
1.1.2. Структурно-характеристический подход на основе инвариантов графов 20
1.2. Классификация задач определения максимальных общих частей и сходства двух орграфов 22
1.2.1. Классификация задач определения максимальных общих фрагментов двух орграфов 22
1.2.2. Классификация задач определения сходства орграфов 25
1.3. Результаты вычислительных экспериментов определения сходства орграфов по П-подходу 26
1.3.1. Метод монотонных расширений частичных решений для определения MCS и MCF двух орграфов 26
1.3.2. Результаты анализа П-подхода к определению сходства орграфов и его недостатки 27
1.4. Эффективность решения задач определения сходства на орлесах и ордеревьях 28
1.4.1. Экспериментальные оценки вычислительной сложности алгоритма определения сходства двух ордеревьев по методу монотонных расширений частичных решений 28
1.4.2. Экспериментальные оценки вычислительной сложности оригинального алгоритма определения сходства двух ордеревьев 29
1.5. Задачи вычисления сходства ордеревьев и орлесов, имеющие прикладную значимость 30
1.5.1. Задача вычисления сходства пар ордеревьев и орлесов с весами на вершинах, решаемые по разработанному алгоритму 30
1.5.2. Задача поиска в базе орлесов, сходных с шаблоном 31
1.6. Основные результаты и выводы по главе 35
2. Модели обобщенной надструктурной характеризации орграфов 37
2.1. Обобщенная модель орграфа в базисе полупутей и ее подмодели 38
2.1.1. Порождающая граф-модель орграфа в базисе полупутей 38
2.1.2. Подкласс порождающих граф-моделей орграфа в базисе полупутей
2.2. Стратификация порождающих моделей орграфа в базисе полупутей 45
2.3. Порождающие модели с выделенной вершиной и система методов решения задач определения сходства расположения двух полупутей с уточнением результата
2.3.1. Иерархические g-модели с выделенной вершиной в направленных орграфах 46
2.3.2. Система стратификации g-моделей 48
2.4. Методы решения задач различения и сходства расположения полупутей с учетом их точного расположения в орграфе
2.4.1. Формализованная постановка задачи различения расположения полупутей заданного типа в орграфе
2.4.2. Формализованная постановка задачи определения сходства расположения полупутей в орграфе на основе
2.4.3. Метод решения задачи определения сходства двух орграфов на основе сходства расположения полупутей
2.5. Класс базовых моделей, построенных на основе g-моделей орграфов, и его основные подклассы 52
2.5.1. Класс базовых моделей 53
2.5.2. Примеры решения задач различения орграфов и различения расположения фрагментов в орграфе на основе Ь-моделей 54
2.5.3. Класс иерархических Ь-моделей 56
2.5.4. Система стратификации Ь-моделей 56
2.5.5. Метод количественного определения сходства орграфов с использование Ь-моделей 57
2.5.6. Пример решения задачи определения сходства орграфов на основе Ь-моделей вида V се HPw 58
3. Алгоритмические основы методов надструктурной характеразации для анализа сходства орграфов 62
3.1. Задача определения сходства орграфов и подструктурный подход к её решению 62
3.2. Методы определения сходства орграфов на основе надграфов полупутей
3.2.1. Классификация методов определения сходства двух орграфов 65
3.2.2. Надграфы полупутей как основа нового метода определения сходства орграфов с точной характеризацией
3.2.3. Главное свойство надграфов полупутей 68
3.2.4. Связь изменений надграфов полупутей, порожденных изменениями анализируемых орграфов 73
3.3. Эффективные методы решения задач определения точного и частичного точного сходства орграфов большого
3.3.1. Сведение задачи распознавания изоморфизма надграфов к распознаванию изоморфизма их исходных орграфов 75
3.3.2. Алгоритм конструктивного распознавания исходного орграфа в надграфе полупутей 78
3.3.3. Метод распознавания изоморфизма орграфов большого порядка 80
3.3.4. Метод распознавания изоморфного вложения для орграфов большого порядка 81
3.3.5. Метод определения сходства двух орграфов большого порядка по П-подходу с использованием алгоритма
3.4. Надструктурный подход к определению сходства орграфов 84
3.4.1. Страты надграфов полупутей и их применение для определения сходства орграфов 84
3.4.2. Пример анализа сходства и кластеризации орграфов по П- и Н-подходу 86
3.4.3. Экспериментальные оценки вычислительной сложности алгоритма построения надграфов полупутей для ордеревьев 87
3.4.4. Эффективный алгоритм решения задач определения сходства для двудольных орграфов большого порядка 89
3.5. Результаты экспериментов по определению сходства и различению орграфов на основе характеристик
сходства 89
3.6. Основные результаты и выводы по главе 91
4. Два подхода к определению сходства темпоральных орграфов 94
4.1. Основные определения и базовые классы задач в анализе T-орграфов 95
4.1.1. Основные определения 95
4.1.2. Базовые классы теоретических и прикладных задач в анализе темпоральных орграфов 96
4.2. Два класса задач определения сходства Т-орграфов решению задач 97
4.2.1. Функции вычисления расстояний и индексов сходства структур tiG, tjG 97
4.3. Система методов анализа сходства Т-орграфов по Н-подходу с использованием надграфов полупутей 99
4.4. Метод повышения эффективности решения задач определения сходства темпоральных орграфов 105
4.5. Подход к определению сходства T-орграфов на основе иерархической системы моделей сложности
4.5.1. Расширенная матрица b-модели tG 106
4.5.2. Матрицы вкладов фрагментов в общую сложность tG 107
4.6. Методы анализа глобального и локального сходства двух Т-орграфов 111
4.6.1. Метод анализа глобального сходства T-орграфов на основе индексов и вектор-индексов сложности tG 112
4.6.2. Метод анализа динамики изменения локальных свойств и сходства T-орграфов на основе относительных вкладов вершин в сложность tG 113
4.7. Основные результаты и выводы по главе 114
Заключение 116
Список литературы 118
