автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и программные средства для различения расположения фрагментов графовых моделей систем

На правах рукописи

Незнанов Алексей Андреевич

Методы и программные средства для различения расположения фрагментов графовых моделей систем

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва, 2005

Работа выполнена на кафедре Прикладной математики Московского Энергетического Института (Технического Университета)

Научный руководитель: кандидат технических наук, доцент

Кохов Виктор Алексеевич

Официальные оппоненты: доктор технических наук, доцент

Фальк Вадим Николаевич

кандидат технических наук, доцент Грызунов Аркадий Борисович

Ведущая организация: Всероссийский институт научной и технической

информации (ВИНИТИ), г. Москва.

Защита состоится 23 декабря 2005 г.

на заседании диссертационного совета Д 212.157.01

при Московском Энергетическом институте (Техническом Университете)

по адресу: 111250, Москва, Красноказарменная ул., д. 17 (ауд. Г-306)

С диссертацией можно ознакомиться в библиотеке

Московского Энергетического Института (Технического Университета).

Отзывы в двух экземплярах, заверенные печатью организации, просьба направлять по адресу: 111250, г. Москва, ул. Красноказарменная, д. 14, Ученый Совет МЭИ (ТУ).

Автореферат разослан « » ноября 2005 г.

Ученый секретарь кандидат технических наук, профессор

Ладыгин И.И.

Общая характеристика работы

Актуальность темы работы.

Графовые модели систем (ГМС) - математические модели структур систем. Использование компьютерной техники для анализа и синтеза ГМС позволило сделать качественный скачок в структурном анализе и привело к развитию прикладной теории графов. Однако особую роль методы прикладной теории графов играют именно в развитии информационных технологий (теории трансляции, оптимизации программ, организации сложных структур данных, визуализации данных, построении человеко-машинных интерфейсов и др.).

