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

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

005051190

Старичкова Юлия Викторовна

Исследование методов и разработка программных средств анализа структурной сложности и симметрии графовых моделей систем

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

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

4 АПР 2013

Москва, 2013

005051190

Работа выполнена на кафедре анализа данных и искусственного интеллекта Национального исследовательского университета «Высшая школа экономики»

Научный руководитель: Незнанов Алексей Андреевич

кандидат технических наук, доцент, доцент кафедры анализа данных и искусственного интеллекта федерального государственного автономного образовательного учреждения высшего профессионального образования Национального исследовательского университета «Высшая школа экономики»

Официальные оппоненты: Лаговский Борис Андреевич

доктор технических наук, доцент, профессор кафедры прикладной математики федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный технический университет радиотехники, электроники и автоматики» (МГТУ МИРЭА)

Троицкий Виктор Валерьевич

кандидат технических наук, доцент, начальник отдела разработки ЗАО «СУП Медиа»

Ведущая организация: Федеральное государственное автономное обра-

зовательное учрезедение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

Защита состоится «17» апреля 2013 г. в 14:00 на заседании диссертационного совета Д 212.131.05 при МГТУ МИРЭА по адресу: Москва, 119454, пр-т Вернадского, д. 78, Д412

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА.

Автореферат разослан «15» марта 2013 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу 119454, г. Москва, пр-т Вернадского,78, диссертационный совет Д 212.131.05

Ученый секретарь .

диссертационного совета Е.Г.Андрианова

к.т.н, доцент ¿у

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

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

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

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

Объектом работы являются ГМС в виде транзитивных графов степени 4 и ориентированных графов. Предметом - их характеристики структурной сложности (индексы, вектор-индексы, ö-модели) и симметрии (от порядка группы автоморфизмов до структуры стационарных подгрупп). Работа продолжает исследования в области прикладной теории графов, проводимые В.А. Коховым, A.A. Незнановым. В ней рассматриваются вопросы создания программных средств, использующих взаимосвязь структурной сложности, сходства и симметрии для графовых моделей различных классов.

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

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

1. Даётся обзор и анализируются классические модели структурной сложности ГМС, в частности, оригинальный представительный класс моделей,

предложенный В.А. Коховым и реализованный в виде программных средств для класса обыкновенных графов C.B. Ткаченко и A.A. Незнановым.

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

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

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

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

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

Научные результаты и их новизна

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

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

3. В соответствии с предложенной классификацией ТГС4 разработан универсальный расширяемый программный комплекс генерации семейств ГМС, позволяющий, в том числе, безызбыточно порождать все ТГС4 до 30 вершин включительно с различными вариантами полностью симметричных диаграмм.

4. Для семейств ТГС4 получены результаты сравнительного анализа характеристик симметрии и структурной сложности с использованием индексов и вектор-индексов спектральной сложности, è-моделей в различных базисах, позволившие упорядочить семейства по различным мерам структурной сложности.

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

Оригинальная классификация и методы генерации семейств ТГС4 позволят повысить качество систем управления и топологий вычислительных систем с точки зрения сложности, надёжности и живучести.

Методы исследований и достоверность результатов. Задачи исследования решаются в работе с помощью методов прикладной теории графов, теории групп, теории вычислительной сложности алгоритмов, анализа и построения эффективных алгоритмов и др. В работе существенно использованы результаты, полученные В.А. Коховым, C.B. Ткаченко, A.A. Незнановым, И.А. Фараджевым, В. D. McKay, G. F. Royle, E. Luks. Основой получения новых научных результатов являются объёмные вычислительные эксперименты с использованием авторских и сторонних программных средств. При малой сложности исходных данных результаты вычислительных экспериментов на тестовых наборах исходных данных совпадают с известными результатами. При обработке сложных исходных данных сравнивались результаты, полученные различными методами решения одной и той же задачи.

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 13-й и 14-й международных научно-технических конференциях студентов и аспирантов «радиоэлектроника, электротехника и энергетика» (г. Москва, 2008-2009), на международных форумах информатизации МФИ-2009, МФИ-2010 (международные конференции «Информационные средства и технологии», г. Москва, 2009-2010), на тринадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2010 (г. Тверь, 2010), на семинарах ИППИ РАН и НИУ ВШЭ (г. Москва, 2012).

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

1) анализе современных моделей структурной сложности ГМС, описании представительных базисов структурных дескрипторов для орграфов, создании оригинальных программных средств анализа сложности орграфов в различных базисах структурных дескрипторов;

2) выделении бесконечных и конечных семейств ТГС4, безызбыточно покрывающих все ТГС4 до 30 вершин, создании программных средств синтеза и визуализации представителей семейств ТГС4;

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

Публикации. Основные результаты, полученные в процессе выполнения диссертационной работы, опубликованы в 3 статьях (из них - 2 из списка ВАК РФ), в трудах и тезисах докладов конференций, учебно-методических пособиях.

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы (76 наименований) и 3 приложений. Она содержит 127 страницу в основной части и 309 страниц приложений.

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

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

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

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

