Введение к работе
Актуальность темы. Задача генерации графов заданного класса важна как в комбинаторном анализе, так и при решении прикладных проблем в различных областях знания, например, в химии, где структурные формулы соединений могут быть представлены молекулярными графами. В этой области эффективная генерация молекулярных графов необходима, с одной стороны, для традиционной химической практики при формировании гипотез о строении соединения с учетом выявленных данных; прогнозировании структур с заданными свойствами; построении всех возможных продуктов реакции и т. п. С другой стороны, не менее актуально развитие алгоритмов генерации графов для совершенствования компьютерных методов в химии, способствующих решению подобных задач. Наиболее яркие примеры: системы искусственного интеллекта, компьютерного синтеза, помощи исследователю при установлении строения соединений по молекулярным спектрам. При их реализации роль программной компоненты, выполняющей в ограниченное время эффективную, исчерпывающую генерацию требуемых молекулярных графов, трудно переоценить.
Построение полных списков графов с заданными характеристиками имеет и самостоятельное практическое значение. Такне списки, в частности, позволяют проверить различные гипотезы о существовании графов с определенными свойствами, оценить информативность используемых н вновь предложенных инвариантов графов, широко применяемых в том числе и для решения прикладных задач.
Цель работы состоит в создании эффективного алгоритма и программы генерации из множества помеченных вершин с заданной валентностью всех связных молекулярных графов, содержащих заданный набор непересекающихся фрагментов.
Научная новизна работы заключается в разработке эффективного алгоритма генерации всех связных неизоморфных молекулярных графов (их канонических матриц смежности) из множества помеченных вершин с заданной валентностью. Найдены условия, позволяющие сократить перебор при проверке сильной каноничности частнчно-заполненных матриц. Предложен способ задания информации о структурных фрагментах, обеспечивающий эффективное построение всех молекулярных графов, содержащих заданный набор непересекающихся фрагментов. Сформулированы н проверены новые приемы ранжирования генерируемых молекулярных графов и сокращения избыточной информации.
Практическая ценность работы определяется тем. что на основе
— 4 —
предложенного алгоритма генерации молекулярных графов разработана программа GENM, которая включена в состав систем для установления строения органических соединении по молекулярным спектрам: КОМПАС п CliemArt (НИОХ СО РАН, Новосибирск), РАСТР (ВНИИОС, Москва). Программа GENM может использоваться и как средство пользователя (химика, математика), и как необходимый инструментарий, позволяющий выдвигать и проверять новые приемы в решении прикладных химических задач.
Апробация работы. Основные результаты работы представлены на на VI и VIII Всесоюзных конференциях «Использование вычислительных машин в спектроскопии молекул и химических исследованиях» (Новосибирск. 1983. 1989), III Всесоюзном совещании «Методы и программы решения оптимизационных задач на графах и сетях» (Ташкент, 1984), II Всесоюзной конференции «Математические методы и ЭВМ в аналитической химии» (Москва, 1991), IX Всесоюзной конференции «Химическая информатика» (Черноголовка, 1992), II Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 1996) и др.
Публикации. По теме; диссертации опубликовано 15 работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, выводов, списка литературы из 84.наименований, приложенных актов о внедрении. Общий объем диссертации — 79 страниц.