Одним из основных классов задач прикладной теории графов является класс задач различения графов и различения расположения фрагментов графов. История развития методов решения задач различения графов насчитывает более 50 лет. В настоящее время в решении задач распознавания изоморфизма графов, распознавания изоморфного вложения графов и смежных с ними задач достигнут большой теоретический и практический прогресс. Но задачи различения расположения фрагментов графов, более сложных, чем вершины, изучены намного слабее. Исследование расположения фрагментов графов актуализировалось в конце 80-х годов прошлого века в связи с развитием приложений химической теории графов ((¿БАВ.-анализа, £УУУ?-анализа и др.), правдоподобных рассуждений, структурного распознавания образов, структурной лингвистики. Эти исследования шли в достаточно узких областях (например, большинство предложенных топологических индексов явно или неявно учитывали расположение простейших фрагментов) и несистематически. Не существует даже устоявшейся терминологии, пригодной как для теоретических, так и для прикладных исследований.

Учёт расположения фрагментов ГМС наполняет новым содержанием отношения «подсистема-надсистема». Задачи различения расположения фрагментов ГМС обобщают задачи различения ГМС, принимая во внимание надсисте-му, в которую входят рассматриваемые фрагменты. Решение этих задач позволяет исследовать отношения эквивалентности и толерантности ГМС с учётом расположения фрагментов, расширяет возможности подструктурной характе-ризации ГМС. Особенно ярко различия в расположении фрагментов проявляются в симметрии (асимметрии) расположения фрагментов. Учёт симметрии -общеметодологический принцип повышения эффективности компьютерной обработки структурной информации, как в задачах анализа, так и синтеза структур.

Работа продолжает исследования научного руководителя диссертанта -Кохова В.А., которые привели к созданию новой научной дисциплины «структурный спектральный анализ систем» (СС-анализ). Выделены пять основных классов задач СС-анализа, среди которых - класс задач различения расположения фрагментов в графе и различения графов с учётом расположения фрагментов. __

РОС НАЦИОНАЛЬНАЯ | БИБЛИОТЕКА [

9« ЩшжРОУ

Цель работы. Цель диссертационной работы - разработка, программная реализация и исследование методов различения расположения фрагментов в ГМС и методов различения FMC с учётом расположения фрагментов на основе различных отношений эквивалентности. Это позволит повысить эффективность компьютерных методов анализа сходства ГМС и широко использовать их в научных и прикладных исследованиях, связанных со структурным спектральным анализом систем.

Решаемые задачи. Для достижения поставленной цели в работе решаются следующие задачи:

1. Развитие переборно-группового и структурно-характеристического подходов к решению задач различения расположения фрагментов (РРФ) в графе.

2. Разработка алгоритмов решения задач из класса РРФ, использующих эти подходы.

3. Создание эффективного специализированного метода в рамках трансграфового подхода к решению задач из класса РРФ для цепных фрагментов.

4. Повышение эффективности решения базовых задач СС-анализа (таких как поиск всех канонических изоморфных вложений, поиск максимального изоморфного пересечения, декомпозиция графа на неизоморфные фрагменты и др.) при помощи учёта симметрии расположения фрагментов в графе.

5. Реализация разработанных алгоритмов в виде подсистем АСНИ «GraphModel Workshop» (GMW) и программных средств учебного назначения.

6. Исследование разработанных алгоритмов и их реализаций, установление границ применимости, определение асимптотических оценок вычислительной сложности, сравнение с ранее существующими алгоритмами.

7. Применение реализованных подсистем GMW для получения теоретических и прикладных результатов, использование в учебном процессе.

Научная новизна. Показана перспективность и эффективность учёта расположения произвольных фрагментов при решении задач структурного анализа с использованием вычислительной техники. Для этого:

1. Разработан эффективный алгоритм канонизации представления помеченного фрагмента в топологии графа на основе сильного порождающего множества группы автоморфизмов фрагмента.

2. Развит и углублён переборно-групповой подход к решению задач из класса РРФ на основе Мрупп, индуцированных группой автоморфизмов графа.

3. Предложена и реализована полная схема характеризации расположения произвольных фрагментов графа (от построения баз помеченных

фрагментов до анализа математических моделей характеризации рас-

1 . t

положения фрагментов) с точностью до орбит ¿-групп в рамках переборно-группового и структурно-характеристического подходов.

4. Реализован трансграфовый подход к различению расположения цепных фрагментов путём различения вершин графа расположения цепей.

5. Методология решения базовых задач СС-анализа путём монотонного расширения частичных решений, развитая Грызуновым А.Б., впервые дополнена универсальным механизмом эффективного анализа стационарных подгрупп группы автоморфизмов графа.

6. Обобщены и реализованы итерационные алгоритмы усиления чувствительности структурных инвариантов вершин графов в базисе произвольных фрагментов на основе g-моделей, позволившие резко повысить чувствительность структурных инвариантов.

7. Получены новые теоретические результаты исследований расположения фрагментов в графе, проведённые в АСНИ GMW (в особенности -исследований характеристик симметрии транзитивных графов, являющихся моделями топологий вычислительных комплексов и сетей, и других семейств ГМС с ярко выраженной симметрией).

Практическая полезность. Результаты работы (в особенности программные комплексы) могут быть использованы для повышения эффективности и качества компьютерной обработки данных, представленных в виде ГМС.

Учёт расположения фрагментов ГМС позволит: повысить эффективность анализа семантических сетей и качество структурной аналогии при проведении правдоподобных рассуждений в системах под держки принятия решений; повысить качество оценки надёжности и живучести при проектировании топологий вычислительных сетей и сред; использовать более широкий спектр отношений эквивалентности и толерантности структур в приложениях структурной информатики, химической структурной информатики и структурного распознавания образов.

Методы исследований и достоверность результатов. Задачи, поставленные в работе, решаются с помощью методов теории графов, прикладной теории графов, теории групп, теории анализа вычислительной сложности алгоритмов, анализа и построения эффективных алгоритмов и др. В работе существенно использованы результаты, которые получили Кохов В.А, Фараджев И.А., Грызунов А.Б., Ткаченко C.B., Скоробогатов В.A., J. R. Ulimann, В. D. McKay, G. F. Royle, P. Willett, E. Luks, L. E. Druffel.

Основой получения новых научных результатов являются объёмные вычислительные эксперименты. При малой сложности исходных данных результаты вычислительных экспериментов на тестовых наборах исходных данных совпадают с известными результатами. При обработке сложных исходных данных сравнивались результаты, полученные различными методами решения одной и той же задачи.

Реализация результатов. Работа выполнялась в соответствии с проектом ГКНТ России «Новые принципы и методы получения чистых веществ и материалов» макропрограмма 10.2 «Разработка математических основ и программных средств химической информатики» тема 10.2.3 «Построение алгоритмов и создание программ быстрой обработки и извлечения физико-химической информации» и зарегистрированной темой НИР МЭИ (ТУ) № 1147970. Разработанные программные средства используются в учебном процессе и научно-исследовательской работе кафедры Прикладной математики МЭИ (ТУ), кафедры «Информационные системы» МГТУ «Станкин» и кафедры «Компьютерные системы автоматизации производства» МГТУ им. Н.Э. Баумана. Модели, методы и программные компоненты используются в производственном процессе и исследовательской работе ООО «Фирма Перспектива». АСНИ «Graph Model Workshop» («Мастерская граф-моделей») зарегистрирована в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (СВИДЕТЕЛЬСТВО № 2005612847 от 2.11.2005 г.).

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на международных научно-технических конференциях студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА» (с 6-ой по 11-ую, г. Москва, 2000-2005 гг.), на международных форумах информатизации МФИ-2001 - МФИ-2005 (международные конференции «Информационные средства и технологии», г. Москва, 2001-2005 гг.), на научной сессии МИФИ (г. Москва, 2004 г.), на десятой национальной конференции по искусственному интеллекту с международным участием КИИ-2004 (г. Тверь, 2004 г.), на первом всероссийском совещание НМС по информатике при Минобразования и науки Российской Федерации «Актуальные проблемы информатики в современном российском образовании» (г. Москва, 2004 г.).

Личный вклад диссертанта. Работа продолжает развитие методов структурного спектрального анализа, разработанных Коховым В.А. Диссертантом пройден путь от анализа задач до создания прикладных программ. Личный вклад диссертанта состоит в разработке эффективных методов решения задач различения расположения фрагментов в графе и реализации эффективных программных средств в рамках единой методологии решения базовых задач структурного спектрального анализа, а также проведении научных исследований, использующих эти средства.

Публикации. Основные результаты, полученные в процессе выполнения диссертационной работы, опубликованы в 21 печатной работе в виде справочника, учебно-методического пособия, паспортов программных продуктов, докладов и тезисов докладов.

Структура и объём работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы (123 наименования) и приложений. Диссертация содержит 169 страницы машинописного текста.

Содержание работы

Во введении обоснована актуальность темы диссертационной работы, поставлены цели и задачи исследований, сформулированы научная новизна и практическая значимость, приведено краткое содержание работы по главам.

В первой главе рассматриваются основные понятия, связанные с исследованием расположения фрагментов ГМС и формулируются основные решаемые задачи. При этом используется следующая терминология.

Абстрактный тип (7) - произвольный обыкновенный граф, определённый с точностью до автоморфизма. Группу его вершинных автоморфизмов (также с точностью до изоморфизма) обозначим через Аш{{).

Граф / назовём фрагментом графа й, если I изоморфно вкладывается в С в некотором смысле. В большинстве случаев будем считать, что смысл отношения изоморфного вложения определён заранее. В данной работе рассматриваются в основном два типа вложения:

1) в смысле подграфа (обозначение - <Л>);

2) в смысле произвольного фрагмента (обозначение - «А»).

Помеченным графом называется граф, с множеством вершин которого взаимно однозначно сопоставлено множество пометок, то есть каждая вершина которого имеет уникальный атрибут. Наличие пометок будем обозначать верхним индексом «"V Понятие пометок вершин графа отличается от понятия нумерации (идентификации) вершин с целью хранения структурной информации

Помеченным фрагментом/^" типа I графа С назовём помеченный граф 1(1/, пометки которого соответствуют вершинам графа С, образующим (вместе с некоторыми инцидентными им рёбрами) часть графа С, изоморфную Л Через /^'(6)= {,7, /"■"»>} обозначим множество всех помеченных фрагментов типа {графа О.

Для различения абстрактного типа и типов реальных фрагментов графа будем называть тип фрагмента с заданной нумерацией вершин идентификационным типом. Специального обозначения вводить не будем, так как из контекста обычно ясно, введена нумерация вершин или нет. Если на множестве вершин абстрактного типа фрагмента г и графа С задана нумерация, то помеченный фрагмент графа/"'" может быть представлен различными изоморфными вложениями - отображениями номеров вершин г в номера вершин б. Число изоморфных вложений, представляющих один и тот же помеченный фрагмент графа, равняется порядку группы автоморфизмов абстрактного типа (| Лн/(г) |).

Помеченный фрагмент удобно представлять одним из изоморфных вложений, которое назовём каноническим. Каноническим будем считать то из изоморфных вложений, образующих фрагмент/®' графа С, у которого список номеров вершин графа й, в порядке нумерации вершин типа фрагмента лексикографически минимален. Переход от неканонического представления помеченного фрагмента к каноническому назовём канонизацией представления фрагмента. Таким образом, установлено однозначное соответствие между помеченными фрагментами и каноническими изоморфными вложениями.

Формулировка задач из класса задач различения расположения фрагментов (РРФ) проводится на базе понятия /-группы графа, индуцированной группой вершинных автоморфизмов и отражающей симметрию расположения фрагментов типа / в графе.

/-автоморфизмом графа Э называется подстановка £ на множестве помеченных фрагментов типа / графа (7 (или канонических изоморфных вложений) /^'((7), индуцированная некоторым вершинным автоморфизмом g графа й. В процессе индуцирования помеченный фрагмент е ^'((Т), представленный каноническим изоморфным вложением (уь у2, ..., у„) графа (7, переходит в помеченный фрагмент/®', полученный канонизацией вложения {щ, и2, ..., и„), где и, = г е [1, и], п - число вершин фрагмента.

Группой I-автоморфизмов графа С (т!и/((7), /-группой) называется группа подстановок, носителем которой является всё множество /-автоморфизмов для данного а групповой операцией - операция произведения (композиции) подстановок.

В работе исследуются следующие базовые задачи (см. таблицу 1):

• различения расположения однотипных фрагментов (РРОФ) типа / по отношению принадлежности одной орбите /-группы и автоморфного разбиения множества однотипных фрагментов (АРМОФ);

• различения расположения произвольных фрагментов (РРФ) по отношениям между орбитами /-групп на основе операции вложения;

• различения расположения фрагментов относительно выделенного по отношению принадлежности одной орбите фиксатора /-группы.

Таблица I

Варианты задач различения графов и различения расположения фрагментов в графе

№ Обозначение Задача

1. Различение пары графов

1.1 Изоморфизм И (?2

1.2 Изоморфизм <?1 подграфу О: (вложение в смысле подграфа)

1.3 Изоморфизм С] любой части ф (вложение в смысле произвольного фрагмента)

2. Различение расположения пары фрагментов типа /1, Л

2.1 Автоморфное расположение/®/ и/®2( е Е(С)

2.2 Расположение с вложением /®" в/®'2 в смысле подграфа

2.3 уда уда Расположение с вложением в/®" в смысле произвольного фрагмента

3. Различение расположения пары фрагментов относительно фрагмента ^

3.1 Л -гЛ Автоморфное расположение/®]' и/*7^' 6 ДО) относительно f

3.2 уда Расположение с вложением /®" в/1"2 в смысле подграфа отн./7-'

3.3 уда сл/уда Расположение с вложением /®" в/'-"2 в смысле произвольного фрагмента относительно

Например, задача различения расположения двух однотипных помеченных фрагментов/^',,/^ типа / в графе <7 определяется следующими параметрами: РРОФ = < <7,/®'*/% где С - обыкновенный граф (С = (V, Е), | V | =р, \ Е \ = д);

.Л в (>?*" - множество всех помеченных фрагментов типа /, вкладываемых в С? в некотором смысле или, что то же, множество всех канонических изоморфных вложений (вСв некотором смысле);

- отношение принадлежности к одной орбите /-группы (группы автоморфизмов фрагментов типа /).

Решением задачи РРОФ является ответ на вопрос, связаны ли/®, и отношением то есть, принадлежат ли у^',- и /"у одной и той же орбите /группы. В такой постановке РРОФ является задачей распознавания свойств.

Обобщением задачи РРОФ является задача различения расположения двух помеченных фрагментов /1>п11 ]<1>й] типов /1 и /2 в графе (7. Она определяется следующими параметрами:

РРФ = <СЛ^/%£1сй>, где

/№\ е /)а1 е ^ (7*5'1 и - множества всех помеченных фрагментов типов /1 и /2, вкладываемых в С в некотором смысле);

- отношение «элемент орбиты помеченного фрагмента/'7'"1, изоморфно вкладывается в элемент орбиты помеченного фрагмента/*7""2,», то есть Vf■>'ix е ОЛ * ЩАи^О),^) : с,

где 0( Ли/^С),/®') - орбита /1>' относительно /-группы.

Заметим, что задачи РРОФ и РРФ обобщают задачи распознавания изоморфизма графов (РИГ) и изоморфного вложения графов (РИВГ) соответственно. ^-эквивалентность - предельный случай всех остальных отношений эквивалентного расположения помеченных фрагментов (т-эквивалентности), так же, как отношение «быть изоморфными» - предельный случай всех отношений эквивалентности графов, ^-эквивалентность служит для анализа чувствительности (оценки полноты) инвариантов фрагментов, используемых при решении задач из класса РРФ.

Для решения задач из класса РРФ выделены следующие подходы.

1. Переборно-групповой. Основан на прямом анализе /-групп и обеспечивает получение точного решения задач установления ^-эквивалентного расположения помеченных фрагментов. При его реализации используются последние достижения в построении и исследовании порождающих множеств групп автоморфизмов графов и разработки автора.

2. Структурно-характеристический. Основан на анализе структурных и числовых инвариантов и обеспечивает как приближённое (для графов общего вида), так и точное (для более узких классов графов) решение задач установления ^-эквивалентного расположения помеченных фрагментов. Однако главное преимущество этого подхода в том, что он позволяет исследовать широкий класс отношений т-эквивалентности на множестве помеченных фрагментов графа и применяется для анализа сложности и сходства графов, прорисовки диаграмм и др.

3. Трансграфовый. Основан на сведении задачи различения расположения сложных фрагментов графа к задаче различения расположения вершин другого графа (графа расположения фрагментов - ГРФ). Этот подход

позволяет наглядной визуализировать помеченные фрагменты в виде вершин ГРФ.

Во второй главе рассматривается переборно-групповой подход к решению задач различения расположения фрагментов, основанный на анализе индуцированных представлений группы автоморфизмов графа (ГАГ). Предлагается общая схема практического использования данного подхода для характериза-ции расположения произвольных фрагментов с точностью до орбит i-rpynn. Она состоит из двух этапов: на первом этапе производится поиск орбит /-групп (или фиксаторов/стабилизаторов Мрупп) исследуемых типов фрагментов, а на втором - анализируется матрица пересечений орбит помеченных фрагментов.

Первый этап может включать в себя построение баз исследуемых помеченных фрагментов, для чего существует три способа:

1. Построение баз всех однотипных помеченных фрагментов на основе алгоритма поиска всех канонических изоморфных вложений фрагмента в граф (ПВКИВ). Применяется, если априори задан базис структурных дескрипторов (СД). Определение того, что элемент базиса является фрагментом исследуемого графа, производится процедурой ПВКИВ.

2. Декомпозиция графа на неизоморфные фрагменты (ДГНФ) с последующим запуском процедур ПВКИВ. Применяется, если исследуемые типы фрагментов задаются свойствами собственных фрагментов исследуемого графа и их число мало по сравнению с общим числом собственных фрагментов.

3. Декомпозиция графа на помеченные фрагменты. Применяется, если исследуемые типы фрагментов задаются свойствами собственных фрагментов исследуемого графа и их число велико.

При программной реализации работа идёт только с порождающими множествами групп автоморфизмов специального вида, не прибегая к использованию полных групп. Приводится оригинальный эффективный алгоритм канонизации представления помеченного фрагмента, использующий порождающее множество, содержащее в худшем случае не более (р/(р/ - 1) / 2) автоморфизмов, где pf- число вершин фрагмента. Он имеет квадратичную оценку асимптотической временной и емкостной сложности в худшем случае. Этот алгоритм используется во всех случаях обработки помеченных фрагментов, в том числе и при использовании других подходов. Для графа в худшем случае используется либо (рс - 1), либо (рс (pa - 1) / 2) автоморфизмов, где pG - число вершин графа, в зависимости от решаемой задачи.

Второй этап в общем виде заключается в построении и анализе матрицы пересечений орбит двух фрагментов (МПОФ). МПОФ содержит информацию о значениях характеристики у(©'\, 0й,) (у - некоторый коэффициент сходства или различия орбит помеченных фрагментов), для всех упорядоченных пар орбит /-групп (©",■, 0й,) для фрагментов типов /1 и (1. Анализ МПОФ позволяет охарактеризовать расположение всех фрагментов типов t\ и й в графе (рис. 1).

Матрица пересечений орбит фрагментов типа rl (строки) и /2 (столбцы) (максимум коэффициента сходства Л/573):

1 2 3

1 0,75000000 0,52083333 0,75000000

2 0,18750000 0,75000000 0,52083333

Л о— Тип фрагмента (1 Матрица пересечении орбит фрагментов типа fl и /2 (максимум коэффициента различия MDB):

1 2 3

1 0,81250000 0,97916667 0,97916667

2 0,97916667 1,00000000 1,00000000

Тип фрагмента il

В графе G две орбиты фрагментов типа /1: 1 - (1,2,3), (3,4,5); 2 - (1,2,6), (4,5,7), и три орбиты фрагментов типа /2: 1 -(1,4,3,5), (2,4,3,5), (4,1,3,2), (5,1,3,2); 2 - (3,1,2,6), (3,2,1,6), (3,4,5,7), (3,5,4,7); 3 - (6,1,2,3), (6,2,1,3), (7,3,4,5), (7,3,5,4)). Построим МПОФ типов й и /2, где характеристиками пересечения орбит являются: максимум коэффициента сходства MSB = (р(МСГ(/"„/'\)) + qiMCFif",,/'2^))2

0>(/",) + ?(/", )ХХЛ) + ?(Л)> , MCF(faj, faj) - максимальная общая часть фрагментов/'', и faj,p- число вершин, q - число рёбер; и максимум коэффициента различия MDTi = (1 - MSB). |:Л" 4 I Граф характеризации расположения орбит фрагментов типов Л и /2 в графе д (максимум коэффициента различия МОВ)

Ряс. 1. Пример »растеризации расположения фрагментов по схеме переборно-группового подхода

Дополнение методов спектрального анализа графов учётом расположения фрагментов на основе переборно-группового подхода резко повышает качество проводимого подструктурного анализа, не понижая границу его применимости. Рис. 2 иллюстрирует это утверждение: верхний график (круги) - время, затрачиваемое на получение помеченных фрагментов, нижний (треугольники) -время анализа г-групп. Видно, что анализ г-групп занимает малую часть времени, потраченного на получение помеченных фрагментов. Однако область применения переборно-группового подхода в чистом виде ограничена. Во-первых, помеченные фрагменты могут не пересекаться, в отличие от графов, у которых всегда есть общий фрагмент. Во-вторых, анализ г-групп не даёт никакой новой информации о тождественных графах по сравнению с ГАГ. Поэтому на практике методы переборно-группового подхода либо применяются для анализа ГМС с ярко выраженной симметрией, либо дополняют методы структурно-характеристического подхода, предлагая уникальную возможность и в его рамках анализировать расположение фрагментов с точностью до орбит Мрупп.

Рис. 2. Сравнение времени, затрачиваемого на построение баз помеченных фрагментов и на анализ /-групп (ось X - графы с равномерно растущим числом вершин от 30 до 990, число фрагментов также растёт линейно, ось У - время работы в миллисекунд ах)

В третьей главе рассмотрен структурно-характеристический подход к решению задач различения расположения фрагментов, основанный на анализе структурных и числовых инвариантов фрагментов. Описывается его практическая реализация на основе построения и исследования g- и ¿-моделей графа (математических моделей характеризации расположения фрагментов в графе, предложенных Коховым В.А.) в априори заданных базисах СД. Этап получения баз помеченных фрагментов полностью совпадает с описанным при реализации переборно-группового подхода. Но далее производится построение g- или Ь-модели исследуемого графа и анализ структурных или числовых характеристических инвариантов помеченных фрагментов, g- и ¿»-модели представляют собой двудольные графы с весами (соответствующими помеченным фрагментам, их классам или типам) на вершинах левой и правой доли и рёбрах, некоторые их части являются структурными инвариантами помеченных фрагментов, а интегральные свойства этих частей - числовыми инвариантами. Использование g-и ¿-моделей позволяет построить стратифицированную систему отношений т-эквивалентности помеченных фрагментов графа, монотонно изменяющихся с изменением базисов СД.

Для усиления чувствительности локальных структурных инвариантов автором разработан и реализован универсальный метод уточнения разбиения множества вершин графа на классы эквивалентности с использованием g-модели с произвольной правой частью и наличием одновершинных фрагментов в левой части. Процедура итерационного уточнения разбиения (ИУР) позволяет уточнять приближение не только к орбитам группы автоморфизмов, но и к орбитам её стационарных подгрупп (фиксаторов/стабилизаторов). Кроме универсальной процедуры ИУР, использующей произвольную £-модель, созданы более эффективные варианты, использующие ^-модели в базисах цепей и циклов. В этих вариантах исключено явное использование группы автоморфизмов

фрагмента. Использование процедуры ИУР позволяет уменьшить размерность ^-моделей и ослабить требования к базисам СД при сохранении качества решения задач различения расположения фрагментов. Как показывают эксперименты, базиса цепей длины от 1 до 5 уже достаточно для определения орбит практически всех графов, за исключением нескольких семейств регулярных графов. Таким образом, ИУР может во многих случаях заменить анализ ГАГ и /-групп.

Отдельно рассмотрен специальный подкласс ^-моделей - графы расположения цепей (ГРЦ), которые представляют собой иерархические ^-модели с равными долями в базисе связных цепей. Приведён алгоритм построения ГРЦ, линейный относительно числа анализируемых цепей исходного графа. Орбиты вершин ГРЦ при некоторых условиях соответствуют орбитам цепей исходного графа. Это позволяет реализовать трансграфовый подход к решению задач из класса РРФ для цепных фрагментов. Поставлена задача построения графов расположения фрагментов (ГРФ) для расширения трансграфового подхода на более широкий класс фрагментов. Хотя эффективность трансграфового подхода оказывается ниже, чем других подходов (в первую очередь из-за большого размера ГРФ), использование ГРФ облегчает работу с помеченными фрагментами

Рис. 3. Примеры визуализации симметрии расположения цепиых фрагментов (цифры на вершинах ГРЦ обозначают длину соответствующих цепей исходного графа) и визуализации вкладов цепных фрагментов в общую сложность графа

В четвёртой главе описывается авторский вклад в развитие АСНИ «Graph Model Workshop» (созданной совместно с Коховым В.А. и Ткаченко C.B.) и её функциональное наполнение, рассматриваются вопросы повышения эффективности решения задач структурного спектрального анализа и авторские алгоритмы, обсуждаются практические вопросы реализации программных средств и проведения вычислительных экспериментов. АСНИ «Graph Model Workshop» (далее - GMW) предназначена для проведения научных исследований, объектом которых являются графовые модели систем, включая подготовку исходных данных, автоматическое проведение вычислительных экспериментов и обра-

ботку их результатов (рис. 4). АСНИ работает под управление ОС Windows 98-ХР. На базе GMW создаются программные средства для решения прикладных задач и программные средства учебного назначения. GMW является открытой системой с многоуровневым интерфейсом для подключения программных расширений, которые могут повышать функциональность всех операций, выполняемых в АСНИ. Большинство программных средств, созданные автором, входят в состав GMW и образуют её подсистемы. С их помощью можно проводить следующие вычислительные эксперименты: проверка базы графов на наличие изоморфных и выделение подмножества попарно неизоморфных графов; попарное сравнение характеристик симметрии (числа симметрии и др.) графов из двух баз; построение по заданной базе графов новой базы со структурными инвариантами исходных графов; многоэтапный эксперимент по характеризации расположения фрагментов графов по схеме переборно-группового подхода; многоэтапный эксперимент по характеризации расположения фрагментов графов по схеме структурно-характеристического подхода; построение и анализ информационных вектор-индексов сложности и вектор-индексов структурной спектральной сложности в произвольном базисе структурных дескрипторов.

Разработки автора также используются в экспериментах по анализу сходства графов, проводимых совместно с Ткаченко С.В, и средствах структурного поиска (иерархического поиска в базах структурной информации).

;:,MdC I«?p£Kdfl Т рДф МОДСЛРЙ ;';..f C^PTt-Bbn? ТРП0/)0Г;ИИ :gn!Î;].

Я! Феия Правка Вт Sua Запуос Сервис Оюа Спрвви

« х t- m я

eftъ

шшш

- a х

щ 1

23 I fê?

Регулярная сетевая топология

J Верами; 9

Рёбер: 18

Рис. 4. Главное окно АСНИ «Graph Model Workshop» с открытой базой топологий КС Подсистемы GMW создавались в основном в среде Borland Delphi, частично - в среде Microsoft Visual С++ .NET, и представляют собой набор динамически компонуемых библиотек (таблица 2).

Таблица 2

Параметры основных программных библиотек автора, содержащих расширения (ТШР

№ Библиотека Количество экспортируемых функций объем авторского исходного кода, КБ Количество компилируемых строк кода Объём машинного кода, КБ

Общие модули - 341 - -

1 Основные алгоритмы 168 1672 69552 619

2 Интерактивные расширения (например, анализ ¡-групп) 36 1136 327687 4192

3 Стандартные интерфейсные диалоги (например, ввод базисов СД) 5 138 274564 1953

4 Вспомогательные расширения 39 179 19751 217

Автором реализованы эффективные методы получения и хранения орбит стационарных подгрупп ГАГ, что позволило уменьшить накладные расходы на учёт симметрии графа для сокращения перебора при решении переборных (№>-полных) задач структурного спектрального анализа. Порождающие множества стационарных подгрупп строятся путём модификации сильного ПМ ГАГ, орбиты подгрупп хранятся в словаре на основе чёрно-красного дерева поиска.

Так, по методологии монотонного расширения частичных решений разработаны алгоритмы установления изоморфного вложения и поиска максимального общего фрагмента пары графов. Для симметричных графов время выполнения данных алгоритмов с учётом симметрии уменьшается на несколько порядков (с нескольких часов до секунд). Различные варианты учёта симметрии исследовались при решении задачи декомпозиции графа на неизоморфные фрагменты, причём её решение ускоряется практически для всех классов графов, но менее, чем в два раза. При разработке интерактивных алгоритмов (во время выполнения которых человек указывает направление поиска решения, осуществляемого компьютером с одновременной визуализацией процесса решения на диаграмме графа), учёт симметрии позволил предоставить пользователю наглядную дополнительную информацию о структуре графа и отметить заведомо тупиковые направления поиска. В главе также приводится пример проведения сложного многоэтапного вычислительного эксперимента и анализа его результатов, даётся перечень экспериментов, для автоматического проведения которых автором созданы расширения СМ1У.

Пятая глава содержит информацию о теоретических результатах исследования графовых моделей систем и применении авторских разработок в учебном процессе и прикладных областях.

Приведены результаты объёмных вычислительных экспериментов (обработано более 15 ООО ООО графов). Исследовались: симметрия расположения вершин и более сложных фрагментов графов различных классов; связь симметрии графа с его сложностью; отношения эквивалентности и толерантности графов на основе и ¿-моделей; роль итерационных процедур в усилении чувствительности структурных инвариантов графов (особое вниманию уделено §-моделям в базисе простых цепей); методы структурного поиска ГМС с учё-

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

В соавторстве с Коховым В.А. и Ткаченко C.B. на базе АСНИ GMWсоздано четыре программных средства учебного назначения (ПСУН). ПСУН «СТРИН» и ПСУН «Полигон алгоритмов структурной информатики» обеспечивают компьютерную поддержку раздела «Основы структурной информатики» дисциплины «Информатика». ПСУН «Интегрированная среда визуального и алгоритмического решения задач на графовых моделях систем» и ПСУН «Интегрированная среда исследования эффективности алгоритмов обработки графовых моделей систем» обеспечивают компьютерную поддержку структурного анализа и синтеза при выполнении лабораторных работ, курсовых проектов, типовых расчётных заданий и УНИР студентов старших курсов. Информация о них доступна в Интернете по адресу www.graphmodel сот. Учебно-методические комплексы, в которые входят перечисленные выше ПСУН, удостоены диплома П степени конкурса на лучшую разработку и внедрение в учебный процесс новых информационных технологий в области обучения, посвященного 75-летию МЭИ (ТУ) в апреле 2005 года.

В заключении приведены основные результаты работы.

Основные результаты работы

1. Рассмотрены задачи, составляющие инвариантное ядро задач различения расположения фрагментов (РРФ) в 1рафе для отношений Е,-эквивалентности и ^-эквивалентного вложения, а также расширяющие их задачи различения т-эквивалентного расположения фрагментов в графе, проанализированы подходы к их решению.

2. Развита методология переборно-группового подхода к характеризации расположения фрагментов в графе. В рамках данной методологии разработаны эффективные алгоритмы решения задач из класса РРФ, включая алгоритмы:

1) канонизации представления помеченного фрагмента;

2) построения и анализа ПМ ГАГ и её стационарных подгрупп;

3) построения и анализа ПМ /-группы и её подгрупп;

4) построения и анализа матрицы пересечения фрагментов.

Это позволило характеризовать взаимное и относительное расположение произвольных фрагментов с точностью до орбит /-групп (то есть с учётом симметрии исследуемого графа).

3. Разработаны алгоритмы решения задач из класса РРФ в рамках структурно-характеристического подхода, включая алгоритмы:

1) построения и анализа g- и ¿-моделей графов общего вида, в отличие от алгоритмов, разработанных Ткаченко C.B., позволяющие априори задавать базисы структурных дескрипторов;

2) построения и анализа графов расположения цепей (специализированная версия с повышенной эффективностью);

3) итерационного уточнения классов эквивалентности вершин по g-модели с произвольной правой частью и специализированные, с повышенной эффективностью, по g-модели в базисе цепей и циклов. Реализованы универсальные методы учёта симметрии для сокращения перебора при решении Л7>-полных задач структурного анализа. Особую роль данные методы играют в методологии монотонного расширения частичных решений. В рамках данной методологии разработаны авторские версии алгоритмов поиска максимального общего фрагмента двух графов в смысле подграфа (на порядки возросла эффективность анализа симметричных графов, например, транзитивных, являющихся моделями топологий вычислительных комплексов и сетей) и поиска всех канонических изоморфных вложений фрагмента в граф (на порядки возросла эффективность анализа высоко симметричных фрагментов, например, звёзд и клик). Также учёт симметрии применён при решении задачи декомпозиции графа на неизоморфные фрагменты (заметное повышение эффективности), задачи поиска гамильтоновых цепей и циклов (визуализация симметрии при интерактивном выполнении алгоритма) и других задач. Таким образом, показана значимость учёта симметрии и высокая эффективность методов её учёта. Созданы или расширены подсистемы АСНИ «Graph Model Workshop> (среди них «Различение графов», «Симметрия расположения фрагментов графов», «g- и ¿»-модели графов», «Сложность графов», «Декомпозиция графов на неизоморфные фрагменты», «Случайная генерация и трансформация»). АСНИ «Graph Model Workshop» (GMW) зарегистрирована в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (СВИДЕТЕЛЬСТВО №2005612847 от 2.11.2005 г.) Программные разработки содержат более 3 МБ авторского исходного кода и более 8 МБ исполняемого кода. На основе подсистем GMW созданы четыре программных средства учебного назначения для компьютерной поддержки раздела «Основы структурной информатики» дисциплины «Информатика» и поддержки дисциплин «Структурная информатика», «Дискретная математика», «Теория графов и комбинаторика», «Анализ и проектирование эффективных алгоритмов» и др.

Проведены объёмные вычислительные эксперименты с использованием GMW. Их результаты позволили:

1) исследовать характеристики симметрии и построить симметричные диаграммы транзитивных графов степени 4 с числом вершин до 31 (вошедшие в справочник [1]);