Далее уточняются объекты исследований: ГМС в виде обыкновенных іра-фов и орграфов, а также их подклассы - транзитивные, планарные и пр. Далее под графом будем понимать ГМС произвольного класса. Граф 0\ изоморфно вкладывается в граф С2, если С2 изоморфен Є і или в Є2 есть часть, изоморфная С]. Части графа определяются в соответствии с алгебраической системой Клода Бержа. Абстрактный тип или абстрактный граф (I) - произвольный граф, определённый с точностью до автоморфизма. Группу его вершинных автоморфизмов (также с точностью до изоморфизма) обозначим через Лш{(). Граф г назовём фрагментом графа С, если I изоморфно вкладывается в Є в некотором заранее определённом смысле, то есть, если необходимо, будем различать фрагменты-подграфы, фрагменты-частичные графы и т.п. Теперь можно провести формализацию результата изоморфного вложения фрагмента в граф. Помеченным графом называется граф, каждой вершине которого сопоставлен уникальный вес (пометка), то есть каждая вершина которого имеет ^уникальный атрибут. Наличие пометок будем обозначать верхним индексом Понятие пометок вершин графа отличается от понятия нумерации (идентификации) вершин с целью хранения структурной информации.

Помеченным фрагментом (ПФ) типа / графа С назовём помеченный граф і, пометками которого являются вершины графа С, образующие (вместе с некоторыми инцидентными им рёбрами) часть графа С, изоморфную Л Через Ґ'м(0) = ...,/'",„} обозначим множество всех помеченных фрагмен-

тов типа / графа О.

Для различения абстрактного типа и типов реальных фрагментов графа будем называть тип фрагмента с заданной нумерацией вершин идентификационным типом. Специального обозначения вводить не будем, так как из контекста обычно ясно, введена нумерация вершин или нет. Не ограничивая общности, можно считать, что вершины нумеруются числами из натурального ряда: (1,2, ...,/;), гдер - число вершин графа. Это позволит записывать ПФ в виде вектора пометок, в порядке, задаваемым нумерацией вершин идентификационного ти-

па. Если на множестве вершин абстрактного типа фрагмента г и графа С задана нумерация, то помеченный фрагмент графа может быть представлен различными изоморфными вложениями - отображениями номеров вершин г в номера вершин С. Число изоморфных вложений, представляющих один и тот же помеченный фрагмент графа, равно порядку группы автоморфизмов абстрактного типа ( | Аш{г) |). Таким образом, число всех изоморфных вложений фрагмента типа I в граф О равно | /* (С) | • | Ли1(1) |. Помеченный фрагмент удобно представлять одним из изоморфных вложений, которое назовём каноническим.

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

Вводится понятие инварианта графа и классифицируются пространства характеризации структурной сложности, определяются индексы структурной сложности в виде чисел, векторов, матриц и структурных моделей. Далее излагаются различные подходы (К. Шеннона, А.Н. Колмогорова, С. Бертца, П. Биллета, Д. Бончева, М. Рандича, В.А. Кохова и др.) к пониманию и формализации структурной сложности графов и показывается, что исследование сложности неотделимо от исследований симметрии. Спектральная структурная сложность графа определяется разнообразием и количеством его фрагментов. В её основе лежат понятия базиса и структурного спектра. Базис фрагментов (В) -упорядоченный набор абстрактных типов (возможно, с весами). Структурный спектр 55(&75) графа С в базисе произвольных абстрактных типов В = (/,, 12, ..., /*) определяется следующим образом:

55(С/5) = <Н',, Н'2, ..., И'Р>, где и^- - число канонических изоморфных вложений (в некотором смысле) абстрактного типа /,• в граф С.

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

Вектор-индекс структурной спектральной сложности К_/55С(С/ В) графа С в базисе произвольных абстрактных типов В = (1], ь, ..., к) определяется следующим образом:

К_/55С(С/Д) = ^ЧБСЦ,), и'2*/5С(/2), ..., щЧБС((к)>, где IV, - число канонических изоморфных вложений (в некотором смысле) абстрактного типа /,■ в граф С, /5С(7,) - некоторая мера сложности типа

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

Шенноновский подход к формализации структурной сложности основан на учёте симметрии вершин и более крупных ПФ графа. Через Aut(G) обозначим группу автоморфизмов графа G (ГАГ), а через \Aut(G)\ - порядок группы. Если \Aut(G)\ = 0, то все элементы графа уникальны с точки зрения расположения в нём, а если \Aut(G)\ > 0, то граф обладает нетривиальной симметрией, и его элементы могут быть автоморфны. Орбита вершины v е V — подмножество Q(Aut(G), v) вершин графа G, которые могут быть отображены на вершину v:0(/!m/(G),v) = {v' :[3g е Aul(G): g(v') = v]j. Граф называется транзитивным, если все его вершины принадлежат одной орбите, и тождественный, если число орбит равно числу вершин. Симметрия более крупных ПФ определяется аналогично, с использованием индуцированных представлений Aut(G) на множестве ПФ конкретного типа (/-группы - Aut'(G)). Чем больше порядок группы, тем крупнее могут быть классы эквивалентности элементов (орбит) графа по отношению «быть автоморфными». Можно определить информационное содержание (количество информации), приходящееся на один фрагмент из

k I p(DI I

F""(G)S по формуле HC' =-^C, Iog2C,, где Ct = —в предположении, что

г-1 IF I

множество F*1'' разбивается на к классов эквивалентности F^',-, / б (1, к). На основе понятия информационного содержания ПФ можно построить большое число обобщений, включая индексы и вектор-индексы информационной сложности графа в различных базисах.

В работе также рассматривается предложенная В.А. Коховым' стратифицированная система структурных моделей структурной сложности (GMS), объединяющая несколько подходов. Наиболее общими являются g-модели, представляющие собой двудольные графы, вершины которых взвешены помеченными фрагментами или их классами (вплоть до орбит /-групп), а рёбра - различными характеристиками взаимного расположения помеченных фрагментов/классов/орбит. ¿-модели и их подмодели являются наиболее важными с практической точки зрения, так как в них вершины одной из долей взвешены абстрактными типами, что делает вершины доли уникальными и позволяет применить полиномиальные алгоритмы поиска максимального общего фрагмента двух ¿-моделей для эффективной реализации обобщённого подструктур-ного подхода к анализу сходства графов.

Также в главе даётся обзор других популярных подходов к формализации структурной сложности, и приводятся примеры практического применения соответствующих моделей. Дополнительно даётся обзор методов визуализации ГМС, что будет востребовано в главе 3.

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

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

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

Во второй главе исследуется структурная сложность орграфов различных классов на основе как ранее разработанных программных средств построения индексов сложности, так и на основе оригинальной системы построения вектор-индексов спектральной сложности и ¿-моделей в базисах путей, контуров и ориентированных цепных фрагментов (ОЦФ). Базисы путей и контуров ограниченной длины (ОР0.„ и ОС0.„) для орграфов уже рассматривались ранее и реализуются для полноты программных разработок и сравнения результатов.

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

1.1

мы получаем 2^' ОЦФ для для нечётного ц и {2' л -22 ) - для чётного. Разница в формулах количества фрагментов объясняется тем, что ОЦФ на нечётном числе дуг являются тождественными, а на чётном - могут иметь нетривиальный автоморфизм. В таблице 1 приведены диаграммы базовых ОЦФ и их стандартных значений сложности. Отметим, что сложность элементов базиса задаётся априори и может считаться атрибутом базиса.

Таблица 1. Минимальные ОЦФ и их стандартная сложность

№ 1 Текстовое представление ОЦФ I Изображение ОЦФ ® Сл. 1

2 0 3

3 00 9

4 01 10

5 ¡0 11

6 ООО 31

7 001 32

8 100 33

9 010 34

В качестве примера рассмотрим орграф, изображённый на рис. 1. Используем фрагменты с 1 по 5 из таблицы 1 в качестве как левого, так и правого базисов. Полученная ¿-модель представлена на рис. 2.

Рис. 1. Исходный орграф (несвязный)

На вершинах правой доли (типах фрагментов) показано количество соответствующих помеченных фрагментов, а на вершинах левой доли (помеченных фрагментах) - каноническое представление ТТФ.

Рис. 2. 6-модель в структурной форме (взвешенный двудольный граф)

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

Количество вершив в орграфе

Рис. 3. Сравнение времени, затрачиваемого на построение моделей сложности (треугольники - 6-модель HM(tDCF<i-i(nii>) lOCf'os) в базисе ОЦФ, крестики - 6-модель BM(tDPn.s(r\w) tDPrui) в базисе путей, квадраты - ISSC(G/DCFM), круги - ISSC(G/DP„.}))

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

В результате рассмотрения современного уровня исследований на стыке теории графов и теории групп предложена оригинальная классификация ТГС4, основанная как на характеристиках стабильности симметрии, так и на визуализации диаграмм ТГС4, отражающих симметрию. Эта работа опирается на опыт многочисленных исследователей проблем, связанных с изоморфизмом/автоморфизмом и транзитивными графами, как наиболее сложными случаями входных данных (L. Babai, M. Luks, B.D. McKay, G.F. Royle, G.Miller, J. Hoprcoft, G. Gati, P. Potocnik, И.А. Фараджев, C.A. Евдокимов, Б.Ю. Вейсфей-лер, B.A. Кохов и др.). Исходными данными является полная база ТГС4 до 30 вершин включительно и информация о строении ГАГ1.

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

Для полноценной классификации ТГ требуется рассмотреть более подробно строение группы автоморфизмов. Фиксатор (стабилизатор) вершины у е V - подгруппа Аш(С, у), оставляющая неподвижной вершину у, то есть = 0') = у}. Фиксатор подмножества вершин У0 с У -

подгруппа Аш(С, V0), оставляющая неподвижной каждую вершину множества V0, то есть Аи/(С,У°) = р| Аш(С^). Стабилизатор подмножества вершин

У1 с У - подгруппа А и 1[С, У1], оставляющая множество V1 неподвижным, то есть Аи1[С,У1 ] = {?£Л»/(С):VI-еК'[я(у)еК1 ]}.

Орбита вершины V е У относительно фиксатора Аи1(С, У0) - подмножество 0(Аи/(С, У0), у) вершин графа О, которые могут быть отображены на вершину V при условии фиксации подмножества V с У: = = V]}. Орбита вершины у е Vотно-

сительно стабилизатора АШ{С, У1] - подмножество 0(Лм/[О\ К1], у) вершин графа С, которые могут быть отображены на вершину V при условии стабилизации подмножества Vх с У:&{АШ[в,У1],у) = {у':е Аш[С,V1]:#(у') = у]}.

В.А. Коховым в 1986 г. введены удобные интегральные характеристики симметрии. Подмножество вершин У а V называется экстремальным подмножеством нетождественной стабильности графа, если справедливо (Аги{С, V) ФЕр)&.(У\>еУ\ V : Ан1(С, У и {у}) ~ Ер). Подмножество вершин

У* с У называется экстремальным подмножеством тождественной стабильности графа, если справедливо (Аш(С,У*)*Ер)&(ЫеУ*:Аш(С,У*\{у})ФЕр). Пусть П~ и 1Г обозначают

соответственно множество всех подмножеств V и V* вершин графа С. Тогда

I// = гшп \У'\ — число тождественной стабильности графа, а % = тах -

гея-' 1 у~еП

число нетождественной стабильности графа. Числом тождественности /(б) графа С называется минимальное число новых вершин, необходимых для построения тождественного надграфа Об графа С, то есть

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

Г " ' •

13

Основной результат главы - каталог семейств связных транзитивных графов степени 4 (59 бесконечных и 72 конечных).

Таблица 2 представляет собой элемент каталога семейств ТГС4 без информации о структурной сложности, а именно — семейство 0_21. Для каждого семейства указываются интегральные характеристики семейства: ГУ - число вершин в первом графе семейства; ЦУ- число вершин в первом уникальном графе семейства (когда происходит стабилизация характеристик семейства); РМ - число вершин последнего графа в семействе, если оно конечное (в данном примере отсутствует); ЗУ - шаг числа вершин; \Аи1{С)\ - число симметрии (порядок группы автоморфизмов); у - число тождественной стабильности; % -число нетождественной стабильности; п - порядок группы предыдущего представителя семейства. Видно, что С_21 содержит графы с регулярной группой, у которых порядок ГАГ равен числу вершин графа. Далее приведены все существенно различные максимально симметричные прорисовки диаграмм этого семейства (в данном случае - 6 вариантов).

_Таблица 2. Пример информации о семействе ТГС4

№ 15. Название: С21

IV 5К V X \АМ{С,)\ \АШ(С) |

16 18 2 1 0 18 п+2

Известные представители: 16-4-2, 18-4-5, 20-4-14, 22-4-6, 24-4-22, 26-4-2, 28-4-17, 30-4-11

Диаграммы трёх первых представителей, начиная с уникального:

Другие варианты прорисовок диаграмм представителей семейства:

:

Каталог также содержит большой объём дополнительной информации. Так, таблица 3 - пример одной из классификационных таблиц.

Таблица 3. Классификация бесконечных семейств ТГС4 по числу нетождественной стабильности

№ X Кол-во семейств Идентификаторы семейств

1. 0 19 G_21, G_22, G.27, G_28, G_29, G_30, G_35, GJ6, GJ1, CJ8, G_74, G 78, G 117, G 214, G 215, G 217, G. 220, G_233, G_237

2. 1 И G 1, G 2, G 5, G 6, G 7, G_102, GJ 07. G l 08, G .119, G 209, G_231

3. 2 19 G 11, G_12, G_13, G_14, G_15, G_16, GJ7, G_18, G_20, G_33, G_42, G_103, G_125, G_210, G_211, G_219, G_222, G_230, G_239

4. 4 3 G 26, G56, G 238,

5. 10 1 G 10000 4

6. /+1 1 G 10000 1

7. ./+2 2 G 1000 2, G 10000 3

8. /44 2 G 25, G 68

9. 7+8 1 G 203

Для обеспечения и проверки уникальности представителей семейств среди всех ТГС4 построен лес семейств. Его основное дерево имеет корнем клику на 5 вершинах. Каждая развилка в лесе обозначает порождение нового семейства с выделением первого уникального представителя семейства. Лес покрывает все ТГС4 до 30 вершин включительно (289 графов), то есть в нём 289 вершин. Бесконечные семейства образуют подграф из 194 вершин. Остальные вершины обозначают конечные семейства. Интересно, что некоторые графы малого размера не попали в основной лес бесконечных семейств. Например, из двух графов на 8 вершинах один входит в дерево с корнем в клике на 5 вершинах, а второй расположен отдельно. Это обусловлено требованием безызбыточности семейств. Сам лес семейств реализован в виде интерактивной графовой модели.

Проведён анализ спектральной сложности бесконечных семейств ТГС4. Показано, что JSSC в различных базисах различным образом коррелирует с характеристиками симметрии, что важно при выборе необходимого семейства при синтезе структуры реальной системы с заданными характеристиками.

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

На базе GMW создаются программные средства для решения прикладных задач и программные средства учебного назначения. GMW является открытой

системой с многоуровневым интерфейсом для подключения программных расширений, которые могут повышать функциональность всех операций, выполняемых в АСНИ. Реализованные автором программные средства можно разделить на два класса: анализа структурной сложности орграфов и синтеза графов. Разработки автора также используются с целью расширения доступных отношений сходства структур в экспериментах по анализу сходства графов на основе структурно-характеристического подхода. ■ - ~

[|=| Файл Правкз Вт Грзф Фрагмент Запуск Сервис Окна Справка

й-у:^" их

«Sh:.I ЕЗ Фрагмент

Окна ,............-.......................

ЯЯ Ошо 6а... : ;

31 TI ►вин

Расстояние - 4

Д Ошо еж..;

62

......M¿_

12-4-1

тз

шшштж

12-4-7 т

G23

тл в

и Вершин; 2®

Л »1

% 4

В \ Е«*

Ш Изменен |

¡Mili

Рис. 4. Главное окно АСНИ «Grapli Model Workshop» (окно редактирования графа содержит лес семейств ТГС4)

Программные средства реализованы в основном в среде Embarcadero RAD Studio (Delphi) для ОС Microsoft Windows и представляют собой набор динамически компонуемых библиотек (таблица 4) и отдельных средств организации интерфейса с пользователем.

Таблица 4. Параметры программных библиотек, содержащих расширения GMW

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

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

I Синтез транзитивных топологий 3 114 98742 2145

2 Вычисление моделей сложности орграфов 9 93 62451 2602

3 Вспомогательные программы 10 36 9735 142

В части анализа структурной сложности орграфов наиболее интересны алгоритмы вычисления индексов, вектор-индексов и построение /»-моделей сложности в базисах ОЦФ. Данный базис, являясь уникальным именно для орграфов, позволяет эффективно вычислять изоморфные вложения фрагментов ограниченного размера и даёт многообразие оценок сложности с высокой дискриминирующей способностью.

Система анализа спектральной сложности орграфов включает редактор базисов ОЦФ. На рис. 5 представлен внешний вид редактора. Он позволяет задавать элементы базиса различной длины, их индексы структурной сложности, а также загружать/сохранять базисы в собственном формате. Основной сценарий использования системы - выбор и сохранение базиса, построение и сохранение ¿-моделей для базы ГМС, использование сохранённых моделей сложности для анализа сходства или решения других задач. Для подтверждения корректности и оценки временной вычислительной сложности алгоритмов генерации /БС(С/ОР) в базисе путей, №С(С/ОС) в базисе контуров, ¡8С{ОЮСР) в базисе ОЦФ и построения ¿-моделей в базисе путей, контуров и ОЦФ были проведены объемные вычислительные эксперименты на семействах одно-, двух-, трехсвяз-ных орграфов различной сложности. Особенностью вычислений является последовательное наращивание длины путей и ОЦФ (длина < 10) при вычислении индексов структурной сложности и построении ¿-моделей для каждого семейства.

Рис. 5. Диалог создания базиса структурных дескрипторов (ориентированных цепных фрагментов)

Для применения при решении прикладных задач реализован учёт произвольных весов вершин и дуг орграфов. В таком виде средства анализа структурной сложности использовались в проектах по анализу данных (graph mining)

для анализа сходства понятийных структур (conceptual graphs) и компьютерной лингвистике для выявления схожих цепочек в структурных моделях текстов.

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

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

| Файл Генерацт Ввд Помощи . Сектетво Варшнт Превст. 1

3

О

о

«

о

□ Основные гйрзметрй генерации IB Генерация с начала

С гервего уникального представ... Р

КйВДЫЙ?)-ЬЙГрзф ;

0 Генераций с задвинь^ числом eepimH Г"

Нйчдавмон -ясш- sffpuaiH 5

Конечной ж/к: 18 В Параметры еь«ес&а®АСНИ

В Создать новую §азу Р

Стия» дяя новой Safe; Fi'ipjri

Диапазон козрдмнат ЮС

Масштабирования по размеру oitna |

Выбрано семейств - 3 \ Будет сгенерировано графов - 24

Рис. 6. Интерфейс подсистемы ТгапяСеп (каталог семейств и параметры генерации)

Система может быть легко расширена для синтеза других семейств путём добавления в базу семейств новых скриптов генерации. Именно это позволило применить генератор при решении задач оптимизации систем управления, когда потребовалась генерация: семейств транзитивных графов степени 3 и 5. Наиболее востребованным оказалась возможность выбора семейства с заданной длиной минимальных циклов, которые выступали в роли проектных групп, в то время как рёбра, не входящие в минимальные циклы, соответствовали передаче результатов деятельности проектных групп.

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

На базе разработок автора созданы программные средства учебного назначения, внедрённые в учебный процесс НИУ МЭИ и НИУ ВШЭ по дисциплинам «Теория графов и комбинаторика», «Прикладная теория графов», «Практикум на ЭВМ» и снабжённые методической поддержкой.

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

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

1. Рассмотрена проблема определения структурной сложности систем и задачи анализа структурной сложности, проанализированы подходы к их решению.

2. Развита методология анализа структурной сложности орграфов в базисах ориентированных цепных фрагментов (ОЦФ). Предложены системы базисов ОЦФ и реализованы алгоритмы:

1) эффективного поиска вложений элементов базиса ОЦФ в исследуемый орграф;

