Исследование методов и разработка программных средств анализа структурной сложности и симметрии графовых моделей систем тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Старичкова, Юлия Викторовна

• Старичкова, Юлия Викторовна
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Старичкова, Юлия Викторовна

ВВЕДЕНИЕ.

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

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

Цель работы

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

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

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

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

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

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

Публикации

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

главам.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.8.4. b-модели

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

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

1.8.7.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.3. Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3.6. Внедрение

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

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

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

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

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

4.4.5. Внедрение

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

Введение диссертации (часть автореферата) на тему «Исследование методов и разработка программных средств анализа структурной сложности и симметрии графовых моделей систем»

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тверь, 2010 г.), на семинаре «Комбинаторика инвариантов Васильева» (г. Москва, 2012), семинарах ИППИ РАН и НИУ ВШЭ (г. Москва, 2012).

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

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

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

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

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

Публикации

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Старичкова, Юлия Викторовна

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

4.1. Вычислены и проанализированы индексы структурной спектральной сложности орграфов планарных, бесконтурных и общего вида в базисе путей, полупутей, контуров, полуконтуров и ОЦФ ограниченной длины (более 30 базисов, более 200 экспериментов, более года машинного времени), что позволило, например, установить различия в дискриминирующей способности базисов для данных классов ГМС.

4.2. Построены ¿-модели орграфов планарных, бесконтурных и общего вида в базисе путей, полупутей, контуров, полуконтуров и ОЦФ ограниченной длины и провести анализ результатов различения и анализа сходства орграфов по обобщённому подструктурному подходу.

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

4.4. Исследован отдельный класс планарных транзитивных графов, для которого исследованы характеристики симметрии и сложности и построены бесконечные семейства. Из всех связных ТГ до 30 вершины включительно (всего 98117 графов) - 66 планарных. Целью классификации связных ПТГ является разбиение графов на семейства с учетом некоторых параметров, главными из которых будут характеристики симметрии. Данная классификация разбила весь класс ПТГ. Результатом классификации является 4 семейства ТПГС4 и др.

4.5. Построены £5о-модели и проведена классификация ПТГ (66) на основе сходства расположения орбит цепей длины Р0 - Рп, Были отдельно исследованы подклассы (3) классов (52) полученные в результате анализа сходства расположения орбит фрагментов, с использованием цепей длины более Ро - Р9. Такой подход был применен в связи с тем, что анализ сходства расположения орбит фрагментов, с использованием цепей длины больше, чем Р0 - Р9 для всех планарных транзитивных графов с количеством вершин до 30 представляет сложность, так на построение такой модели затрачивается более 24 часов.

4.6. В результате сравнения результатов классификаций ПТГ по характеристикам симметрии и по сходству расположения орбит фрагментов, с использованием цепей длины Р0 - Рп, классификация по сходству расположения орбит фрагментов оказалась точнее (52 класса), чем классификация по характеристикам симметрии (15 классов), то есть классификация по сходству расположения орбит фрагментов вкладываются в классы по характеристикам симметрии.

5. Разработан программный комплекс (ПК) для генерации семейств ТГС4 (59 бесконечных и 72 конечных, из которых 4 являются планарными), в котором реализованы оригинальные алгоритмы генерации, возможность выбора прорисовок диаграмм, поиск семейств по характеристикам симметрии и другие возможности. Проведены объёмные вычислительные эксперименты с использованием ОМ\¥ и авторских программных разработок с целью исследования характеристик симметрии и сложности ТГС4, что позволило подтвердить корректность классификации и построить симметричные диаграммы представителей семейств ТГС4 (более 120 экспериментов, более 1,5 лет машинного времени) и дополнительно классифицировать семейства. Данный ПК является расширяемым и может служить базой для создания других программ синтеза графовых моделей систем.

6. Разработаны ПК для анализа структурной сложности орграфов.

6.1. ПК «Индексы сложности орграфов» позволяет вычислять индексы спектральной структурной сложности орграфов с базисах путей, полупутей, контуров, полуконтуров и ОЦФ с возможность наращивания фрагментов базиса.

6.2. ПК «¿-модели орграфов» позволяет строить b-модели для орграфов в базисах путей, полупутей, контуров, полуконтуров и произвольных ОЦФ. Построенные модели могут сохраняться либо в виде графов, либо в виде специальных структур в базе данных результатов АСНИ.

7. Программные разработки содержат более 400 КБ авторского исходного кода и более 6 МБ исполняемого кода. Большинство программных разработок способны интегрироваться в АСНИ «Graph Model Workshop» (GMW). На базе программных разработок созданы программные средства учебного назначения (2 ПСУН) для поддержки дисциплин «Теория графов и комбинаторика», «Практикум на ЭВМ», «Теория вычислительной сложности», «Дискретная математика».