2) исследовать структурные и числовые инварианты графов и их фрагментов на основе g- и ft-моделей, предложенные Коховым В.А. (показана эффективность методов анализа сходства графов на их основе);

3) исследовать итерационные процедуры уточнения разбиения множества вершин графа на классы эквивалентности по ^-модели в базисе цепей различной длины (подтвердилось резкое повышение чувствительности структурных инвариантов итерационного типа);

4) выделить графы, обладающих изоморфными примарными подграфами или примарными частичными графами, полученными удалением вершин или рёбер из разных орбит (пример исследования оригинального отношения эквивалентности графов).

Выводы

В работе анализируются и систематизируются задачи различения расположения произвольных фрагментов в графе и подходы к их решению. Задачи различения расположения фрагментов в графе обобщают соответствующие задачи различения графов, а также позволяют впервые поставить задачи различения графов с учётом расположения фрагментов. Эти задачи актуализировались с развитием структурного спектрального анализа систем, их решение необходимо в химической структурной информатике, структурной лингвистике, при исследовании топологий вычислительных систем и сред, распознавании образов и в других прикладных областях.

Особое внимание уделено классам эффективно решаемых задач и повышению чувствительности локальных инвариантов. В результате можно сделать вывод о возможности практического применения методов переборно-группового подхода для исследования графов с числом вершин до 1000 при размере фрагментов до нескольких десятков вершин на современном персональном компьютере. Методы структурно-характеристического подхода, которые требуют построения сложных структурных инвариантов (g- и ¿-моделей), не позволяют исследовать графы такого размера (граница применимости -150 вершин), однако предоставляют разнообразные схемы характеризации расположения фрагментов по большому спектру отношений.