2) построения и анализа моделей структурной сложности (индексов и вектор-индексов спектральной сложности, ¿-моделей) для орграфов общего вида.

Это позволило повысить качество и эффективность решения задач различения и анализа сходства орграфов.

3. На основе результатов, полученных ранее при изучении конечных групп и конструктивного перечисления транзитивных графов, предложена оригинальная классификация связных транзитивных графов степени 4 (ТГС4) с выделением конечных и бесконечных семейств, причём критериями выделения, наряду с классическими параметрами, являлись также характеристики стабильности симметрии, структурной сложности и варианты прорисовки диаграмм.

4. Предложенная классификация позволила создать каталог семейств ТГС4 (59 бесконечных и 72 конечных семейства), причём представители семейств безызбыточно покрывают все ТГС4 до 30 вершин.

5. Созданы программные средства структурного анализа (среди них «Сложность орграфов в цепных базисах», «TransGen - система синтеза транзитивных топологий»). Программные разработки содержат более 400 КБ авторского исходного кода и более 6 МБ исполняемого кода. Большинство программных разработок способны интегрироваться в АСНИ «Graph Model Workshop».

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

7. На базе программных разработок созданы программные средства учебного назначения для поддержки дисциплин «Теория графов и комбинаторика», «Практикум на ЭВМ», «Прикладная теория графов».

