Разработка методов и программных средств для решения задач различения и анализа сложности ациклических структур

• Автор: Джасим Малатх Рахим
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 159 с. : ил.

ВВЕДЕНИЕ
Тема работы Разработка методов и программных средств для решения задач различения и анализа сложности ациклических структур.

Актуальность

Эти методы требуют эффективных алгоритмов определения сходства ГМС, выраженного в количественном виде, для поиска наиближайших соседей по сходству с ГМС, которая анализируется. К таким алгоритмам относятся алгоритмы определения максимального изоморфного пересечения пары ГМС и семейства ГМС. Успех разработки таких ИПС напрямую зависит от создания математических теорий сходства ГМС и разработки как эвристических, так и точных эффективных алгоритмов поиска одного или всех общих фрагментов пары или семейства ГМС. Как отмечено в , сдерживающим фактором на пути создания интеллектуальных экспертных систем с правдоподобными рассуждениями в области химической информатики является отсутствие развитых теорий сходства и инструментальных программных средств для определения и исследования сходства структурированных нечисловых объектов графов, мультиграфов, гиперграфов. Таким образом, проблема определения сходства структур, представленных графами, является центральной комбинаторной проблемой структурного анализа систем. СЕАанализ, с целью выделения из них тех, которые в наибольшей степени отвечают за то или иное свойство химическо го соединения. Указанный подход ставит своей целью количественно выявить значимость вкладов различных СД в наличие того или иного свойства соединения. Однако, этот подход не получил должного развития, связанного с учетом расположения и взаимного расположения фрагментов структур. Таким образом,. ГМС . ГМС относительно заданного фрагмента. Несмотря на большие успехи, достигнутые в области теории графов, прикладной теории графов и химической теории 1рафов, вопрос разработки ЭВМориентированной методологии для эффективного решения задач различения ГМС и определения их сложности, а также решения задач различения расположения фрагментов в ГМС и определения их вкладов в общую сложность ГМС остатся открытым и является одним из центральным вопросов ССанализа систем. Решение этих задач и задач определения сходства на основе различных моделей сложности для АС является основной целью данной диссертации. Вопросы разработки наиболее общего подхода к анализу сходства АС, основанного на подструктурном подходе, рассмотрены в , . Однако, этот подход не получил должного развития с точки зрения разработки наиболее эффективных алгоритмов для решения задач распознавания изоморфного вложения ациклических структур во всем многообразии задач распознавания изоморфного вложения АС. Задачи различения графов. Графы, как математические модели структур систем, могут быть связаны отношениями эквивалентности, отражающими свойства структур. Спектр отношений эквивалентности структур очень широк от отношения содержать одинаковое число элементов до отношения быть изоморфными. Отношение быть изоморфными является точной верхней гранью всех отношений эквивалентности структур, определяет наименьшие но мощности классы эквивалентности и хорошо изучено. Исследование рештки отношений эквивалентности структур актуальная проблема ССанализа систем и смежных наук. Существует важный класс отношений, которые определяются в первую очередь не размерами графов, а тем, что и определяет структуру расположением фрагментов в них. Именно такие отношения эквивалентности выделяют новые классы графов и новые отношения эквивалентности графов. Они строятся на основе свойств группы автоморфизмов графа и характеристических инвариантов для определения расположения фрагментов в графе. Задачи различения расположения фрагментов в графе подробно рассмотрены в работах 7,,,,,,,. В данной работе будут рассмотрены задачи определения изоморфного вложения одной АС в другую. Особое внимание будет уделено мало исследованным задачам определения всех канонических изоморфных вложений дерева в дерево и леса в дерево, имеющих широкий спектр практических применений 4. Пусть 7Г, граф с множеством вершин Г7у,,у2,. Е0еи УСт р, ЕСг у, а а отношение эквивалентности графов. Через Я или обозначим отношение быть изоморфными графами, то есть С1Л если Зср УУ2лУу1це У у,,у, е1иру,ру е2, где фОру,е У2. У у, и Е о яу, и е Е.