В результате объёмных вычислительных экспериментов показана роль локальных характеристических инвариантов, используемых совместно с процедурами усиления их чувствительности (в данном случае - итерационного уточнения разбиения множества вершин на классы эквивалентности), при анализе интегральных свойств графовых моделей систем.

Методы решения задач различения расположения фрагментов в графе реализованы в подсистемах АСНИ «Graph Model Workshop». Реализация эффективных методов анализа симметрии расположения фрагментов в графе позволила повысить эффективность решения других задач структурного спектрального анализа (для некоторых классов графов на порядки). Этим была подтверждена общеметодологическая значимость учёта симметрии как универсального метода повышения эффективности обработки структурной информации.

Основные работы, опубликованные по теме диссертации:

1. Незнанов A.A., Кохов В.А. Справочник по теории графов. Характеристики симметрии и сложности связных транзитивных графов степени 4 с числом вершин до 30 включительно. — М. Деп. в ВИНИТИ, №1094-В2004,2004.-418 с.

2. Кохов В.А., Ткаченко C.B., Незнанов A.A. Построение алгоритмов и программ быстрой обработки физико-химической информации. — Отчёт по НИР, выполненной на кафедре ПМ. Зарегистрированная тема НИР МЭИ № 1147970,2001.

3. Незнанов A.A., Кохов В.А. Методы анализа симметрии и сложности структур в базисе цепных фрагментов. // Тезисы докладов шестой ежегодной международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА». М.: МЭЩТУ), 2000. - с. 235-236.

4. Незнанов A.A., Кохов В.А. Методы определения изоморфного вложения граф-моделей и их применение для анализа симметрии и сложности систем. // Тезисы докладов седьмой ежегодной международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА». М.: МЭЩТУ), 2001. - с. 264-265.

5. Незнанов A.A., Кохов В.А. Структурная информатика: симметрия структур. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2001), Т.З, Москва, 2001.

6. Незнанов A.A., Кохов В.А. Подсистема «Симметрия фрагментов структур» 1 Ulli «СТРИН-2.0». // Тезисы докладов восьмой ежегодной международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА». М.: МЭЩТУ), 2002. - с.281-282.

7. Ткаченко C.B., Незнанов A.A., Кохов В.А. Компьютерная поддержка курса «Основы Структурной информатики». // Доклады международной конференции «Информационные средства и технологии». (МФИ-2002), Т.2, Москва, 2002. - с. 55-58.

8. Незнанов A.A., Кохов В.А. Методы декомпозиции графов на неизоморфные фрагменты с учётом симметрии. // Тезисы докладов девятой ежегодной международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА». М.: МЭЩТУ), 2003. - с. 300-301.

9. Незнанов A.A., Кохов В.А. Алгебраический подход к анализу симметрии расположения фрагментов графа. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2003), Т.1, Москва, 2003.-е. 216-219.

10. Незнанов A.A., Кохов В.А. Сходство систем в топологии надсистемы. // Научная сессия МИФИ-2004: Сб. науч. трудов. Т.З, М.:МИФИ, 2004. -с. 198-199.

20

05-221 10

11. Незванов A.A., Кохов В.А. Базовые алгоритмы структурной информатики: декомпозиция графов. // Тезисы докладов десятой ежегодной международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА». М.: МЭИ(ТУ), 2004. - с. 326-327.

12. Кохов В.А., Незнанов A.A., Ткаченко С.В. Компьютерные методы анализа сходства графов. // Десятая Национальная конференция по искусственному интеллекту с международным участием. КИИ-2004: Труды конференции. В 3-х т. Том 1. М.: Физматлит, 2004. - С. 162-171.