8. Проведены объёмные вычислительные эксперименты с использованием GMW и авторских программных разработок с целью исследования:

1) характеристик симметрии и сложности ТГС4, что позволило подтвердить корректность классификации и построить симметричные диаграммы представителей семейств ТГС4 (более 120 экспериментов, более 1,5 лет машинного времени);

2) структурной сложности семейств ТГС4 из каталога (см. пункт 4) в различных базисах (12 базисов, более 60 экспериментов, более недели

машинного времени), что позволило дополнительно классифицировать семейства и расширить множество параметров генерации семейств; 3) числовых и структурных инвариантов орграфов и их подклассов (например, планарных орграфов) на основе g- и ¿-моделей В.А. Кохова в различных базисах (более 30 базисов, более 200 экспериментов, более года машинного времени), что позволило, например, уточнить различия в дискриминирующей способности базисов ОЦФ и базисов путей, полупутей, контуров.

Выводы

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

Методы построения различных моделей сложности орграфов реализованы в авторских программных средствах, способных работать как независимо, так и в составе АСНИ «Graph Model Workshop». Результаты объёмных вычислительных экспериментов свидетельствуют, что при анализе спектральной сложности орграфов выбор базиса приобретает ещё большее значение, чем в случае обыкновенных графов. При исследовании орграфов получены результаты по количественному анализу индексов структурной спектральной сложности орграфов различных классов в базисах ориентированных цепных фрагментов и показан эффект повышения различающей способности от выбора базиса ОЦФ определённого вида. Граница применимости сложных структурных моделей сложности (¿-моделей) также повышается при использовании ОЦФ. При этом базис ОЦФ сохраняет все полезные свойства базиса путей: универсальность, наращиваемость и т.п., но является более естественным для орграфов, так как его наращивание не зависит от ориентации дуг. При практическом применении это позволило намного точнее решать задачи определения сходства структур, связи в которых имеют явное направление: «подчинение» в синтаксических деревьях, «объект-свойство» в понятийных структурах, «следование» в диаграммах бизнес-процессов.

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