Список литературы диссертационного исследования кандидат технических наук Старичкова, Юлия Викторовна, 2013 год

1. Месарович М., Такахара Я. Общая теория систем: математические основы. М.: Мир, 1978. 311 с.

2. Bertalanffy L. General System Theory: Foundations, Development, Applications. New York: George Braziller, 1969. 296 pp.

3. Science and Engineering of Natural Systems Group. // Complexity Science Focus. URL: http://www.complexity.ecs.soton.ac.uk/ (дата обращения: 23.20.2011).

4. Сетров М.И. Общие принципы организации систем и их методологическое значение. Л.: Наука, 1971. 132 с.

5. Поваров Г.Н. Об уровнях сложности систем // Методологические проблемы кибернетики. 1970. Т. 2.

6. Бир С. Мозг фирмы. М.: УРСС, 2005.

7. Незнанов A.A. "Методы и программные средства для различения расположения фрагментов графовых моделей систем," М., Диссертация на соискание учёной степени к.т.н. 2005. 162 с.

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

9. Ю.Шеннон К. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963. 832 с.

10. П.Хартли P.B.J1. Передача информации // В кн.: Теория информации и её приложения. М.: Физматгиз, 1959.

11. Колмогоров А.Н. Теория информации и теория алгоритмов. М.: Наука, 1987. 304 с.

12. Мартин-Лёф П. Очерки по конструктивной математике. М.: Мир, 1975. 136 с.

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

14. Кохов В.А., Незнанов А.А. Методические указания у лабораторным работам по дисциплине "Теория графов и комбинаторика", тема: симметрия структур. М.: 2001. документ.

15. Кинг Р. Химические приложения топологии и теории графов. М.: Мир, 1987. 560 с.

16. U.S. Environmental Protection Agency. // Molecular Descriptors Guide. 2008. URL: http://www.epa.gov/nrmrl/std/qsar/MolecularDescriptorsGuide-vl02.pdf (дата обращения: 14.05.2011).

17. Virtual Computational Chemistry Laboratory. Topological descriptors // Virtual Computational Chemistry Laboratory. 2005. URL: http://www.vcclab.org/lab/ indexhlp/topodes.html (дата обращения: 12.09.2011).

18. Faulon J.L., Bender A. Handbook of Chemoinformatics Algorithms. Chapman and Hall/CRC, 2010. 454 pp.

19. Кохов B.A. Граф-модели для определения сходства структур систем с учетом сходства расположения фрагментов // "X Национальная конференция по искусственному интеллекту с международным участием". 2006. Т. 1. С. 208216.

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

21. Кохов В.А., Незнанов А.А., Ткаченко С.В. Задачи анализа структурного сходства и методы их решения // Двенадцатая национальная конференция по искусственному интеллекту с международным участием. КИИ-2010. Труды конференции. М. 2010. Т. 1. С. 161-169.

22. Willett P., Willett J. Similarity and Clustering in Chemical Information Systems. John Wiley & Sons, 1987. 266 pp.

23. DiBattista G., Eades P., Tamassia R. and Tollis I.G. Graph Drawing. Algorithms for the Visualization of Graphs. Prentice Hall, 1998. 397 pp.

24. Kaufmann M., Wagner D. Drawing Graphs: Methods and Models. Springer, 2001. 312 pp.

25. Kruja E., Marks J., Blair A. and Waters R. "A Short Note on the History of Graph Drawing," Lecture Notes in Computer Science, Vol. 2265, 2002.

26. Eiglsperger M., Fekete S.P. and Klau G.W. Orthogonal Graph Drawing. 2001.

27. Tollis. A.P. Ioannis G. Algorithms for Area-Efficient Orthogonal Drawings. 1995.

28. Read R.C. A new method for drawing a planar graph given the cyclic order of the edges at each vertex.

29. Hong S., Eades P. Symmetric Graph Drawing // In: Handbook of graph drawing and visualization. CRC Press, 2005.

30. KoxoB B.A., Ткачеко C.B. Решатель базовых задач структурной информатики. М.: Изд. дом МЭИ, 2008. 192 с.

31. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384 с.

32. Sabidussi G. Vertex-transitive graphs // Monatsh. Math. 1964. Vol. 68. pp. 426-438.

33. Yap H.P. Point symmetric graph with p less then 13 points // Nanta Math. 6. 1973. pp. 8-20.

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

35. Royle G.F., Praeger C.F. "Constructing the vertex-transitive graphs of order 24," Journal of Symbolic Computation, Vol. 8, No. 4, 1989. pp. 309-326.

36. McKay B.D., Royle G.F. The transitive graphs with at most 26 vertices // Ars Combinatoria. 1990. pp. 161-176.

37. Godsil C., Royle G. Algebraic Graph Theory. New York: Springer-Ver lag, 2001. 452 pp.