13. Кохов В.А., Незнанов A.A., Горшков С.А. ППП «СТРИН+»: Подсистема сравнительного анализа структур. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2004), Т.1, Москва, 2004. - с. 215-218.

14. Незнанов A.A., Кохов В.А. Базовые алгоритмы структурной информатики: поиск всех канонических изоморфных вложений фрагмента в граф. // Тезисы докладов одиннадцатой ежегодной международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА». М.: МЭЩТУ), 2005. - с. 347-348.

Подписано в печать &Ь Зак. ЗУО Тир. П. л.

Полиграфический центр МЭИ (ТУ)

111250, г. Москва, ул. Красноказарменная, д. 13

РНБ Русский фонд

19749

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

Актуальность темы работы.

Цель работы

Решаемые задачи.

Научная новизна

Практическая полезность.

Методы исследований и достоверность результатов.

Реализация результатов.

Апробация работы.

Личный вклад диссертанта.

Публикации

Содержание работы по

главам.

1. РАЗЛИЧЕНИЕ РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ КАК НОВЫЙ УРОВЕНЬ ЗАДАЧ РАЗЛИЧЕНИЯ ГРАФОВ.

1.1. Эквивалентность и толерантность графов и расположения их фрагментов.

1.2. Графы, фрагменты и помеченные фрагменты.

1.3. Группы автоморфизмов, индуцированные вершинной группой автоморфизмов {Ani{G)).

1.3.1. Пример t-группы.

1.4. Задачи различения расположения фрагментов в графе.

1.4.1. Задачи различения расположения однотипных фрагментов.

1.4.2. Задачи различения расположения произвольных фрагментов.

1.4.3. Обсуждение постановок задач различения расположения фрагментов.

1.4.4. Сведение задач различения графов к задачам различения расположения фрагментов.

1.4.5. Сводная таблица основных задач различения.

1.4.6. Инвариантное ядро задач различения №1 (ИЯЗР1) в СС-анализе.

1.4.7. Инвариантное ядро задач различения №2 (ИЯЗР2) в СС-анализе.

1.4.8. £,- и т-эквивалентность.

1.4.9. Задачи различения т-эквивалентности расположения фрагментов.

1.5. Подходы к решению задач из ИЯЗР1 и ИЯЗР2.

1.5.1. Систематизация подходов к решению задач из ИЯЗР1.

1.5.2. Сложность и методы решения задач из ЙЯЗР1.

1.5.3. Систематизация подходов к решению задач из ЙЯЗР2.

Выводы и результаты по главе.

2. ПЕРЕБОРНО-ГРУППОВОЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧ РАЗЛИЧЕНИЯ РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ.

2.1. Базовые задачи.

2.1.1. Представление фрагментов в памяти компьютера.

2.1.2. Построение порождающего множества группы автоморфизмов графа.

2.1.3. Вид порождающего множества, используемый в данной работе.

2.1.4. Представление порождающего множества, описанного выше.

2.1.5. Канонизация представления помеченного фрагмента на основе порождающего множества группы автоморфизмов фрагмента.

2.1.6. Построение порождающего множества фиксатора/стабилизатора подмножества вершин графа.

2.2. Построение и исследование ^-групп.

2.2.1. Представление порождающего множества t-группы.

2.2.2. Поиск помеченного фрагмента в базе фрагментов.

2.2.3. Построение порождающего множества t-группы.

2.2.4. Поиск орбит t-группы без построения порождающего множества t-группы.

2.3. Решение задач из класса задач различения расположения фрагментов.

2.3.1. Решение задач различения расположения однотипных фрагментов.

2.3.2. Решение задач различения расположения произвольных фрагментов.

2.3.3. Построение и анализ матрицы пересечения орбит помеченных фрагментов.

2.3.4. Пример характеризации расположения фрагментов в графе.

2.4. Экспериментальная оценка вычислительной сложности алгоритмов.

2.5. Перспективы дальнейшего развития методов переборно-группового подхода.

Выводы и результаты по главе.

3. СТРУКТУРНО-ХАРАКТЕРИСТИЧЕСКИЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧ РАЗЛИЧЕНИЯ РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ.

3.1. Использование структурных инвариантов.

3.2. g-модели и й-модели графа для визуализации и решения задач различения расположения фрагментов графа.

3.3. Построение и исследование g-моделей и й-моделей.

3.3.1. Способы задания базисов структурных дескрипторов.

3.3.2. Определение рёбер и их весов.

3.3.3. Решение задач из класса задач различения расположения фрагментов на основе g-моделей.

3.3.4. Решение задач из класса задач различения расположения фрагментов на основе b-моделей.

3.3.5. Построение отношений эквивалентности и сходства графов на основе g- и b-моделей.

3.4. Построение и исследование графов расположения цепей.

3.4.1. g-модели с равными долями.

3.4.2. Определение графа расположения цепей (ГРЦ).

3.4.3. Эффективный метод построения ГРЦ.

3.4.4. Обозначения ГРЦ.

3.4.5. Алгоритм построения ГРЦ.

3.4.6. Доказательство корректности алгоритма.

3.4.7. Некоторые свойства ГРЦ.

3.4.8. Пример построения ГРЦ.

3.4.9. Исследование симметрии цепей исходного графа с использованием ГРЦ.

3.4.10. Обобщение ГРЦ для анализа фрагментов других типов.

3.4.11. Результаты экспериментов.

3.5. Усиление чувствительности структурных инвариантов.

3.5.1. Итерационные методы усиления чувствительности.

3.5.2. Итерационное уточнение разбиения множества вершин на классы эквивалентности по g-модели

3.5.3. Параметризация процедуры построения матрицы структурных инвариантов и проведение экспериментов по исследованию чувствительности инвариантов итерационного типа.

3.6. Перспективы развития методов структурно-характеристического подхода.

Выводы и результаты по главе.

4. ПОДСИСТЕМЫ АСНИ «GRAPHMODEL WORKSHOP» ДЛЯ ИССЛЕДОВАНИЯ АЛГОРИТМОВ СТРУКТУРНОГО СПЕКТРАЛЬНОГО АНАЛИЗА СИСТЕМ.

4.1. История создания.

4.2. Общая архитектура АСНИ и место авторских подсистем в ней.

4.3. Программная реализация подсистем.

4.4. Основные расширения АСНИ, реализованные автором.

4.5. Учёт симметрии расположения фрагментов для повышения эффективности решения задач структурного спектрального анализа.

4.5.1. Развитие методологии монотонного расширения частичных решений.

4.5.2. Поиск всех канонических изоморфных вложений.

4.5.3. Максимальное изоморфное пересечение с учётом симметрии.

4.5.4. Декомпозиция графа на неизоморфные фрагменты.

4.5.5. Интерактивный поиск гамильтоновых цепей и циклов.

4.6. Система проведения экспериментов и «полигон» исследования эффективности алгоритмов

4.6.1. Схема эксперимента.

4.6.2. Сохранение результатов.

4.6.3. Анализ результатов.

4.6.4. Пример многоэтапного вычислительного эксперимента.

4.6.5. Вычислительные эксперименты, которые могут проводиться с использованием программных разработок автора.

4.7. Исследование эффективности подходов к решению задач различения расположения фрагментов.

4.7.1. Используемые методики и тестовые данные.

4.7.2. Результаты вычислительных экспериментов.

4.7.3. Границы применимости.

Тема работы: методы и программные средства для различения расположения фрагментов графовых моделей систем.

Актуальность темы работы

Проблема выявления и практического использования взаимосвязи физико-химических свойств систем и процессов, с одной стороны, и их структур, с другой стороны, носит название проблемы структур. Исследование проблемы структур представляет собой одно из непрерывно актуальных направлений развития науки и техники [61, 109, 114]. Объясняется это тем, что проблема структур, наряду с базовыми физическими законами, лежит в основе научно-технической инженерии, обусловленной возрастающими потребностями человечества в самом широком смысле, включая и идеально-познавательную потребность [49]. С проблемой структур связаны задачи установления корреляций вида «структура-свойство», анализа сложности и сходства структур, выполнения эквивалентных структурных преобразований, синтеза конкретных физических и химических структур, изучения динамики и функциональных свойств систем, выявления глобальных свойств через локальные и др. Успешным, но пока не полным решением этих задач объясняются успехи в синтезе молекулярных структур, структур электрических цепей, электронных схем, регулярных топологий вычислительных сетей и сред [43], в проектировании схем программ и др.

Графовые модели систем (ГМС) - математические модели структур систем. Использование компьютерной техники для анализа и синтеза ГМС позволило сделать качественный скачок в структурном анализе и привело к развитию прикладной теории графов. Однако особую роль методы прикладной теории графов играют именно в развитии информационных технологий (теории трансляции, оптимизации программ, организации сложных структур данных, визуализации данных, построении человеко-машинных интерфейсов и др.) [62].

Одним из основных классов задач прикладной теории графов является класс задач различения графов и различения расположения фрагментов графов. История развития методов решения задач различения графов насчитывает более 50 лет. В настоящее время в решении задач распознавания изоморфизма графов, распознавания изоморфного вложения графов и смежных с ними задач достигнут большой теоретический и практический прогресс. Но задачи различения расположения фрагментов графов, более сложных, чем вершины, изучены намного слабее. Исследование расположения фрагментов графов актуализировалось в конце 80-х годов прошлого века в связи с развитием приложений химической теории графов (QSAR-анализа, QRRR-анализа и др.), правдоподобных рассуждений, структурного распознавания образов, структурной лингвистики. Эти исследования шли в достаточно узких областях (например, большинство предложенных топологических индексов явно или неявно учитывали расположение простейших фрагментов) и несистематически. Не существует даже устоявшейся терминологии, пригодной как для теоретических, так и для прикладных исследований. Эта проблема актуализировалась ещё больше после того, как Журавлёв Ю.И. и его ученики [57, 56, 47] с наиболее общих теоретических позиций показали, что при решении задач распознавания выражение глобальных (интегральных) свойств через локальные вполне возможно.

Учёт расположения фрагментов ГМС наполняет новым содержанием отношения «подсистема-надсистема». Задачи различения расположения фрагментов ГМС обобщают задачи различения ГМС, принимая во внимание надсистему, в которую входят рассматриваемые фрагменты. Решение этих задач позволяет исследовать отношения эквивалентности и толерантности ГМС с учётом расположения фрагментов, расширяет возможности подструктурной характеризации ГМС. Особенно ярко различия в расположении фрагментов проявляются в симметрии (асимметрии) расположения фрагментов. Учёт симметрии - общеметодологический принцип повышения эффективности компьютерной обработки структурной информации, как в задачах анализа, так и синтеза структур.