■ . ; J

і . .

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

1. Старичкова Ю.В., Незианов A.A. Выделение, генерация и визуализация семейств транзитивных графов степени 4 по характеристикам симметрии и структурной сложности / Вестник Тамбовского университета. Серия: Естественные и технические науки, 2012. -Т.2. Вып.2. - С. 532-547. - 1,1 п.л. (вклад автора 1 п.л.)

2. Старичкова Ю.В., Незнанов A.A. Программный комплекс для генерации семейств транзитивных графов степени 4 / Бизнес-информатика, 2011. - № 3. - С. 36-44. - 0,8 п.л. (вклад автора 0,6 п.л.)

3. Старичкова Ю.В., Незнанов A.A. Программные средства для построения и исследования моделей структурной сложности орграфов // Двенадцатая национальная конференция по искусственному интеллекту с международным участием. КИИ-2010. Труды конференции. Т. 4. - М. : Физ-матлит, 2010. - С. 34-40. - 0,5 пл. (вклад автора 0,4 пл.)

4. Акчурин P.M., Старичкова Ю.В., Шаграев А. Г. Множество операций преобразования структур, Доклады международной конференции «Информационные средства и технологии». (МФИ-2009), Т.2, Москва, 2009. - 0,2 п.л. (вклад автора 0,1 пл.)

