close

Вход

Забыли?

вход по аккаунту

?

bd000100890

код для вставкиСкачать
На правах рукописи
Незнанов Алексей Андреевич
Методы и программные средства
для различения расположения фрагментов
графовых моделей систем
Специальность 05.13.11 -Математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Москва, 2005
Работа выполнена на кафедре Прикладной математики
Энергетического Института (Технического Университета)
Научный руководитель:
кандидат технических наук, доцент
Кохов Виктор Алексеевич
Официальные оппоненты:
доктор технических наук, доцент
Фальк Вадим Николаевич
Московского
кандидат технических наук, доцент
Грызунов Аркадий Борисович
Ведущая организация:
Всероссийский институт научной и технической
информации (ВИНИТИ), г. Москва.
Защита состоится 23 декабря 2005 г.
на заседании диссертационного совета Д 212.157.01
при Московском Энергетическом инсттуте (Техническом Университете)
по адресу: 111250, Москва, Красноказарменная ул., д. 17 (ауд. Г-306)
С диссертацией можно ознакомиться в библиотеке
Московского Энергетического Института (Технического Университета).
Отзывы в двух экземплярах, заверенные печатью организации, просьба
направлять по адресу: 111250, г. Москва, ул. Красноказарменная, д. 14,
Ученый Совег М Э И (ТУ).
Автореферат разослан «-с-о » ноября 2005 г.
Ученый секретарь
кандидат технических наук,
профессор
Ладьптга И.И.
^^С>-Н
д^^^^^д
Общая характеристика работы
Актуальность темы работы.
Графовые модели систем (ГМС) - математические модели структур сис­
тем. Использование компьютерной техники для анализа и синтеза ГМС позво­
лило сделать качественный скачок в структурном анализе и привело к развитию
прикладной теории графов. Однако особую роль методы прикладной теории
графов играют именно в развитии информационных технологий (теории транс­
ляции, оптимизации программ, организации сложных структур данных, визуа­
лизации данныж, построении человеко-машинных интерфейсов и др.).
Одним из основных классов задач прикладной теории графов является
класс задач различения графов и различения расположения фрагментов графов.
История развития методов решения задач различения графов насчитывает бо­
лее 50 лет. В настоящее время в решении задач распознавания изоморфизма
графов, распознавания изоморфного вложения графов и смежных с ними задач
достаинут большой теоретический и практический прогресс. Но задачи разли­
чения расположения фрагментов графов, более сложных, чем вершины, изуче­
ны намного слабее. Исследование расположения фрагментов графов актуализи­
ровалось в конце 80-х годов прошлого века в связи с развитием приложений
химической теории графов (QSAR-aHamisa, QRRR-saajmsa и др.), правдоподоб­
ных рассуждений, структурного распознавания образов, структурной лин­
гвистики. Эти исследования шли в достаточно узких областях (например,
большинство предложенных топологических индексов явно или неявно учиты­
вали расположение простейших фрагментов) и несистематически. Не сущест­
вует даже устоявшейся терминологии, пригодной как для теоретических, так и
для прикладных исследований.
Учёт расположения фрагментов Г М С наполняет новьпл содержанием от­
ношения «подсистема-надсистема». Задачи различения расположения фрагмен­
тов Г М С обобщают задачи различения ГМС, принимая во внимание надсистему, в которую входят рассматриваемые фрагменты. Решение этих задач позво­
ляет исследовать отношения эквивалентности и толерантности ГМС с учётом
расположения фрагментов, расширяет возможности подструктурной характеризации ГМС. Особенно ярко различия в расположении фрагментов проявля­
ются в симметрии (асимметрии) расположения фрагментов. Учёт симметрии общеметодологический принцип повьппения эффективности компьютерной об­
работки структурной информации, как в задачах анализа, так и синтеза струк­
тур.
Работа продолжает исследования научного руководителя диссертанта Кохова В.А., которые привели к созданию новой научной дисциплины «струк­
турный спектральный анализ систем» (СС-анализ). Выделены пять основных
классов задач СС-анализа, среди которых - класс задач различения расположе­
ния фрагментов в графе и различения графов с учётом расположения фрагмен­
тов.
j РОС НАЦИОНАЛЬНАЯ
БИБЛИОТЕКА
CtlMifl
О* МО-
I
т^^щ
I тшвтт^Л
■»
Цель работы. Цель диссертационной работы - разработка, программная
реализация и исследование методов различения расположения фрагментов в
Г М С и методов различения Г М С с учётом расположения фрагментов на основе
разлргеных отношений эквивалентности. Это позволит повысить эффективность
компьютерных методов анализа сходства ГМС и широко использовать их в на­
учных и прикладных исследованиях, связанных со структурньпи спектральным
анализом систем.
Решаемые задачи. Для достижения поставленной цели в работе решают­
ся следующие задачи:
1. Развитие переборно-группового и структурно-характеристического
подходов к решению задач различения расположения фрагментов
(РРФ) в храфе.
2. Разработка алгоритмов решения задач из класса Р Р Ф , использующих
эти подходы.
3. Создание эффектавного специализированного метода в рамках транс­
графового подхода к решению задач из класса РРФ для цепных фраг­
ментов.
4. Повышение эффективности решения базовых задач СС-анализа (таких
как поиск всех канонических изоморфных вложений, поиск макси­
мального изоморфного пересечения, декомпозиция графа на неизо­
морфные фрагменты и др.) при помощи учёта симметрии расположе­
ния фрагментов в графе.
5. Реализация разработанных алгоритмов в виде подсистем АСНИ
«GraphModel Workshop» (GMW) и программных средств учебного на­
значения.
6. Исследование разработанных алгоритмов и их реализаций, установле­
ние границ применимости, определение асимптотических оценок вы­
числительной сложности, сравнение с ранее существующими алгорит­
мами.
7. Применение реализованных подсистем GMW для получения теорети­
ческих и прикладных результатов, использование в учебном процессе.
Научная новизна. Показана перспективность и эффективность учёта рас­
положения произвольных фрагментов при решении задач структурного анализа
с использованием вычислительной техники. Для этого:
1. Разработан эффективный алгоритм канонюации представления поме­
ченного фрагмента в топологии графа на основе сильного порождаю­
щего множества группы автоморфизмов фрагмента.
2. Развит и угл5^лён переборно-групповой подход к решению задач из
класса РРФ на основе ?-групп, индуцированных группой автоморфиз­
мов графа.
3. Предложена и реализована полная схема характеризации расположе­
ния произвольных фрагментов графа (от построения баз помеченных
фрагментов до анализа математических моделей характеризации рас-
4.
5.
6.
7.
положения фрагментов) с точностью до орбит /-групп в рамках пере­
борно-группового и структурно-характеристического подходов.
Реализован трансграфовый подход к различению расположения цеп­
ных фрагментов путём различения вершин графа расположения цепей.
Методология решения базовых задач СС-анализа путём монотонного
расширения частичных решений, развитая Грызз^овым А.Б., впервые
дополнена универсальным механизмом эффективного анализа стацио­
нарных подгрупп группы автоморфизмов графа.
Обобщены и реализованы итерационные алгоритмы усиления чувст­
вительности структурных инвариантов вершин графов в базисе щоизвольных фрагментов на основе g-моделей, позволившие резко повы­
сить чувствительность структурных инвариантов.
Получены новые теоретические результаты исследований расположе­
ния фрагментов в графе, проведённые в АСНИ GMW (в особенности исследований характеристик симметрии транзитивных графов, являю­
щихся моделями топологий вычислительных комплексов и сетей, и
других семейств Г М С с ярко выраженной симметрией).
Практическая полезность. Результаты работы (в особенности про­
граммные комплексы) могут быть использованы для повьппения эффективно­
сти и качества компьютерной обработки данных, представленных в виде ГМС.
Учёт расположения фрагментов ГМС позволит: повысить эффективность
анализа семантических сетей и качество структурной аналогии при проведении
правдоподобных рассуждений в системах поддержки принятия решений; повы­
сить качество оценки надёжности и живучести при проектировании топологий
вычислительных сетей и сред; использовать более широкий спектр отношений
эквивалентности и толерантности структур в приложениях структурной ин­
форматики, химической структурной информатики и структурного распознава­
ния образов.
Методы исследований и достоверность результатов.
Задачи, постав­
ленные в работе, решаются с помощью методов теории графов, прикладной
теории графов, теории групп, теории анализа вычислительной сложности алго­
ритмов, анализа и построения эффективных алгоритмов и др. В работе сущест­
венно использованы результаты, которые получили Кохов В.А, Фараджев И.А.,
Грызунов А.Б., Ткаченко С В . , Скоробогатов В.А., J . R. Ullmann, В. D. McKay,
G. F. Royle, P. WiUett, E. L u b , L. E. Draffel.
Основой получения новых научных результатов являются объёмные вы­
числительные эксперименты. При малой сложности исходных данных резуль­
таты вычислительных экспериментов на тестовых наборах исходных данных
совпадают с известными результатами. При обработке сложных исходных дан­
ных сравнивались результаты, полученные различными методами решения од­
ной и той же задачи.
Реализация результатов.
Работа выполнялась в соответствии с проек­
том Г К Н Т России «Новые принципы и методы получения чистых веществ и
материалов» макропрограмма 10.2 «Разработка математических основ и про­
граммных средств химической информатики» тема 10.2.3 «Построение алго­
ритмов и создание программ быстрой обработки и извлечения физикохимической ршформации» и зарегистрированной темой НИР М Э И (ТУ) №
1147970. Разработанные программные средства используются в учебном про­
цессе и научно-исследовательской работе кафедры Прикладной математики
М Э И (ТУ), кафедры «Информационные системы» МГТУ «Станкин» и кафедры
«Компьютерные системы автоматизации производства» М1ТУ им. Н.Э. Баума­
на. Модели, методы и программные компоненты используются в производст­
венном процессе и исследовательской работе ООО «Фирма Перспектива».
АСНИ «Graph Model Workshop» («Мастерская граф-моделей») зарегистрирова­
на в Федеральной службе по интеллектуальной собственности, патентам и то­
варным знакам (СВИДЕТЕЛЬСТВО № 2005612847 от 2.11.2005 г.).
Апробация работы. Основные положения и результаты диссертации
докладывались и обсуждались на международных научно-технических конфе­
ренциях
студентов
и
аспирантов
«РАДИОЭЛЕКТРОНИКА,
ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА» (с 6-ой по 11-ую, г. Москва, 2000-2005
гг.), на международных форумах информатизации МФИ-2001 - МФИ-2005
(международные конференции «Информационные средства и технологии», г.
Москва, 2001-2005 гг.), на научной сессии М И Ф И (г. Москва, 2004 г.), на деся­
той национальной конференции по искусственному интеллекту с международ­
ным участием КИИ-2004 (г. Тверь, 2004 г.), на первом всероссийском совеща­
ние НМС по информатике при Минобразования и науки Российской Федерации
«Актуальные проблемы информатики в современном российском образовании»
(г. Москва, 2004 г.).
Личный вклад диссертанта. Работа продолжает развитие методов
структурного спектрального анализа, разработанных Коховым В.А. Диссертан­
том пройден путь от анализа задач до создания прикладных программ. Личный
вклад диссертанта состоит в разработке эффективных методов решения задач
различения расположения фрагментов в графе и реализации эффективных про­
граммных средств в рамках единой методологии решения базовых задач струк­
турного спектрального анализа, а также проведении научных исследований, ис­
пользующих эти средства.
Публикации. Основные результаты, полученные в процессе вьшолнения
диссертационной работы, опубликованы в 21 печатной работе в виде справоч­
ника, учебно-методического пособия, паспортов программных продуктов, док­
ладов и тезисов докладов.
Структура и объём работы.
Диссертация состоит из введения, пяти
глав, заключения, списка литературы (123 наименования) и приложений. Дис­
сертация содержит 169 страницы машинописного текста.
Содержание работы
Во введении обоснована актуальность темы диссертационной работы, по­
ставлены цели и задачи исследований, сформулированы научная новизна и
практическая значимость, приведено краткое содержание работы по главам.
В первой главе рассматриваются основные понятия, связанные с исследо­
ванием расположения фрагментов ГМС и формулируются основные решаемые
задачи. При этом используется следующая терминология.
Абстрактный тип (t) - произвольный обыкновенный граф, определённый
с точностью до автоморфизма. Группу его вершинных автоморфизмов (также с
точностью до изоморфизма) обозначим через Aut{t).
Граф / назовём фрагментом графа G, если / изоморфно вкладывается в G в
некотором смысле. В большинстве случаев будем считать, что смысл отноше­
ния изоморфного вложения определён заранее. В данной работе рассматрива­
ются в основном два типа вложения:
1) в смысле подграфа (обозначение - <Л>);
2) в смысле произвольного фрагмента (обозначение - «'*»).
Помеченным графом называется граф, с множеством вершин которого вза­
имно однозначно сопоставлено множество пометок, то есть каждая вершина
которого имеет уникальный атрибут. Наличие пометок будем обозначать верх­
ним индексом «"''». Понятие пометок вершин графа отличается от понятия ну­
мерации (идентификации) вершин с целью хранения структурной информации
Помеченным фрагментом/^" типа / графа G назовём помеченный граф t"',
пометки которого соответствуют вершинам графа G, образующим (вместе с не­
которыми инцидентными им рёбрами) часть графа G, изоморфную /. Через
F^"{G)= {f"\,f''2,
■■■,f^^'m} обозначим множество всех помеченных фрагмен­
тов типа t графа G.
Для различения абстрактного типа и типов реальных фрагментов графа бу­
дем называть тип фрагмента с заданной нумерацией вершин идентификацион­
ным типом. Специального обозначения вводить не будем, так как из контекста
обычно ясно, введена нумерация вершин или нет. Если на множестве вершин
абстрактного типа фрагмента t и графа G задана нумерация, то помеченный
фрагмент графа У*' может быть представлен различными изоморфными вложе­
ниями - отображениями номеров вершин t в номера вершин G. Число изоморф­
ных вложений, представляющих один и тот же помеченный фрагмент графа,
равняется порядку группы автоморфизмов абстрактного типа (| Aut{t) | ) .
Помеченный фрагмент удобно представлять одним из изоморфных вложе­
ний, которое назовём каноническим. Каноническим будем считать то из изо­
морфных вложений, образующих фрагмент Z*^^' графа G, у которого список но­
меров вершин графа G, в порядке нумерации вершин типа фрагмента t, лекси­
кографически минимален. Переход от неканонического представления поме­
ченного фрагмента к каноническому назовём канонизацией представления
фрагмента. Таким образом, установлено однозначное соответствие между по­
меченными фрагментами и каноническими изоморфными вложениями.
Формулировка задач из класса задач различения расположения фрагментов
(РРФ) проводится на базе понятия г-группы графа, индуцированной группой
вершинных автоморфизмов и отражающей симметрию расположения фрагмен­
тов типа i в графе.
t-автоморфизмом графа G называется подстановка ^ на множестве поме­
ченных фрагментов типа / графа G (или канонических изоморфных вложений)
F^^\G), индуцированная некоторым вершинным автоморфизмом g графа G. В
процессе индуцирования помеченный фрагмент f'\ & F^^'{G), представленный
каноническим изоморфньпи вложением (vi, vi, ..., v„) графа G, переходит в по­
меченный фрагмент/''у, полученный канонизацией вложения {щ, uj, ..., и„), где
и, = g(v,), г е [1, и], и - число вершин фрагмента.
Группой t-автоморфизмов графа G (Auf{G), /-группой) называется группа
подстановок, носителем которой является всё множество /-автоморфизмов для
данного /, а групповой операцией - операция произведения (композиции) под­
становок.
В работе исследуются следующие базовые задачи (см. таблицу 1):
• различения расположения однотипных фрагментов (РРОФ) типа / по
отношению принадлежности одной орбите /-группы и автоморфного
разбиения множества однотипных фрагментов (АРМОФ);
• различения расположения произвольных фрагментов (РРФ) по отно­
шениям между орбитами /-групп на основе операции вложения;
• различения расположения фрагментов относительно выделенного по
отношению принадлежности одной орбите фиксатора /-группы.
Таблица 1
Варианты задач различения графов и различения расположения фрагментов в графе
№
I Обозначение {Задача
1. Различение п а р ы графов
1.1
1.2
G,«G2
G,c^G2
Изоморфизм G\ и Gi
2.1
2.2
Л-/''2
Автоморфноерасположение/^'^'H/^Vе F{G)
2.3
j<i)t\ ^^)a
Расположение с вложением f^" bf''"' в смысле произвольного фраг­
мента
Изоморфизм G\ подграфу G : (вложение в смысле подграфа)
Изоморфизм G i любой части G j (вложение в смысле произвольного
1.3 G,d*G2
фрагмента)
2. Различение расположения пары фрагментов типа П , <2
Mil ^
мл
Расположение с вложением /'''"' •af^'^ в смысле подграфа
3. Различение расположения пары фрагментов относительно фрагмента f
3.1
3.2
f\
».Л Автоморфное расположение/®]' и/^^'з' е f ( G ) относительно f
f<t)t\ £-^^/«'2Расположение с вложением / ® " в/*"^ в смысле подграфа ат./'^
3.3
мл ^*,f>^
Расположение с вложением /''•'" в/''-'" в смысле произвольного фраг­
мента относительно г^
Например, задача различения расположения двух однотипных помеченных
фрагментов/'^'j,/'''"^ типа / в графе G определяется следующими параметрами:
РРОФ = < G,f'bf'j,
%>, где
G - обыкновенный граф (G = (Г, £), | V\=p,\E\=q);
f^^'h f^'j e F"^' {F^'' - множество всех помеченных фрагментов типа /,
вкладываемых в G в некотором смысле или, что то же, множество всех канони­
ческих изоморфных вложений / в G в некотором смысле);
^' - отношение принадлежности к одной орбите /-группы (группы авто­
морфизмов фрагментов типа 0Решением задачи РРОФ является ответ на вопрос, связаны ли/''-", и f^^'j от­
ношением 4', то есть, принадлежат ли у^'",- и f^^j одной и той же орбите tгруппы. В такой постановке РРОФ является задачей распознавания свойств.
Обобщением задачи РРОФ является задача различения расположения двух
помеченных фрагментов/'''"'в/'''"^^ типов й я й ъ графе G. Она определяется
следующими параметрами:
Р Р Ф = <С,/'^*/«"*;,^=^>, где
/ " ' , е i^-"', /-"^у е F^^ (i^-"' и i^-"^ - множества всех помеченных фраг­
ментов типов й и (2, вкладываемых в G в некотором смысле);
4 " ^ - отношение «элемент орбиты помеченного фрагмента/"'"', изоморф­
но вкладывается в элемент орбиты помеченного фрагмента/''""^,», то есть
Vf'\
е @{AuAG),f^"d {3f>% е @{Auf{G),f>%) : (f>\ ^f>%)\
где &{Auf{G),f^') - орбита f^' относительно r-группы.
Заметим, что задачи РРОФ и РРФ обобщают задачи распознавания изо­
морфизма графов (РИГ) и изоморфного вложения графов (РИВГ) соответствен­
но, ^-эквивалентность - предельный случай всех остальных отношений эквива­
лентного расположения помеченных фрагментов (т-эквивалентности), так же,
как отношение «быть изоморфными» - предельный случай всех отношений эк­
вивалентности графов, ^-эквивалентность служит для анализа чувствительно­
сти (оценки полноты) инвариантов фрагментов, используемых при решении за­
дач из класса РРФ.
Для решения задач из класса Р Р Ф выделены следующие подходы.
1. Переборно-групповой. Основан на прямом анализе /-групп и обеспечи­
вает получение точного решения задач установления ^-эквивалентного
расположения помеченных фрагментов. При его реализации использу­
ются последние достижения в построении и исследовании порождаю­
щих множеств групп автоморфизмов графов и разработки автора.
2. Структурно-характеристический. Основан на анализе структурных и
числовых инвариантов и обеспечивает как приближйнное (для графов
общего вида), так и точное (для более узких классов графов) решение
задач установления ^-эквивалентного расположения помеченных фраг­
ментов. Однако главное преимущество этого подхода в том, что он по­
зволяет исследовать широкий класс отношений т-эквивалентности на
множестве помеченных фрагментов графа и применяется для анализа
сложности и сходства графов, прорисовки диаграмм и др.
3. Трансграфовый. Основан на сведении задачи различения расположения
сложных фрагментов графа к задаче различения расположения вершин
другого храфа (графа расположения фрагментов - ГРФ). Этот подход
10
позволяет наглядной визуализировать помеченные фрагменты в виде
вершин Г Р Ф .
Во второй главе рассматривается переборно-групповой подход к реше­
нию задач различения расположения фрагментов, основанный на анализе инду­
цированных представлений группы автоморфизмов графа (ГАГ). Предлагается
общая схема практического использования данного подхода для характеризации расположения произвольных фрагментов с точностью до орбит f-групп.
Она состоит из двух этапов: на первом этапе производится поиск орбит /-групп
(или фиксаторов/стабилизаторов Г-групп) исследуемых типов фрагментов, а на
втором - анализируется лютрыг^а пересечений орбит помеченных фрагментов.
Первый этап может включать в себя построение баз исследуемых поме­
ченных фрагментов, для чего существует три способа:
1. Построение баз всех однотипных помеченных фрагментов на основе
алгоритма поиска всех канонических изоморфных вложений фрагмента
в граф (ПВКИВ). Применяется, если априори задан базис структурных
дескрипторов (СД). Определение того, что элемент базиса является
фрагментом исследуемого графа, производится процедурой П В К И В .
2. Декомпозиция графа на неизоморфные фрагменты СЩИФ) с после­
дующим запуском процедур П В К И В . Применяется, если исследуемые
типы фрагментов задаются свойствами собственных фрагментов ис­
следуемого графа и их число мало по сравнению с общим числом соб­
ственных фрагментов.
3. Декомпозиция графа на помеченные фрагменты. Применяется, если
исследуемые типы фрагментов задаются свойствами собственных
фрагментов исследуемого графа и их число велико.
При программной реализации работа идёт только с порождающими мно­
жествами групп автоморфизмов специального вида, не прибегая к использова­
нию полных групп. Приводится оригинальный эффективный алгоритм канони­
зации представления помеченного фрагмента, использующий порождающее
множество, содержащее в худшем случае не более (р/(р/ - 1) / 2) автоморфиз­
мов, где pf - число вершин фрагмента. Он имеет квадратичную оценку асим­
птотической временной и емкостной сложности в худшем случае. Этот алго­
ритм используется во всех случаях обработки помеченных фрагментов, в том
числе и при использовании других подходов. Для графа в худшем случае ис­
пользуется либо {рс - 1), либо {pQ (ра - 1) / 2) автоморфизмов, где ра - число
вершин графа, в зависимости от решаемой задачи.
Второй этап в общем виде заключается в построении и анализе матрицы
пересечений орбит двух фрагментов (МПОФ). МПОФ содержит информацию о
значениях характеристики у(0",, ®'^j) (у - некоторый коэффициент сходства
или различия орбит помеченных фрагментов), для всех упорядоченных пар ор­
бит /-групп (©";, 0"^,) для фрагментов типов /1 и /2. Анализ МПОФ позволяет
охарактеризовать расположение всех фрагментов типов /1 и й в графе (рис. 1).
11
Исследуемый граф G
Тип фрагмента й
Тип фрагмента ?1
В графе G две орбиты фрагментов типа /1:
1 - ( U , 3 ) , (3,4,5); 2 - (1Д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Д,1,3), (7,3,4,5), (7,3,5,4)).
Построим МПОФ типов й и /2, где харак­
теристиками пересечения орбит являются:
максимум коэффициента сходства MSB =
Матршю пересечений орбит
фрагментов'типа г1 (строки) и /2 (столбцы)
(максимум коэффициента сходства MSB):
1
2
3
1
0,75000000 0,52083333 0,75000000
2
0,18750000 0,75000000 0,52083333
Матрица пересечений орбит
фрагментов типа г1 и /2
(максимум коэффициента различия MDB):
1
2
3
1
0,81250000 0,97916667 0,97916667
2
0,97916667
1,00000000
1,00000000
{p{MCF(f'\,f\))*q{MCF(f'\,r%))f
ipif'\) + g(f\)Xp(f'\)
+ 9(f'j)^
Граф характеризации расположения орбит
MCF(f'^i,f'^j) - максимальная общая
фрагментов типов г1 и /2 в графе G
часть фрагментов/'', nf'^j,p~число вер­
(максимум коэффициента различия MDI3)
шин, q - число рёбер; и максимум коэффициеита различия МОП = (1 - Ш13).
Ряс. 1. Пример характеризации расположения фрагментов
по схеме переборно-группового подхода
Дополнение методов спектрального анализа графов учётом расположения
фрагментов на основе переборно-группового подхода резко повышает качество
проводимого подструктурного анализа, не понижая границу его применимости.
Рис. 2 иллюстрирует это утверждение: верхний график (круги) - время, затра­
чиваемое на получение помеченных фрагментов, нижний (треугольники) время анализа г-групп. Видно, что анализ г-групп занимает малую часть време­
ни, потраченного на получение помеченных фрагментов. Однако область при­
менения переборно-группового подхода в чистом виде ограничена. Во-первых,
помеченные фрагменты могут не пересекаться, в отличие от графов, у которых
всегда есть общий фрагмент. Во-вторьпс, анализ ?-групп не даёт никакой новой
информации о тождественных графах по сравнению с ГАГ. Поэтому на прак­
тике методы переборно-группового подхода либо применяются для анализа
Г М С с ярко выраженной симметрией, либо дополняют методы структурнохарактеристического подхода, предлагая уникальную возможность и в его рам­
ках анализировать расположение фрагментов с точностью до орбит Мрупп,
12
IWOO» '
l«00O ixmt
■
mom
110 000
10101»
moo»ЙОООО '
TOO» 6000050000
wooo
woo»
20 ( X » '
lOOCD «
' . »
«■
ГРЛФЮГРЛФЗО
ГРАФПО
ГРАФ170
ГРАФ2Э0
ГРЛФ290
П»АФ5М
ГРАФЛЮ
ГРАФ470
Рис. 2. Сравнение времени, затрачиваемого на построение баз помеченных фрагментов
и на анализ /-групп (ось X - графы с равномерно растущим числом вершин от 30 до 990,
число фрагментов также растёт линейно, ось ¥ - время работы в миллисекундах)
В третьей главе рассмотрен структурно-характеристический подход к
решению задач различения расположения фрагментов, основанный на анализе
структурных и числовых инвариантов фрагментов. Описывается его практиче­
ская реализация на основе построения и исследования g- и Ь-моделей графа
(математических моделей характеризации расположения фрагментов в графе,
предложенных Коховым В.А.) в априори заданных базисах СД. Этап получения
баз помеченных фрагментов полностью совпадает с описанным при реализации
переборно-группового подхода. Но далее производится построение g- или Ьмодели исследуемого графа и анализ структурных или числовых характеристи­
ческих инвариантов помеченных фрагментов, g- и 6-модели представляют со­
бой двудольные графы с весами (соответствующими помеченным фрагментам,
их классам или типам) на вершинах левой и правой доли и рёбрах, некоторые
их части являются структурными инвариантами помеченных фрагментов, а ин­
тегральные свойства этих частей - числовыми инвариантами. Использование gи ^-моделей позволяет построить стратифицированную систему отношений тэквивалентности помеченных фрагментов графа, монотонно изменяющихся с
изменением базисов СД.
Для усиления чувствительности локальных структурных инвариантов ав­
тором разработан и реализован универсальный метод уточнения разбиения
множества вершин графа на классы эквивалентности с использованием gмодели с произвольной правой частью и наличием одновершинных фрагментов
в левой части. Процедура итерационного уточнения разбиения (ИУР) позволяет
уточнять приближение не только к орбитам группы автоморфизмов, но и к ор­
битам её стационарных подгрупп (фиксаторов/стабилизаторов). Кроме универ­
сальной процедуры ИУР, использующей произвольную g-модель, созданы бо­
лее эффективные варианты, использующие g-модели в базисах цепей и циклов.
В этих вариантах исключено явное использование группы автоморфизмов
13
фрагмента. Использование процедуры РГУР позволяет уменьшить размерность
g-моделей и ослабить требования к базисам СД при сохранении качества реше­
ния задач различения расположения фрагментов. Как показывают эксперимен­
ты, базиса цепей длины от 1 до 5 уже достаточно для определения орбит прак­
тически всех графов, за исключением нескольких семейств регулярных графов.
Таким образом, ИУР может во многих случаях заменить анализ Г А Г и f-rpynn.
Отдельно рассмотрен специальный подкласс ^-моделей - графы располо­
жения цепей (ГРЦ), которые представляют собой иерархические g-модели с
равными долями в базисе связных цепей. Приведён алгоритм построения ГРЦ,
линейный относительно числа анализируемых цепей исходного графа. Орбиты
вершин ГРЦ при некоторых условиях соответствуют орбитам цепей исходного
графа. Это позволяет реализовать трансграфовый подход к решению задач из
класса Р Р Ф для цепных фрагментов. Поставлена задача построения графов рас­
положения фрагментов (ГРФ) для расширения трансграфового подхода на бо­
лее широкий класс фрагментов. Хотя эффективность трансграфового подхода
оказьгоается ниже, чем других подходов (в первую очередь из-за большого раз­
мера Г Р Ф ) , использование Г Р Ф облегчает работу с помеченными фрагментами
и позволяет наглядно отображать их свойства (рис. 3).
Рис. 3. Примеры визуализации симметрии расположения цепных фрагментов
(цифры на вершинах Г Р Ц обозначают длину соответствующих цепей исходного графа)
и визуализации вкладов цепных фрагментов в общую сложность графа
В четвёртой главе описывается авторский вклад в развитие АСНИ «Graph
Model Workshop» (созданной совместно с Коховым В.А. и Ткаченко С В . ) и её
функциональное наполнение, рассматриваются вопросы повышения эффектив­
ности решения задач структурного спектрального анализа и авторские алгорит­
мы, обсуждаются практические вопросы реализации программных средств и
проведения вычислительных экспериментов. АСНИ «Graph Model Workshop»
(далее - GMW) предназначена для проведения научных исследований, объектом
которых являются графовые модели систем, включая подготовку исходных
данных, автоматическое проведение вычислительных экспериментов и обра-
14
ботку их результатов (рис. 4). АСНИ работает под управление ОС Windows 98ХР. На базе GMW создаются программные средства для решения прикладных
задач и программные средства учебного назначения. GMW является открытой
системой с многоуровневым интерфейсом для подключения программных рас­
ширений, которые могут повышать функциональность всех операций, выпол­
няемых в АСНИ. Большинство программных средств, созданные автором, вхо­
дят в состав GMW и образуют её подсистемы. С их помощью можно проводить
следующие вычислительные эксперименты: проверка базы графов на наличие
изоморфных и выделение подмножества попарно неизоморфных графов; по­
парное сравнение характеристик симметрии (числа симметрии и др.) графов из
двух баз; построение по заданной базе графов новой базы со структурными ин­
вариантами исходных графов; многоэтапный эксперимент по характеризации
расположения фрагментов графов по схеме переборно-группового подхода;
многоэтапный эксперимент по характеризации расположения фрагментов гра­
фов по схеме структурно-характеристического подхода; построение и анализ
информационных вектор-индексов сложности и вектор-индексов структурной
спектральной сложности в произвольном базисе структурных дескрипторов.
Разработки автора также используются в экспериментах по анализу сход­
ства графов, проводимых совместно с Ткаченко С.В, и средствах структурного
поиска (иерархического поиска в базах структурной информации).
Я ! Дийя Правка В т
База Запуос Ccpwc Оюа Справка
Vif
Cftb
X t- 31 в ■
! ►
а X
ii:.ii
23 i ft" * «fl i ¥ -»§■ iii i «И «il S
Регудцрнаяатеаая толшягия
]B^ia*i'9
Рёбер: la
Рис. 4. Главное окно АСНИ «Graph Model Workshop» с открытой базой топологий КС
Подсистемы GMW создавались в основном в среде Borland Delphi, частич­
но - в среде Microsoft Visual C++ .NET, и представляют собой набор динамиче­
ски компонуемых библиотек (таблица 2).
15
Таблица 2
П а р а м е т р ы основных программных библиотек автора, содержащих расширения GMfV
№
1
Библиотека
Общие модули
Основные алгоритмы
Интерактивные расширения
2
(например, анализ t-групп)
Стандартные интерфейсные диа­
3
логи (например, ввод базисов СД)
Вспомогательные расширения
4
Количество
Объём
экспорти­ авторского
руемых
исходного
функций
кода, К Б
-
341
Количество
компили­
руемых
строк кода
-
Объём
машин­
ного
кода, К Б
-
168
1672
69552
619
36
1136
327687
4192
5
138
274564
1953
39
179
19751
217
Автором реализованы эффективные методы получения и хранения орбит
стационарных подгрупп ГАГ, что позволило уменьшить накладные расходы на
учёт симметрии графа для сокращения перебора при решении переборных (M*полных) задач структурного спектрального анализа. Порождающие множества
стационарных подгрупп строятся путём модификации сильного ПМ ГАГ, орби­
ты подгрупп хранятся в словаре на основе чёрно-красного дерева поиска.
Так, по методологии монотонного расширения частичных решений разра­
ботаны алгоритмы установления изоморфного вложения и поиска максималь­
ного общего фрагмента пары графов. Для симметричных графов время выпол­
нения данных алгоритмов с учётом симметрии уменьшается на несколько по­
рядков (с нескольких часов до секунд). Различные варианты учёта симметрии
исследовались при решении задачи декомпозиции графа на неизоморфные
фрагменты, причём её решение ускоряется практически для всех классов гра­
фов, но менее, чем в два раза. При разработке интерактивных алгоритмов (во
время выполнения которых человек указывает направление поиска решения,
осуществляемого компьютером с одновременной визуализацией процесса ре­
шения на диаграмме графа), учёт симметрии позволил предоставить пользова­
телю наглядную дополнительную информацию о структуре графа и отметить
заведомо тупиковые направления поиска. В главе также приводится пример
проведения сложного многоэтапного вычислительного эксперимента и анализа
его результатов, даётся перечень экспериментов, для автоматического проведе­
ния которых автором созданы расширения GMW.
Пятая глава содержит информацию о теоретических результатах иссле­
дования графовых моделей систем и применении авторских разработок в учеб­
ном процессе и прикладных областях.
Приведены результаты объёмных вычислительных экспериментов (обра­
ботано более 15 000 000 графов). Исследовались: симметрия расположения вер­
шин и более сложных фрагментов графов различных классов; связь симметрии
графа с его сложностью; отношения эквивалентности и толерантности графов
на основе g- и А-моделей; роль итерационных процедур в усилении чувстви­
тельности структурных инвариантов графов (особое вниманию уделено
g-моделям в базисе простых цепей); методы структурного поиска ТЫС с учё-
16
том расположения фрагментов. Результаты отдельных исследований опублико­
ваны в виде справочника по теории графов.
В соавторстве с Коховьп*! В.А. и Ткаченко С В . на базе АСНИ GMWсозда­
но четыре программных средства учебного назначения (ПСУН). П С У Н
«СТРИН» и ПСУН «Полигон алгоритмов структурной информатики» обеспе­
чивают компьютерную поддержку раздела «Основы структурной информати­
ки» дисциплины «Информатика». ПСУН «Интегрированная среда визуального
и алгоритмического решения задач на графовых моделях систем» и П С У Н
«Интегрированная среда исследования эффективности алгоритмов обработки
графовых моделей систем» обеспечивают компьютерную поддержку структур­
ного анализа и синтеза при выполнении лабораторных работ, курсовых проек­
тов, типовых расчётных заданий и УНИР студентов старших курсов. Информа­
ция о них доступна в Интернете по адресу www.graphmodel сот. Учебнометодические ковлплексы, в которые входят перечисленные выше ПСУН, удо­
стоены диплома П степени конкурса на лучшую разработку и внедрение в
учебный процесс новых информационных технологий в области обучения, по­
священного 75-летию М Э И (ТУ) в апреле 2005 года.
В заключении приведены основные результаты работы.
Основные результаты работы
1. Рассмотрены задачи, составляющие инвариантное ядро задач различе­
ния расположения фрагментов (РРФ) в графе для отношений ^эквивалентности и ^-эквивалентного вложения, а также расширяющие
их задачи различения т-эквивалентного расположения фрагментов в
графе, проанализированы подходы к их решению.
2. Развита методология переборно-группового подхода к характеризации
расположения фрагментов в графе. В рамках данной методологии раз­
работаны эффективные алгоритмы решения задач из класса Р Р Ф ,
включая алгоритмы:
1) канонизации представления помеченного фрагмента;
2) построения и анализа П М Г А Г и её стационарных подгрупп;
3) построения и анализа П М /-группы и её подгрупп;
4) построения и анализа матрицы пересечения фрагментов.
Это позволило характеризовать взаимное и относительное расположе­
ние произвольных фрагментов с точностью до орбит г-групп (то есть с
учётом симметрии исследуемого графа).
3. Разработаны алгоритмы решения задач из класса РРФ в рамках струк­
турно-характеристического подхода, включая алгоритмы:
1) построения и анализа g- и 6-моделей графов общего вида, в отли­
чие от алгоритмов, разработаш1ых Ткаченко С В . , позволяющие априо­
ри задавать базисы структурных дескрипторов;
2) построения и анализа графов расположения цепей (специализиро­
ванная версия с повышенной эффективностью);
17
3) итерационного уточнения классов эквивалентности вершин по ^модели с произвольной правой частью и специализированные, с повы­
шенной эффективностью, по g-модели в базисе цепей и циклов.
4. Реализованы универсальные методы учёта симметрии для сокращения
перебора при решении NP-полных задач структурного анализа. Осо­
бую роль данные методы играют в методологии монотонного расши­
рения частичных решений. В рамках данной методологии разработаны
авторские версии алгоритмов поиска максимального общего фрагмен­
та двух графов в смысле подграфа (на порядки возросла эффектив­
ность анализа симметричных графов, например, транзитивных, яв­
ляющихся моделями топологий вычислительных комплексов и сетей) и
поиска всех канонических изоморфных вложений фрагмента в граф (на
порядки возросла эффективность анализа высоко симметричных фраг­
ментов, например, звёзд и клик). Также учёт симметрии применён при
решении задачи декомпозиции графа на неизоморфные фрагменты (за­
метное повьппение эффективности), задачи поиска гамильтоновых це­
пей и циклов (визуализация симметрии при интера1сгивном выполне­
нии алгоритма) и других задач. Таким образом, показана значимость
учёта симметрии и высокая эффективность методов её учёта.
5. Созданы или расширены подсистемы АСНИ «Graph Model Workshopy
(среди них «Различение графов», «Симметрия расположения фрагмен­
тов графов», «g- и ^-модели графов», «Сложность графов», «Декомпо­
зиция графов на неизоморфные фрагменты», «СлучаЙ1ая генерация и
трансформация»). АСНИ «Graph Model Workshop» {GMW) зарегистри­
рована в Федеральной службе по интеллектуальной собственности, па­
тентам и товарньш знакам (СВИДЕТЕЛЬСТВО №2005612847 от
2.11.2005 г.) Программные разработки содержат более 3 МБ авторского
исходного кода и более 8 МБ исполняемого кода.
6. На основе подсистем GMW созданы четыре программных средства
учебного назначения для компьютерной поддержки раздела «Основы
структурной информатики» дисциплины «Информатика» и поддержки
дисциплин «Структурная информатика», «Дискретная математика»,
«Теория графов и комбинаторика», «Анализ и проектирование эффек­
тивных алгоритмов» и др.
7. Проведеьпл объёмные вычислительные эксперименты с использовани­
ем GMW. Их результаты позволили:
1) исследовать характеристики симметрии и построить симметричные
диаграммы транзитивных графов степени 4 с числом вершин до 31
(вошедшие в справочник [1]);
2) исследовать структурные и числовые инварианты графов и их
фрагментов на основе g- иft-моделей,предложенные Коховьш В.А.
(показана эффективность методов анализа сходства графов на их осно­
ве);
18
3) исследовать итерационные процедуры уточнения разбиения мно­
жества вершин графа на классы эквивалентности по ^-модели в базисе
цепей различной длины (подтвердилось резкое повышение чувстви­
тельности структурных инвариантов итерационного типа);
4) выделить графы, обладающих изоморфными примарньти подгра­
фами или примарными частичными графами, полз^енными удалением
вершин или рёбер из разных орбит (пример исследования оригиналь­
ного отношения эквивалентности графов).
Выводы
В работе анализируются и систематизируются задачи различения распо­
ложения произвольных фрагментов в графе и подходы к их решению. Задачи
различения расположения фрагментов в графе обобщают соответствующие за­
дачи различения графов, а также позволяют впервые поставить задачи различе­
ния графов с учётом расположения фрагментов. Эти задачи актуализировались
с развитием структурного спектрального анализа систем, их решение необхо­
димо в химической структурной информатике, структурной лингвистике, при
исследовании топологий вычислительных систем и сред, распознавании обра­
зов и в других прикладных областях.
Особое внимание уделено классам эффективно решаемых задач и повы­
шению чувствительности локальных инвариантов. В результате можно сделать
вывод о возможности практического применения методов переборногруппового подхода для исследования графов с числом вершин до 1000 при
размере фрагментов до нескольких десятков вершин на современном персо­
нальном компьютере. Методы структурно-характеристического подхода, кото­
рые требуют построения сложньк структурных инвариантов (g- и й-моделей),
не позволяют исследовать графы такого размера (граница применимости 150 вершин), однако предоставляют разнообразные схемы характеризации рас­
положения фрагментов по большому спектру отношений.
В результате объёмных вычислительных экспериментов показана роль ло­
кальных характеристических инвариантов, используемых совместно с процеду­
рами усиления их чувствительности (в данном случае - итерационного уточне­
ния разбиения множества вершин на классы эквивалентности), при анализе ин­
тегральных свойств графовых моделей систем.
Методы решения задач различения расположения фрагментов в графе реа­
лизованы в подсистемах АСНИ «Graph Model Workshop». Реализация эффек­
тивных методов анализа симметрии расположения фрагментов в графе позво­
лила повысить эффективность решения других задач структурного спектраль­
ного анализа (для некоторых классов графов на порядки). Этим была подтвер­
ждена общеметодологическая значимость учёта симметрии как универсально­
го метода повьппения эффективности обработки структурной информации.
19
1.
Основные работы, опубликованные по теме диссертации:
Незнанов А.А., Кохов В.А. Справочник по теории графов. Характери­
стики симметрии и сложности связных транзитивных графов степени 4
с числом вершин до 30 включительно. — М. Деп. в ВИНИТИ, №109432004,2004.-418 с.
2. Кохов В.А., Ткаченко С В . , Незнанов А.А. Построение алгоритмов и
программ быстрой обработки физико-химической информации. — От­
чёт по НИР, выполненной на кафедре П М . Зарегистрированная тема
НИР М Э И № 1147970,2001.
3. Незнанов А.А., Кохов В.А. Методы анализа симметрии и сложности
структур в базисе цепных фрагментов. // Тезисы докладов шестой еже­
годной международной научно-технической конференции студентов и
аспирантов
«РАДИОЭЛЕКТРОНИКА,
ЭЛЕКТРОТЕХНИКА
И
ЭНЕРГЕТИКА». М.: МЭЩТУ), 2000. - с. 235-236.
4. Незнанов А.А., Кохов В.А. Методы определения изоморфного вложе­
ния граф-моделей и их применение для анализа симметрии и сложности
систем. // Тезисы докладов седьмой ежегодной международной научнотехнической
конференции
студентов
и
аспирантов
«РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА». М.:
МЭЩТУ), 2001. - с. 264-265.
5. Незнанов А.А., Кохов В.А. Структурная информатика: симметрия
структур. // Доклады международной конференции «Информационные
средства и технологии». (МФИ-2001), Т.З, Москва, 2001.
6. Незнанов А.А., Кохов В.А. Подсистема «Симметрия фрагментов струк­
тур» 111111 «СТРИН-2.0». // Тезисы докладов восьмой ежегодной меж­
дународной научно-технической конференции студентов и аспирантов
«РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА». М.:
М Э Щ Т У ) , 2002. - с.281-282.
7. Ткаченко С В . , Незнанов А.А., Кохов В.А- Компьютерная поддержка
курса «Основы Структурной информатики». // Доклады международной
конференции «Информационные средства и технологии». (МФИ-2002),
Т.2, Москва, 2002. - с. 55-58.
8. Незнанов А.А., Кохов В.А. Методы декомпозиции графов на неизо­
морфные фрагменты с учётом симметрии. // Тезисы докладов девятой
ежегодной международной научно-технической конференции студентов
и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И
ЭНЕРГЕТИКА». М.: МЭЩТУ), 2003. - с. 300-301.
9. Незнанов А.А., Кохов В.А. Алгебраический подход к анализу симмет­
рии расположения фрагментов графа. // Доклады международной кон­
ференции «Информационные средства и технологии». (МФИ-2003), Т.1,
Москва, 2003. - с . 216-219.
10. Незнанов А.А., Кохов В.А. Сходство систем в топологии надсистемы.
// Научная сессия МИФИ-2004: Сб. науч. трудов. Т.З, М.:МИФИ, 2004. с. 198-199.
20
05- 22 1 10
11. Незванов А.А., Кохов В.А. Базовые алгоритмы структурной информа­
тики: декомпозиция графов. // Тезисы докладов десятой ежегодной ме­
ждународной научно-технической конференции студентов и аспирантов
«РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА». М.:
МЭИ(ТУ), 2004. - с. 326-327.
12. Кохов В.А., Незнанов А.А., Ткаченко С В . Компьютерные методы
анализа сходства трафов. // Десятая Национальная конференция по ис­
кусственному интеллекту с международным участием. КИИ-2004: Тру­
ды конференции. В 3-х т. Том 1. М.: Физматлит, 2004. - С162-171.
13. Кохов В.А., Незнанов А.А., Горшков С.А. ПИП «СТРИН+»: Подсис­
тема сравнительного анализа структур. // Доклады международной кон­
ференции «Информационные средства и технологии». (МФИ-2004), Т.1,
Москва, 2004. - с. 215-218.
14. Незнанов А.А., Кохов В.А. Базовые алгоритмы структурной информатики: поиск всех канонических изоморфных вложений фрагмента в
граф. // Тезисы докладов одиннадцатой ежегодной международной на­
учно-технической
конференции
студентов
и
аспирантов
«РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТШСА». М.:
МЭЩТУ), 2005.-с. 347-348.
Подписано в печать
Л1й'&д'
3mi.SW
Тир. fOD П.Л./Д4
Полиграфический центр М Э И (ТУ)
111250, г. Москва, ул. Красноказарменная, д. 13
Р Н Б Русский фонд
20064
19749
/
'
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 142 Кб
Теги
bd000100890
1/--страниц
Пожаловаться на содержимое документа