Работа продолжает исследования научного руководителя диссертанта - Ко-хова В.А., которые привели к созданию новой научной дисциплины «структурный спектральный анализ систем» (СС-анализ). Выделены пять основных классов задач СС-анализа, среди которых - класс задач различения расположения фрагментов в графе и различения графов с учётом расположения фрагментов.

Цель работы

Цель диссертационной работы - разработка, программная реализация и исследование методов различения расположения фрагментов в ГМС и методов различения ГМС с учётом расположения фрагментов на основе различных отношений эквивалентности. Это позволит повысить эффективность компьютерных методов анализа сходства ГМС и широко использовать их в научных и прикладных исследованиях, связанных со структурным спектральным анализом систем.

Решаемые задачи

Для достижения поставленной цели в работе решаются следующие задачи:

1. Развитие переборно-группового и структурно-характеристического подходов к решению задач различения расположения фрагментов (РРФ) в графе.

2. Разработка алгоритмов решения задач из класса РРФ, использующих эти подходы.

3. Создание эффективного специализированного метода (в рамках трансграфового подхода) решения задач из класса РРФ для цепных фрагментов.

4. Повышение эффективности решения базовых задач СС-анализа (таких как поиск всех канонических изоморфных вложений, поиск максимального изоморфного пересечения, декомпозиция графа на неизоморфные фрагменты и др.) при помощи учёта симметрии расположения фрагментов в графе (основным механизмом которого является анализ стационарных подгрупп группы автоморфизмов графа).

5. Реализация разработанных алгоритмов в виде подсистем АСНИ «Graph-Model Workshop» (GMW) и программных средств учебного назначения.

6. Исследование разработанных алгоритмов и их реализаций, заключающееся в доказательстве корректности, установлении границ применимости, определении асимптотических оценок вычислительной сложности, сравнении с ранее существующими алгоритмами.

7. Применение реализованных подсистем GMW для получения теоретических и прикладных результатов, использование в учебном процессе.

Научная новизна

В работе показана перспективность и эффективность учёта расположения произвольных фрагментов при решении задач структурного анализа с использованием вычислительной техники. Новыми научными результатами являются:

1. Разработка эффективного алгоритма канонизации представления помеченного фрагмента в топологии графа на основе сильного порождающего множества группы автоморфизмов фрагмента.

2. Развитие и углубление переборно-группового подхода к решению задач из класса РРФ на основе f-групп, индуцированных группой автоморфизмов графа.

3. Реализация полной схемы характеризации распололсения произвольных фрагментов графа (от построения баз помеченных фрагментов до анализа математических моделей характеризации расположения фрагментов) с точностью до орбит f-групп в рамках переборно-группового и структурно-характеристического подходов.

4. Реализация трансграфового подхода к различению расположения цепных фрагментов путём различения вершин графа расположения цепей.

5. Дополнение методологии решения базовых задач СС-анализа путём монотонного расширения частичных решений, развитой Грызуновым А.Б., универсальным механизмом эффективного анализа стационарных подгрупп группы автоморфизмов графа.

6. Обобщение и реализация итерационных алгоритмов усиления чувствительности структурных инвариантов вершин графов в базисе произвольных фрагментов на основе g-моделей, позволивших резко повысить чувствительность структурных инвариантов.

7. Получение новых теоретических результатов исследований расположения фрагментов в графе, проведённых в АСНИ GMW (в особенности -исследований характеристик симметрии транзитивных графов, являющихся моделями топологий вычислительных комплексов и сетей, и других семейств ГМС с ярко выраженной симметрией [105]).

Практическая полезность

Результаты работы (в особенности программные комплексы) могут быть использованы для повышения эффективности и качества компьютерной обработки данных, представленных в виде ГМС.

Учёт расположения фрагментов ГМС позволит: повысить эффективность анализа семантических сетей и качество структурной аналогии при проведении правдоподобных рассуждений в системах поддержки принятия решений; повысить качество оценки надёжности и живучести при проектировании топологий вычислительных сетей и сред; использовать более широкий спектр отношений эквивалентности и толерантности структур в приложениях структурной информатики, химической структурной информатики и структурного распознавания образов.

Методы исследований и достоверность результатов

Задачи, поставленные в работе, решаются с помощью методов теории графов, прикладной теории графов, теории групп, теории вычислительной сложности алгоритмов, анализа и построения эффективных алгоритмов и др. В работе существенно использованы результаты, которые получили Кохов В.А, Фараджев И.А., Грызунов А.Б., Ткаченко С.В., Скоробогатов В.А., J. R. Ullmann, В. D. McKay, G. F. Royle, P. Willett, E. Luks, L. E. Druffel.

Основой получения новых научных результатов являются объёмные вычислительные эксперименты. При малой сложности исходных данных результаты вычислительных экспериментов на тестовых наборах исходных данных совпадают с известными результатами. При обработке сложных исходных данных сравнивались результаты, полученные различными методами решения одной и той же задачи.

Реализация результатов

Работа выполнялась в соответствии с проектом ГКНТ России «Новые принципы и методы получения чистых веществ и материалов» макропрограмма 10.2 «Разработка математических основ и программных средств химической информатики» тема 10.2.3 «Построение алгоритмов и создание программ быстрой обработки и извлечения физико-химической информации» и зарегистрированной темой НИР МЭИ (ТУ) № 1147970. Разработанные программные средства используются в учебном процессе и научно-исследовательской работе кафедры Прикладной математики МЭИ (ТУ), кафедры «Информационные системы» МГТУ «Станкин» и кафедры «Компьютерные системы автоматизации производства» МГТУ им. Н.Э. Баумана. Модели, методы и программные компоненты используются в производственном процессе и исследовательской работе ООО «Фирма Перспектива». АСНИ «Graph Model Workshop» («Мастерская граф-моделей») зарегистрирована в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (СВИДЕТЕЛЬСТВО № 2005612847 от 2.11.2005 г.).

Апробация работы

Основные положения и результаты диссертации докладывались и обсуждались на 6, 7, 8, 9, 10 и 11 международных научно-технических конференциях студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА» (г. Москва, 2000-2005 гг.), на международных форумах информатизации МФИ-2001, МФИ-2002, МФИ-2003, МФИ-2004, МФИ-2005 (международные конференции «Информационные средства и технологии», г. Москва, 2001-2005 гг.), на научной сессии МИФИ (г. Москва, 2004 г.), на десятой национальной конференции по искусственному интеллекту с международным участием КИИ-2004 (г. Тверь, 2004 г.), на первом всероссийском совещание НМС по информатике при Минобразования и науки Российской Федерации «Актуальные проблемы информатики в современном российском образовании» (г. Москва, 2004 г.).

Личный вклад диссертанта

Работа продолжает развитие методов структурного спектрального анализа, разработанных Коховым В.А. Диссертантом пройден путь от анализа задач до создания прикладных программ. Личный вклад диссертанта состоит в разработке эффективных методов решения задач различения расположения фрагментов в графе и реализации эффективных программных средств в рамках единой методологии решения базовых задач структурного спектрального анализа, а также проведении научных исследований, использующих эти средства.

Публикации

Основные результаты, полученные в процессе выполнения диссертационной работы, опубликованы в 21 печатной работе в виде справочника, учебно-методического пособия, паспортов программных продуктов, докладов и тезисов докладов.

Содержание работы по главам

Диссертация состоит из введения, пяти глав, заключения, списка литературы (123 наименования) и приложений.

Выводы

В работе анализируются и систематизируются задачи различения располо-э/сения произвольных фрагментов в графе и подходы к их решению. Задачи различения расположения фрагментов в графе обобщают соответствующие задачи различения графов, а также позволяют впервые поставить задачи различения графов с учётом расположения фрагментов. Эти задачи актуализировались с развитием структурного спектрального анализа систем, их решение необходимо в химической структурной информатике, структурной лингвистике, при исследовании топологий вычислительных систем и сред, распознавании образов и в других прикладных областях.

Особое внимание уделено классам эффективно решаемых задач и повышению чувствительности локальных инвариантов. В результате можно сделать вывод о возможности практического применения методов переборно-группового подхода для исследования графов с числом вершин до 1000 при размере фрагментов до нескольких десятков вершин на современном персональном компьютере. Методы структурно-характеристического подхода, которые требуют построения сложных структурных инвариантов (g- и 6-моделей), не позволяют исследовать графы такого размера (граница применимости - 150 вершин), однако предоставляют разнообразные схемы характеризации расположения фрагментов по большому спектру отношений.

В результате объёмных вычислительных экспериментов показана роль локальных характеристических инвариантов, используемых совместно с процедурами усиления их чувствительности (в данном случае - итерационного уточнения разбиения множества вершин на классы эквивалентности), при анализе интегральных свойств графовых моделей систем.

Методы решения задач различения расположения фрагментов в графе реализованы в подсистемах АСНИ «Graph Model Workshop». Реализация эффективных методов анализа симметрии расположения фрагментов в графе позволила повысить эффективность решения других задач структурного спектрального анализа (для некоторых классов графов на порядки). Этим была подтверждена общеметодологическая значимость учёта симметрии как универсального метода повышения эффективности обработки структурной информации.

ЗАКЛЮЧЕНИЕ

Основной целью диссертации была разработка, программная реализация и исследование методов различения расположения фрагментов в графе.

В результате выполненной работы получены следующие результаты:

1. Рассмотрены задачи, составляющие инвариантное ядро задач различения расположения фрагментов (РРФ) в графе (ИЯЗР2) для отношений эквивалентности и ^.-эквивалентного вложения, а также расширяющие их задачи различения т-эквивалентного расположения фрагментов в графе, проанализированы подходы к их решению.

2. Развита методология переборно-группового подхода к характеризации расположения фрагментов в графе. В рамках данной методологии разработаны эффективные алгоритмы решения задач из класса РРФ, включая алгоритмы:

1) канонизации представления помеченного фрагмента;

2) построения и анализа ПМ ГАГ и её стационарных подгрупп;

3) построения и анализа ПМ ^-группы и её подгрупп;

4) построения и анализа матрицы пересечения фрагментов.

Это позволило характеризовать взаимное и относительное расположение произвольных фрагментов с точностью до орбит ^-групп (то есть с учётом симметрии исследуемого графа).

3. Разработаны алгоритмы решения задач из класса РРФ в рамках структурно-характеристического подхода, включая алгоритмы:

1) построения и анализа g- и ^-моделей графов общего вида, в отличие от алгоритмов, разработанных Ткаченко С.В., позволяющие априори задавать базисы структурных дескрипторов;

2) построения и анализа графов расположения цепей (специализированная версия с повышенной эффективностью);

3) итерационного уточнения классов эквивалентности вершин по g-модели с произвольной правой частью и специализированные, с повышенной эффективностью, по g-модели в базисе цепей и циклов.

4. Реализованы универсальные методы учёта симметрии для сокращения перебора при решении iVP-полных задач структурного анализа. Особую роль данные методы играют в методологии монотонного расширения частичных решений. В рамках данной методологии разработаны авторские версии алгоритмов поиска максимального общего фрагмента двух графов в смысле подграфа (на порядки возросла эффективность анализа симметричных графов, например, транзитивных, являющихся моделями топологий вычислительных комплексов и сетей) и поиска всех канонических изоморфных вложений фрагмента в граф (на порядки возросла эффективность анализа высоко симметричных фрагментов, например, звёзд и клик). Также учёт симметрии применён при решении задачи декомпозиции графа на неизоморфные фрагменты (заметное повышение эффективности), задачи поиска гамильтоновых цепей и циклов (визуализация симметрии при интерактивном выполнении алгоритма) и других задач. Таким образом, показана значимость учёта симметрии и высокая эффективность методов её учёта.

5. Созданы или расширены подсистемы АСНИ «Graph Model Workshop» (среди них «Различение графов», «Симметрия расположения фрагментов графов», «g- и ^-модели графов», «Сложность графов», «Декомпозиция графов на неизоморфные фрагменты», «Случайная генерация и трансформация»), АСНИ «Graph Model Workshop» (GMW) зарегистрирована в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (СВИДЕТЕЛЬСТВО №2005612847 от 2.11.2005 г.) Программные разработки содержат более 3 МБ авторского исходного кода и более 8 МБ исполняемого кода.

6. На основе подсистем GMW созданы четыре программных средства учебного назначения (ПСУН) для компьютерной поддержки раздела «Основы структурной информатики» дисциплины «Информатика» и поддержки дисциплин «Структурная информатика», «Дискретная математика», «Теория графов и комбинаторика», «Анализ и проектирование эффективных алгоритмов» и др.

7. Проведены объёмные вычислительные эксперименты с использованием GMW. Их результаты позволили:

1) исследовать характеристики симметрии и построить симметричные диаграммы транзитивных графов степени 4 с числом вершин до 31 (вошедшие в справочник);

2) исследовать структурные и числовые инварианты графов и их фрагментов на основе g- и 6-моделей, предложенных Коховым В.А. (показана эффективность методов анализа сходства графов на их основе);

3) исследовать итерационные процедуры уточнения разбиения множества вершин графа на классы эквивалентности по g-модели в базисе цепей различной длины (подтвердилось резкое повышение чувствительности структурных инвариантов итерационного типа);

4) выделить графы, обладающие изоморфными примарными подграфами или примарными частичными графами, полученными удалением вершин или рёбер из разных орбит (пример исследования оригинального отношения эквивалентности графов).

1. A. Lubiw, Some NP-complete problems similar to graph isomorphism, SIAM J. Computing, Vol. 10,(1981), -pp. 11-24.

2. Babai L. Isomorphism testing and symmetry of graphs. II Annals of Discrete Math, 1980, Vol.8, —pp. 101-109.

3. Bunke, Jiang, X. Graph matching and similarity, in Teodorescu, H.-N., Mly-nek, D., Kandel, A., Zimmermann, H.-J. (eds.): Intelligent Systems and Interfaces, Kluwer Academic Publishers, 2000. 33 p.

4. CHEN Ling, YINXinchun, Parallel Algorithm for Testing Isomorphism of Undirected Graphs, Computer Engineering, vol. 28, no. 6, 2002.

5. Chris D. Godsil, Gordon F. Royle. Algebraic Graph Theory. — Springer, 1 edition, 2001. 464 p.

6. D.G. Cornell, C.C. Gotlieb, An efficient algorithm for graph isomorphism, Journal of the Association for Computing Machinery, 17, pp. 51-64, 1970.

7. D.H. Smith, Distance-transitive graphs of valency four, J. London Math. Soc. (2) 8, (1974). -pp. 377-384.

8. Douglas C. Schmidt, Larry E. Druffel. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices. II Journal of the ACM, 23(3), 1976.-pp. 433-445.

9. E. Hemaspaandra, L. A. Hemaspaandra, S. P. Radziszowski, R. Tripathi. Complexity Results in Graph Reconstruction, Technical Report URCS-TR-2004-852, October 10, 2004.-27 p.

10. E. M. Luks. Permutation groups and polynomial time computations. I I DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 11, 1993. —pp. 139-175.

11. E. Spence. Strongly Regular Graphs on at most 64 vertices. — http://www.maths.gla.ac.Lik/~es/srgraphs.html.

12. Gordon F. Royle. Combinatorial Catalogues. — http:// www. esse, uwa. edu. au/~gordon/data.html.

13. J. Manning. Geometric symmetry in graphs. Ph. D. thesis, Purdue University, New York, 1990.

14. J. R. Ullmann. An Algorithm for Subgraph Isomorphism. II Journal of the Association for Computing Machinery, vol. 23, 1976, pp. 31-42.

15. J. Tordn. On the hardness of Graph Isomorphism. II SIAM Journal of Computing, 33(5), 2Ш.-рр. 1093-1108.

16. K.V.S. Bhat, Refined vertex codes and vertex partitioning methodology for graph isomorphism testing, IEEE Transactions on System, Man & Cybernetics, Vol. SMC-10, 1980, др. 610-615.

17. L. Babai, D. Grigoryev, D. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. II Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982,-pp. 310-324.

18. L. P. Cordelia, P. Foggia, C. Sansone, M. Vento, An Improved Algorithm for Matching Large Graphs, Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representation, Italy, 2001.

19. L. P. Cordelia, P. Foggia, C. Sansone, M. Vento, Subgraph Transformations for the Inexact Matching of Attributed Relational Graphs, Computing, suppl. 12, pp. 43-52, 1998.

20. L.P. Cordelia, P. Foggia, C. Sansone, M. Vento, Performance evaluation of the VF Graph Matching Algoritmh, Proc. of the 10th ICIAP, IEEE Computer Society Press, pp. 1172-1177, 1999.

21. Larry E. Druffel, Douglas C. Schimdt, Da Lun Wang. A generator set for representing all automorphisms of graph. IISIAMJ. App. Math., Vol. 34, No. 3, 1978. -pp. 593-596.

22. LI Feng, LI Xiaoyan, Isomorphism Testing Algorithm for Graphs: Incidence Degree Sequence Method and Applications, Journal of Fundan University {Natural Science), vol. 40, 2001. -pp. 318-325.

23. Liu Xiaoyu, Balasubramanian K., Munk M.E. Computational Techniques for Vertex Partitioning of Graphs. // J. Chem. Inf. Comput. Sci. 1990, 30. pp. 263-269.

24. McKay B. D. nauty User's Guide (Version 2.2), 2004. 33 p.

25. McKay B. D., Praeger С. E. Vertex-Transitive Graphs Which Are Not Cayley Graphs. I II J. Austral. Math. Soc. Ser. A 56, 1994. -pp. 53-63.

26. McKay B.D. Practical graph isomorphism. II Congressus Numerantium 30, 1981. -pp. 45-87.

27. McKay, Brendan D.; Royle, Gordon F. The transitive graphs with at most 26 vertices. II Ars Combin. 30 (1990). -pp. 161-176.

28. Messmer B.T., Bunke H., A decision tree approach to graph and subgraph isomorphism detection, Pattern Recognition, vol. 32, 1999. -pp. 1979-1998.

29. Messmer B.T., Bunke H., Subgraph isomorphism in polynomial time. II Technical Report TR-IAM-95-003, 1995. 33 p.

30. MSDN (.Microsoft Developer Network) Library и MSDN online — http://msdn.microsoft.com.

31. P. Dickinson, H. Bunke, A. Dadej and M. Kraetzl. On Graphs with unique node labels. E. Hancock, M. Vento (eds.): Graph Based Representations in Pattern Recognition in Proc. 4th Int. Workshop GBR2003, Springer, LNCS2126,pp. 13-23.

32. P. Foggia, C. Sansone, M. Vento. A Performance Comparison of Five Algorithms for Graph Isomorphism. II International Workshop on Graph-based Representation in Pattern Recognition, Ischia, Italy, pp. 188-199, 23-25 May, 2001.

33. Raymond J.W., Willett P. Maximum common subgraph isomorphism algorithms for the matching of chemical structures. II Journal of Computer-Aided Molecular Design, 16, 2002. -pp. 521-533.

34. Robert F. Bailey. Distance-Transitive Graphs, Department of Pure Mathematics, University of Leeds (2002). 125 p.

35. Ronald С. Read, Robin J. Wilson. An Atlas of Graphs. — Oxford University Press, 1998.-464 p.

36. Royle, Gordon F.; Praeger, Cheryl E. Constructing the vertex-transitive graphs of order 24. II J. Symbolic Comput. 8 (1989), no. 4. -pp. 309-326.

37. To His I., Di Battista G., Eades P., Tamassia R. Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall; Is/ edition (1998). 397 p.