5. Старичкова Ю.В., Незнанов A.A. Улучшенная классификация и генерация транзитивных графов степени 4 // Доклады международной конференции «Информационные средства и технологии». (МФИ-2008), Т.2, Москва, 2008. - С. 75-79- 0,3 п.л. (вклад автора 0,2 пл.)

6. Старичкова Ю.В., Кохов В.А. Связность, симметрия и сложность пленарных графов // Тезисы докладов 14-й международной НТК студентов и аспирантов «Радиоэлектроника, электротехника и энергетика», Т1. -М., МЭИ, 2008. - С. 308-309. - 0,08 п.л. (вклад автора 0,07 п.л.)

7. Старичкова Ю.В., Незнанов A.A. Свидетельство о государственной регистрации программы для ЭВМ «Генератор семейств транзитивных графов степени 4» № 2012613386.

Национальный исследовательский университет «Высшая школа экономики»

04201355022

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

Старичкова Юлия Викторовна

Исследование методов и разработка программных средств анализа структурной сложности и симметрии графовых моделей систем

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

Диссертация на соискание ученой степени кандидата технических наук

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

Москва, 2013

Содержание

ВВЕДЕНИЕ.............................................................................................................................................4

Объект и предмет работы.........................................................................................................................................4

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

Цель работы ......................................................................................................................................................5

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

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

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

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

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

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