38. Dekker A.H., Colbert B.D. Network Robustness and Graph Topology // Proc. Twenty-Seventh Australasian Computer Science Conference (ACSC2004). Dunedin, New Zealand. 2004. pp. 359-368.

39. Dekker A.H., Colbert B.D. The Symmetry Ratio of a Network // The Australasian Theory Symposium (CATS2005). Newcastle, Australia. 2005.

40. Angskun T., Bosilca G. and Dongarra J. Binomial Graph: A Scalable and Fault-Tolerant Logical Network Topology // ISPA07, LNCS 4742, Springer. 2007. pp. 471-482.

41. Hahn G., Sabidussi G. Graph Symmetry: Algebraic Methods and Applications. Springer, 1997. 444 pp.

42. Харари Ф. Теория графов. M.: УРСС, 2003. 300 с.

43. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 326 с.

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

45. Read R.C., Wilson R.J. An Atlas of Graphs. Oxford University Press, 1998. 464 pp.

46. Conder M., Malnic A., Marusic D., and Potocnik P. "A census of semisymmetric cubic graphs on up to 768 vertices," Journal of Algebraic Combinatorics, Vol. 23, No. 3,2006. pp. 255-294.

47. Калягина O.B. Разработка алгоритмов и программ прорисовки трех классов графов. Магистерская диссертация. Москва: МЭИ, 2004.

48. Royle G. // Transitive graphs: сайт. [1997]. URL: mapleta.maths.uwa.edu.au/ -gordon/trans/

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

50. Embarcadero Technologies, Inc. // Embarcadero Delphi XE2. URL: http:// www.embarcadero.com/products/delphi (дата обращения: 24.10.2011).

51. Galitsky В., Kuznetsov S.O., and Usikov D. Parse Thicket Representation for Multi-Sentence Search // Lecture Notes in Artificial Intelligence (LNAI). 2013. Vol. 7735. pp. 154-173.

52. Poelmans J., Elzinga P., Neznanov A., Viaene S., Kuznetsov S.O., Ignatov D.I. and Dedene G. Concept Relation Discovery and Innovation Enabling Technology (CORDIET) // The Computing Research Repository (CoRR). 2012.

53. Luks E.M. "Isomorphism of graphs of bounded valence can be tested in polynomial time," Journal of Computer and System Sciences, Vol. 25, 1982. pp. 42-65.

54. McKay B.D. // The nauty page. URL: http://cs.anu.edu.au/~bdm (дата обращения: 14.10.2010).

55. Junttila Т., Kaski P. // bliss: A Tool for Computing Automorphism Groups and Canonical Labelings of Graphs. URL: http://www.tcs.hut.fi/Software/bliss (дата обращения: 14.10.2010).

56. Grange E. DWScript // DelphiTools.info. URL: http://delphitools.info/dwscript (дата обращения: 3.11.2011).

57. Babai L. Automorphism groups, isomorphism, reconstruction. Vol 1-2. // In: Handbook of combinatorics / Ed. by Graham R.L., Amsterdam: Elsevier, 1995. pp. 1447-1540.

58. Кохов B.A. "Исследование на ЭВМ симметрии транзитивных сильно регулярных графов". Системное моделирование, № 10, 1984. С. 35-44.

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

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

61. Старичкова Ю.В., Незнанов А.А. "Программный комплекс для генерации семейств транзитивных графов степени 4" Бизнес-информатика, Т. 3, 2011. С.36.44.

62. Тараканов В.Е. "Группы автоморфизмов циркулянтов и присоединённые матрицы графов". Математические заметки, Т. 65, № 3, 1999. С. 402-411.

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

64. Randic М. "Similarity Based on Extended Basis Descriptors," J.Chem.Inf. Comput. Sci, Vol. 32, 1992. pp. 686-692.

65. Lauri J., Scapellato R. Topics in Graph Automorphisms and Reconstruction. Cambridge: Cambridge University Press, 2003. 172 pp.

66. Акчурин P.M., Старичкова Ю.В., Шаграев А.Г. Множество операций преобразования структур // МНТК Информационные средства и технологии. МФИ-2009. М. 2009.

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

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

69. Пригожин И. От существующего к возникающему: Время и сложность в физических науках. М.: Наука, 1985. 328 с.

70. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. Москва: Вильяме, 2000. 400 с.

71. Богопольский В.О. Введение в теорию групп. Москва: Ижевск: Институт компьютерных исследований, 2002. 148 с.

72. Зубов B.C., Шевченко И.В. Структуры и методы обработки данных. Практикум в среде Delphi. М.: ФИЛИНЪ, 2004. 304 с.

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

74. Jackson М.О. Social and Economic Networks. Princeton University Press, 2010. 520 pp.