38. V. Arvind, P. Kurur. Graph isomorphism is in SPP. II Electronic Colloquium on Computational Complexity (.ECCQ TR02-037, 2002. 12 p.

39. Willett P., Willett J. Similarity and Clustering in Chemical Information Systems.1. John Wiley & Sons, 1987.

40. Алгоритмические исследования в комбинаторике. Под ред. Фараджева И.А.1. М.: Наука, 1978.- 188 с.

41. Арлазаров BJL, Зуев И.И., Усков А.В., Фараджев И.А. Алгоритм приведения конечных неориентированных графов к каноническому виду. // Журнал вычислит, мат. и мат. физ., 1974, Т. 14, №3. С. 737-743.

42. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. — М.: Радио и связь, 1991. 248 с.

43. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы.: Пер. с англ.: Уч. пос. — М.: «Вильяме», 2000. 384 с.

44. Берж К. Теория графов и её применения. — М.: Изд-во иностр. лит., 1967. -320 с.

45. Бертц С. Математическая модель молекулярной сложности. // Химические приложения топологии и теории графов. — М.: Мир, 1987.

46. Воронцов К. В. Локальные базисы в алгебраическом подходе к проблеме распознавания. — Диссертация на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН, 1999.- 122 с.

47. Гери М., Джонсон Д. Вычислительные машины и труднорещаемые задачи.1. М.:Мир, 1982.-416 с.

48. Готт B.C., Перетурин А.Ф. Симметрия и асимметрия как категории познания. // Симметрия, инвариантность, структура. Философские очерки. М.: Высшая школа, 1967. - С. 3-70.

49. Грызунов А.Б. Разработка методов структурного различения графовых моделей дискретных систем. Дисс. на соискание уч. степени канд.техн. наук. М. МЭИ. 1987.- 163 с.

50. Грызунов А.Б., Кохов В.А. Метод сокращения перебора на основе учета симметрии при решении iVP-полных задач на графах // Моск. Энерг. ин-т. -М, 1987. 58 с. деп. ВИНИТИ, 18.08.87, №6029-В87.

51. Грызунов А.Б., Кохов В.А. Эффективные алгоритмы изоморфного вложения и пересечения графов. // Тезисы докл. межвузовской конференции «Молекулярные графы в химических исследованиях». Калинин, 1990. С. 15-16.

52. Добрынин А.А., Скоробогатов В.А. Метрические инварианты подграфов молекулярных графов. // Математические методы в структурной информатике. — Новосибирск, 1991. С. 3-62.

53. Евдокимов С. А., Пономаренко И.Н. Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время. // Алгебра и анализ, Т. 15, вып. 6, 2003.-С. 1-34.

54. Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.

55. Журавлев Ю. И. Об алгебраических методах в задачах распознавания и классификации. // Распознавание, классификация, прогноз, Т. 1, 1988. -С. 9-16.

56. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации. // Проблемы кибернетики, Т. 33, 1978. С. 5-68.

57. Зубов B.C. Справочник программиста. Базовые методы решения графовых задач и сортировки. — М.: ФИЛИНЪ, 1999. 256 с.

58. Зыков А.А. Основы теории графов. ■— М: Вузовская кн., 2004. 664 с.

59. Исследования по алгебраической теории комбинаторных объектов. Под ред. Фараджева И.А. —М.: ВНИИСИ, 1985.- 187 с.

60. Исследования по общей теории систем. Сборник переводов. Общая редакция и вступит, статья Садовского В.Н. и Юдина Э.Г. М.: «Прогресс», 1969.

61. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. 1104 с.

62. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.

63. М.: Издательский дом «Вильяме», 2000. 720 с.

64. Кнут Д. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд. — М.: «Вильяме», 2000. 832 с.

65. Кнут Д. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.

66. М.: «Вильяме», 2000. 832 с.

67. Коксетер Г.С.М., Мозер У.О.Дж. Порождающие элементы и определяющие соотношения дискретных групп. — М.: Наука. Главная редакция физико-математической литературы, 1980. 240 с.

68. Колмогоров А.Н. Три подхода к определению понятия «количество информации». — Проблемы передачи информации. 1965. Вып. 1. Т.1. С. 1-7.

69. Константинова Е.В., Скоробогатов В.А. Структурные и численные инварианты обыкновенных и молекулярных графов. // Математические методы в структурной информатике. —Новосибирск, 1991. С. 87-129.

70. Кохов В.А. Граф-модели в структурном спектральном анализе систем. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2004), Т.1, Москва, 2004. С. 211-214.

71. Кохов В.А. Диаграммы, числа стабильности и цикловые индексы групп автоморфизмов транзитивных графов. // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд., 1986. С. 97-125.

72. Кохов В.А. Исследование на ЭВМ симметрии транзитивных сильно регулярных графов. // Системное моделирование-10. — Новосибирск: ВЦ СО АН СССР, 1984.-С. 35-44.

73. Кохов В.А. Концептуальные и математические модели сложности графов. // М. Издательство МЭИ, 2002. 160 с.

74. Кохов В.А. Некоторые инварианты конечных графов и их применение. Ав-тореф. диссертации на соискание уч. степени канд. техн. наук. М.:МЭИ. 1976.-20с.

75. Кохов В.А. Основы структурной информатики. // Доклады международной конференции «Информационные средства и технологии». (МФИ-98), Т.З. — Москва, 1998.

76. Кохов В.А. Основы химической структурной информатики. // Тезисы докладов международной конференции «Информационные средства и технологии» международного форума информатизации (МФИ-97), ТЗ, Москва, 1997. -С. 37- 42.

77. Кохов В.А. Решение задач анализа графов и их групп автоморфизмов с помощью ППП «GMW-2.0» — М.: Издательство МЭИ, 2002. 64 с.

78. Кохов В.А. Структурная информатика: методы различения расположения фрагментов графа. // Доклады международной конференции «Информационные средства и технологии» (МФИ-2002), Т2, Москва, МЭИ, 2002. С. 51-54.

79. Кохов В.А. Число тождественности графа. // Моделирование в информатике и вычислительной технике (Системное моделирование-13). — Новосибирск: ВЦ СО АН СССР, 1988. С. 49-63.

80. Кохов В.А., Грызунов А.Б., Картовицкий A.JI. ППП структурного анализа и синтеза молекулярных графов. // Тезисы докладов межвузовской конференции «Молекулярные графы в химических исследованиях». Калинин, 1990. -С. 43-44.

81. Кохов В.А., Незнанов А.А., Горшков С.А. ППП «СТРИН+»: Подсистема сравнительного анализа структур. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2004), Т.1, Москва, 2004. -С. 215-218.

82. Кохов В.А., Незнанов А.А., Ткаченко С.В. Новые программные средства для поиска структурной информации. // Труды международной научно-технической конференции «Информационные средства и технологии». (МФИ-2005), Т.2, Москва, 2005. С. 83-86.

83. Кохов В.А., Незнанов А.А., Ткаченко С.В. «СТРИН». // ПСУН по разделу «Структурная информатика» дисциплины «Информатика» / Паспорт от 16.03.2005 г. М., МЭИ, 2005.

84. Кохов В.А., Незнанов А.А., Ткаченко С.В. «Полигон алгоритмов структурной информатики». // ПСУН по разделу «Структурная информатика» дисциплины «Информатика» / Паспорт от 16.03.2005 г. М., МЭИ, 2005.

85. Кохов В.А., Ткаченко С.В. Редактор структур, автоматическая прорисовка диаграмм и методы анализа сложности и сходства графов: Лабораторный практикум. — М.: Издательство МЭИ, 2001. 120 с.

86. Кохов В.А., Ткаченко С.В., Незнанов А.А. Построение алгоритмов и программ быстрой обработки физико-химической информации. — Отчёт по НИР, выполненной на кафедре ПМ. Зарегистрированная тема НИР МЭИ № 1147970, 2001.- 124 с.

87. Кохов В.А., Ткаченко С.В., Незнанов А.А. Решение базовых задач структурной информатики с помощью ППП «ПОЛИГОН-СТРИН»: лабораторный практикум. — М.: Издательство МЭИ, 2005. 120 с.

88. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. -432 с.

89. Лаке Ю.М. Изоморфизм графов с ограниченными степенями вершин может быть установлен за полиномиальное время — Киберн. сб. М., 1985. N 22. С. 72-101.

90. Липский В. Комбинаторика для программистов. — М.: Мир, 1988. 213 с.

91. Майника Э. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981. -323 с.

92. Незнанов А.А. Разработка и исследование методов анализа расположения и взаимного расположения фрагментов в топологии графовых моделей систем. — Магистерская диссертация, МЭИ, 2002. 106 с.

93. Незнанов А.А., Кохов В.А. Алгебраический подход к анализу симметрии расположения фрагментов графа. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2003), Т.1, Москва, 2003. -С. 216-219.

94. Незнанов А.А., Кохов В.А. Справочник по теории графов. Характеристики симметрии и сложности связных транзитивных графов степени 4 с числом вершин до 30 включительно. — М. Деп. в ВИНИТИ, №1094-В2004, 2004. -418 с.

95. Незнанов А.А., Кохов В.А. Структурная информатика: симметрия структур. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2001), Т.З, — Москва, 2001. С. 38-42.

96. Незнанов А.А., Кохов В.А. Сходство систем в топологии надсистемы. // Научная сессия МИФИ-2004: Сб. науч. трудов. Т.З, М.:МИФИ, 2004. -С. 198-199.

97. Нечепуренко М.И., Попков В.К., Кохов В.А. и др. Алгоритмы и программы решения задач на графах и сетях. — Новосибирск: Наука, 1990. 515 с.

98. Прангишвили И.В. Системный подход и общесистемные закономерности. Серия «Системы и проблемы управления». — М.: СИНТЕГ, 2000. 528 с.

99. Пролубников А.В. Алгоритм поиска приближенного решения задачи проверки изоморфизма подграфов. // Математические структуры и моделирование: Сб. научн. тр. Под ред. А.К. Гуца. Омск: Омск. гос. университет, 2003. Вып. 10.-С. 59-66.

100. Ш.Рихтер Дж. Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows, 4-е изд. — СПб: Питер; М.: «Русская редакция», 2001. 752 с.

101. Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.

102. Седжвик Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах: Пер. с англ. — СПб: ООО «ДиаСофтЮП», 2002. 496 с.

103. Сетров М. И. Общие принципы организации систем и их методологическое значение. М. 1975. - 132 с.

104. Скоробогатов В.А. О распознавании изоморфизма неориентированных графов. // Вычислительные системы. Новосибирск, 1969. Вып. 33 - С. 3-10.

105. Скоробогатов В.А., Хворостов П.В. Анализ метрических свойств графов. // Методы обнаружения закономерностей с помощью ЭВМ. Новосибирск, 1981. -С. 3-20.

106. Скоробогатов В.А., Хворостов П.В. Методы и алгоритмы анализа симмет-рий графов. // Алгоритмы анализа структурной информации, выпуск 103. Новосибирск, 1984.-С. 6-25.

107. Ткаченко С.В., Незнанов А.А., Кохов В.А. Компьютерная поддержка курса «Основы Структурной информатики». // Доклады международной конференции «Информационные средства и технологии» (МФИ-2002), Т.2, Москва, 2002.-С. 55-58.

108. Узоры симметрии. Под ред. М. Сенешаль и Дж. Флека. — М.: Мир, 1980. -269 с.

109. Харари Ф. Теория графов. — М:. Едиториал УРСС, 2003. 296 с.

110. Харари Ф., Палмер Э. Перечисление графов. Пер. с англ. — М.: Мир, 1977, -324 с.

111. Шеннон К. Работы по теории информации и кибернетике. —М.: Изд. ин. лит., 1963.

112. Шрейдер Ю.А. Равенство, сходство, порядок. —М.: Наука, 1971. 256 с.