Публикации ......................................................................................................................................................8

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

1. СТРУКТУРЫ СИСТЕМ, ИХ СЛОЖНОСТЬ И СИММЕТРИЯ......................................10

1.1. Предмет исследования.......................................................................................................................10

1.2. Значимость понятия «структурная сложность»...............................................................................11

1.3. Основные определения, связанные с понятием системы................................................................12

1.4. История развития представлений о сложности систем...................................................................13

1.5. Модели структур систем....................................................................................................................15

1.5.1. Фрагменты и помеченные фрагменты графовых моделей.......................................................................17

1.5.2. Смысл вложения фрагмента в граф............................................................................................................18

1.6. Основные подходы к определению сложности систем...................................................................19

1.6.1. Сложность по Шеннону...............................................................................................................................19

1.6.2. Сложность по Колмогорову........................................................................................................................19

1.7. Структурная сложность......................................................................................................................21

1.7.1. Подход на основе вектор-индексов спектральной сложности.................................................................22

1.7.2. Теоретико-информационный подход к определению сложности через симметрию.............................24

1.7.3. Объединение различных подходов.............................................................................................................25

1.7.4. Топологические индексы.............................................................................................................................26

1.8. Структурные модели структурной сложности и система GMS.....................................................27

1.8.1. Исторический экскурс.................................................................................................................................27

1.8.2. g-модели (базовые модели системы GMS)................................................................................................27

1.8.3. Стратификация g-моделей...........................................................................................................................29

1.8.4. b-модели ....................................................................................................................................................31

1.8.5. Обозначения b-моделей...............................................................................................................................32

1.8.6. Пример построения b-модели.....................................................................................................................33

1.8.7. §(Ь)з-модели..................................................................................................................................................36

1.9. Различение графовых моделей..........................................................................................................37

1.9.1. Постановки задач.........................................................................................................................................38

1.10. Структурное сходство........................................................................................................................38

1.10.1.Подструктурный подход к определению структурного сходства...........................................................39

1.10.2.Сходство как близость мер структурной сложности................................................................................39

1.11. Визуализация структур.......................................................................................................................40

1.11.1. Понятие прорисовки графовой модели......................................................................................................40

1.11.2.Классификация методов прорисовки.........................................................................................................43

1.11.3. Изобразительные соглашения при прорисовке.........................................................................................44

1.11.4. Прорисовки на плоскости............................................................................................................................45

1.11.5. Прорисовка транзитивных графов..............................................................................................................47

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

2. СТРУКТУРНАЯ СЛОЖНОСТЬ ОРГРАФОВ.....................................................................49

2.1. Основные понятия, связанные со спецификой исследования фрагментов орграфов..................49

2.2. Спектральная сложность....................................................................................................................50

2.2.1. Индексы и вектор-индексы структурной спектральной сложности........................................................50

2.2.2. Базисы путей и контуров.............................................................................................................................50

2.2.3. Алгоритм вычисления индексов ССС в базисе путей...............................................................................53

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

ССС в различных базисах СД.....................................................................................................................56

2.2.5. Базис ориентированных цепных фрагментов............................................................................................64

2.2.6. Индексы и вектор-индексы структурной спектральной сложности в базисе ориентированных цепных фрагментов......................................................................................................................................68

2.3. è-модели орграфов в базисе ориентированных цепных фрагментов.............................................68

2.3.1. Алгоритмы построения b-моделей.............................................................................................................69

2.3.2. Используемое в реализации пространство параметризации....................................................................70

2.3.3. Пример ....................................................................................................................................................70

2.3.4. Зависимость вычислительной сложности от длины базиса.....................................................................72

2.3.5. Анализ сходства b-моделей.........................................................................................................................74

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

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

3. КЛАССИФИКАЦИЯ СЕМЕЙСТВ ТРАНЗИТИВНЫХ ГРАФОВ..................................76

3.1. Значимость транзитивных графов.....................................................................................................76

3.2. Постановка задачи..............................................................................................................................77

3.3. История развития исследования ТГС4.............................................................................................77

3.4. Необходимые определения................................................................................................................79

3.5. Подход к классификации ТГС4.........................................................................................................80

3.5.1. Описание порождаемых семейств..............................................................................................................81

3.5.2. Система классификации семейств ТГС4....................................................................................................82

3.6. Корректность и полнота классификации..........................................................................................86

3.7. Лес семейств ТГС4.............................................................................................................................86

3.8. Исследование характеристик симметрии семейств ТГС4..............................................................87

3.9. Исследование сложности семейств ТГС4.........................................................................................88

3.10. Классификация ПТГ с учетов характеристик симметрии...............................................................90

3.10.1. Анализ выделенных семейств.....................................................................................................................92

3.11. Сложность планарных транзитивных графов..................................................................................93

3.11.1. Постановка задачи........................................................................................................................................93

3.11 ^.Классификация планарных транзитивных графов по сходству расположения орбит цепей................93

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

4. ПРОГРАММНЫЕ РАЗРАБОТКИ.........................................................................................95

4.1. Общие сведения о программных разработках.................................................................................95

4.2. Автоматизированная система научных исследований «.Graph Model Workshop»........................96

4.3. Программный комплекс «Сложность орграфов в цепных базисах»..............................................98

4.3.1. Функциональность, объемные характеристики и архитектура................................................................98

4.3.2. Тестирование комплекса.............................................................................................................................99

4.3.3. Проектные решения и вычислительная сложность...................................................................................99

4.3.4. Интерфейс с пользователем......................................................................................................................103

4.3.5. Пример сценария использования..............................................................................................................104

4.3.6. Внедрение ..................................................................................................................................................105

4.4. Программный комплекс «TransGen»..............................................................................................106

4.4.1. Функциональность, объемные характеристики и архитектура..............................................................106

4.4.2. Проектные решения и вычислительная сложность.................................................................................108

4.4.3. Расширяемость системы шаблонов..........................................................................................................110

4.4.4. Интерфейс с пользователем и проведение вычислительных экспериментов.......................................112

4.4.5. Внедрение ..................................................................................................................................................115

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

ЗАКЛЮЧЕНИЕ.................................................................................................................................118

СПИСОК ЛИТЕРАТУРЫ...............................................................................................................122

ПРИЛОЖЕНИЕ 1. СПИСОК СОКРАЩЕНИЙ.......................................................................128

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

4.6. Индексы сложности орграфов.........................................................................................................129

4.7. Индексы сложности бесконтурных орграфов................................................................................131

4.8. Индексы сложности планарных орграфов......................................................................................133

4.9. Индексы сложности планарных бесконтурных орграфов............................................................135

4.10. Модели сложности для классов орграфов в базисе путей различной длины..............................137

4.10.1.Модели сложности для классов орграфов в базисе путей длины 0..2...................................................137

4.10.2. Модели сложности для классов орграфов в базисе путей длины 0..3...................................................139

4.10.3.Модели сложности для классов орграфов в базисе путей длины 0..4...................................................141

4.11. Модели сложности для классов орграфов в базисе ОЦФ различной длины..............................143

4.11.1.Модели сложности для классов орграфов в базисе ОЦФ длины 0..2....................................................143

4.11.2.Модели сложности для классов орграфов в базисе ОЦФ длины 0..3....................................................145

ПРИЛОЖЕНИЕ 3. СЕМЕЙСТВА ТРАНЗИТИВНЫХ ГРАФОВ, ПОРОЖДАЕМЫЕ

ГЕНЕРАТОРОМ TRANSGEN................................................................................................148

4.12. Каталог бесконечных семейств ТГС4.............................................................................................148

4.13. Каталог конечных семейств ТГС4..................................................................................................343

4.14. Дерево семейств ТГС4......................................................................................................................431

4.15. Интегральные характеристики семейств........................................................................................433

ВВЕДЕНИЕ

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

Объект и предмет работы

Объектом работы являются графовые модели систем. Предметом - их характеристики структурной сложности и симметрии.

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

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

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

т.п.), обладающей заданными свойствами: структурной сложностью, надёжностью, симметрией и др.

Объектом работы являются ГМС в виде транзитивных графов степени 4 и ориентированных графов. Предметом - их характеристики структурной сложности (индексы, вектор-индексы, 6-модели) и симметрии (от порядка группы автоморфизмов до структуры стационарных подгрупп). Работа продолжает исследования в области прикладной теории графов, проводимые В.А. Коховым, A.A. Незнановым. В ней рассматриваются вопросы создания программных средств, использующих взаимосвязь структурной сложности, сходства и симметрии для графовых моделей различных классов.

Цель работы

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

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

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

1. Дальнейшие углублённое изучение как классических моделей структурной сложности ГМС, так и оригинального представительного класса моделей, разработанного В.А. Коховым и реализованного в виде программных средств для класса обыкновенных графов C.B. Ткаченко и A.A. Незнановым.

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

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

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

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

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

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