Дипломы, курсовые, рефераты, контрольные...
Срочная помощь в учёбе

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

Диссертация: Методы и программные средства для различения расположения фрагментов графовых моделей систем
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Проблема выявления и практического использования взаимосвязи физико-химических свойств систем и процессов, с одной стороны, и их структур, с другой стороны, носит название проблемы структур. Исследование проблемы структур представляет собой одно из непрерывно актуальных направлений развития науки и техники. Объясняется это тем, что проблема структур, наряду с базовыми физическими законами, лежит… Читать ещё >

Содержание

  • Актуальность темы работы
  • Цель работы
  • Решаемые задачи
  • Научная новизна
  • Практическая полезность
  • Методы исследований и достоверность результатов
  • Реализация результатов
  • Апробация работы
  • Личный вклад диссертанта
  • Публикации
  • Содержание работы по главам
  • 1. РАЗЛИЧЕНИЕ РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ КАК НОВЫЙ УРОВЕНЬ ЗАДАЧ РАЗЛИЧЕНИЯ ГРАФОВ
    • 1. 1. Эквивалентность и толерантность графов и расположения их фрагментов
    • 1. 2. Графы, фрагменты и помеченные фрагменты
    • 1. 3. Группы автоморфизмов, индуцированные вершинной группой автоморфизмов {Ani{G))
      • 1. 3. 1. Пример t-группы
    • 1. 4. Задачи различения расположения фрагментов в графе
      • 1. 4. 1. Задачи различения расположения однотипных фрагментов
      • 1. 4. 2. Задачи различения расположения произвольных фрагментов
      • 1. 4. 3. Обсуждение постановок задач различения расположения фрагментов
      • 1. 4. 4. Сведение задач различения графов к задачам различения расположения фрагментов
      • 1. 4. 5. Сводная таблица основных задач различения
      • 1. 4. 6. Инвариантное ядро задач различения № 1 (ИЯЗР1) в СС-анализе
      • 1. 4. 7. Инвариантное ядро задач различения № 2 (ИЯЗР2) в СС-анализе
      • 1. 4. 8. ?, — и т-эквивалентность
      • 1. 4. 9. Задачи различения т-эквивалентности расположения фрагментов
    • 1. 5. Подходы к решению задач из ИЯЗР1 и ИЯЗР
      • 1. 5. 1. Систематизация подходов к решению задач из ИЯЗР
      • 1. 5. 2. Сложность и методы решения задач из ЙЯЗР
      • 1. 5. 3. Систематизация подходов к решению задач из ЙЯЗР
  • Выводы и результаты по главе
  • 2. ПЕРЕБОРНО-ГРУППОВОЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧ РАЗЛИЧЕНИЯ РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ
    • 2. 1. Базовые задачи
      • 2. 1. 1. Представление фрагментов в памяти компьютера
      • 2. 1. 2. Построение порождающего множества группы автоморфизмов графа
      • 2. 1. 3. Вид порождающего множества, используемый в данной работе
      • 2. 1. 4. Представление порождающего множества, описанного выше
      • 2. 1. 5. Канонизация представления помеченного фрагмента на основе порождающего множества группы автоморфизмов фрагмента
      • 2. 1. 6. Построение порождающего множества фиксатора/стабилизатора подмножества вершин графа
    • 2. 2. Построение и исследование ^-групп
      • 2. 2. 1. Представление порождающего множества t-группы
      • 2. 2. 2. Поиск помеченного фрагмента в базе фрагментов
      • 2. 2. 3. Построение порождающего множества t-группы
      • 2. 2. 4. Поиск орбит t-группы без построения порождающего множества t-группы
    • 2. 3. Решение задач из класса задач различения расположения фрагментов
      • 2. 3. 1. Решение задач различения расположения однотипных фрагментов
      • 2. 3. 2. Решение задач различения расположения произвольных фрагментов
      • 2. 3. 3. Построение и анализ матрицы пересечения орбит помеченных фрагментов
      • 2. 3. 4. Пример характеризации расположения фрагментов в графе
    • 2. 4. Экспериментальная оценка вычислительной сложности алгоритмов
    • 2. 5. Перспективы дальнейшего развития методов переборно-группового подхода
  • Выводы и результаты по главе
  • 3. СТРУКТУРНО-ХАРАКТЕРИСТИЧЕСКИЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧ РАЗЛИЧЕНИЯ РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ
    • 3. 1. Использование структурных инвариантов
    • 3. 2. g-модели и й-модели графа для визуализации и решения задач различения расположения фрагментов графа
    • 3. 3. Построение и исследование g-моделей и й-моделей
      • 3. 3. 1. Способы задания базисов структурных дескрипторов
      • 3. 3. 2. Определение рёбер и их весов
      • 3. 3. 3. Решение задач из класса задач различения расположения фрагментов на основе g-моделей
      • 3. 3. 4. Решение задач из класса задач различения расположения фрагментов на основе b-моделей
      • 3. 3. 5. Построение отношений эквивалентности и сходства графов на основе g- и b-моделей
    • 3. 4. Построение и исследование графов расположения цепей
      • 3. 4. 1. g-модели с равными долями
      • 3. 4. 2. Определение графа расположения цепей (ГРЦ)
      • 3. 4. 3. Эффективный метод построения ГРЦ
      • 3. 4. 4. Обозначения ГРЦ
      • 3. 4. 5. Алгоритм построения ГРЦ
      • 3. 4. 6. Доказательство корректности алгоритма
      • 3. 4. 7. Некоторые свойства ГРЦ
      • 3. 4. 8. Пример построения ГРЦ
      • 3. 4. 9. Исследование симметрии цепей исходного графа с использованием ГРЦ
      • 3. 4. 10. Обобщение ГРЦ для анализа фрагментов других типов
      • 3. 4. 11. Результаты экспериментов
    • 3. 5. Усиление чувствительности структурных инвариантов
      • 3. 5. 1. Итерационные методы усиления чувствительности
      • 3. 5. 2. Итерационное уточнение разбиения множества вершин на классы эквивалентности по g-модели
      • 3. 5. 3. Параметризация процедуры построения матрицы структурных инвариантов и проведение экспериментов по исследованию чувствительности инвариантов итерационного типа
    • 3. 6. Перспективы развития методов структурно-характеристического подхода
  • Выводы и результаты по главе
  • 4. ПОДСИСТЕМЫ АСНИ «GRAPHMODEL WORKSHOP» ДЛЯ ИССЛЕДОВАНИЯ АЛГОРИТМОВ СТРУКТУРНОГО СПЕКТРАЛЬНОГО АНАЛИЗА СИСТЕМ
    • 4. 1. История создания
    • 4. 2. Общая архитектура АСНИ и место авторских подсистем в ней
    • 4. 3. Программная реализация подсистем
    • 4. 4. Основные расширения АСНИ, реализованные автором
    • 4. 5. Учёт симметрии расположения фрагментов для повышения эффективности решения задач структурного спектрального анализа
      • 4. 5. 1. Развитие методологии монотонного расширения частичных решений
      • 4. 5. 2. Поиск всех канонических изоморфных вложений
      • 4. 5. 3. Максимальное изоморфное пересечение с учётом симметрии
      • 4. 5. 4. Декомпозиция графа на неизоморфные фрагменты
      • 4. 5. 5. Интерактивный поиск гамильтоновых цепей и циклов
    • 4. 6. Система проведения экспериментов и «полигон» исследования эффективности алгоритмов
      • 4. 6. 1. Схема эксперимента
      • 4. 6. 2. Сохранение результатов
      • 4. 6. 3. Анализ результатов
      • 4. 6. 4. Пример многоэтапного вычислительного эксперимента
      • 4. 6. 5. Вычислительные эксперименты, которые могут проводиться с использованием программных разработок автора
    • 4. 7. Исследование эффективности подходов к решению задач различения расположения фрагментов
      • 4. 7. 1. Используемые методики и тестовые данные
      • 4. 7. 2. Результаты вычислительных экспериментов
      • 4. 7. 3. Границы применимости

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

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

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

работы.

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

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

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

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

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

Цель работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации.

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

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

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

Выводы.

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

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Показать весь текст

Список литературы

  1. A. Lubiw, Some NP-complete problems similar to graph isomorphism, SIAM J. Computing, Vol. 10,(1981), -pp. 11−24.
  2. Babai L. Isomorphism testing and symmetry of graphs. II Annals of Discrete Math, 1980, Vol.8, —pp. 101−109.
  3. Bunke, Jiang, X. Graph matching and similarity, in Teodorescu, H.-N., Mly-nek, D., Kandel, A., Zimmermann, H.-J. (eds.): Intelligent Systems and Interfaces, Kluwer Academic Publishers, 2000. 33 p.
  4. CHEN Ling, YINXinchun, Parallel Algorithm for Testing Isomorphism of Undirected Graphs, Computer Engineering, vol. 28, no. 6, 2002.
  5. Chris D. Godsil, Gordon F. Royle. Algebraic Graph Theory. — Springer, 1 edition, 2001. 464 p.
  6. D.G. Cornell, C.C. Gotlieb, An efficient algorithm for graph isomorphism, Journal of the Association for Computing Machinery, 17, pp. 51−64, 1970.
  7. D.H. Smith, Distance-transitive graphs of valency four, J. London Math. Soc. (2) 8, (1974). -pp. 377−384.
  8. Douglas C. Schmidt, Larry E. Druffel. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices. II Journal of the ACM, 23(3), 1976.-pp. 433−445.
  9. E. Hemaspaandra, L. A. Hemaspaandra, S. P. Radziszowski, R. Tripathi. Complexity Results in Graph Reconstruction, Technical Report URCS-TR-2004−852, October 10, 2004.-27 p.
  10. E. M. Luks. Permutation groups and polynomial time computations. I I DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 11, 1993. —pp. 139−175.
  11. E. Spence. Strongly Regular Graphs on at most 64 vertices. — http://www.maths.gla.ac.Lik/~es/srgraphs.html.
  12. Gordon F. Royle. Combinatorial Catalogues. — http:// www. esse, uwa. edu. au/~gordon/data.html.
  13. J. Manning. Geometric symmetry in graphs. Ph. D. thesis, Purdue University, New York, 1990.
  14. J. R. Ullmann. An Algorithm for Subgraph Isomorphism. II Journal of the Association for Computing Machinery, vol. 23, 1976, pp. 31−42.
  15. J. Tordn. On the hardness of Graph Isomorphism. II SIAM Journal of Computing, 33(5), 2Ш.-рр. 1093−1108.
  16. K.V.S. Bhat, Refined vertex codes and vertex partitioning methodology for graph isomorphism testing, IEEE Transactions on System, Man & Cybernetics, Vol. SMC-10, 1980, др. 610−615.
  17. L. Babai, D. Grigoryev, D. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. II Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982,-pp. 310−324.
  18. L. P. Cordelia, P. Foggia, C. Sansone, M. Vento, An Improved Algorithm for Matching Large Graphs, Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representation, Italy, 2001.
  19. L. P. Cordelia, P. Foggia, C. Sansone, M. Vento, Subgraph Transformations for the Inexact Matching of Attributed Relational Graphs, Computing, suppl. 12, pp. 43−52, 1998.
  20. L.P. Cordelia, P. Foggia, C. Sansone, M. Vento, Performance evaluation of the VF Graph Matching Algoritmh, Proc. of the 10th ICIAP, IEEE Computer Society Press, pp. 1172−1177, 1999.
  21. Larry E. Druffel, Douglas C. Schimdt, Da Lun Wang. A generator set for representing all automorphisms of graph. IISIAMJ. App. Math., Vol. 34, No. 3, 1978. -pp. 593−596.
  22. LI Feng, LI Xiaoyan, Isomorphism Testing Algorithm for Graphs: Incidence Degree Sequence Method and Applications, Journal of Fundan University {Natural Science), vol. 40, 2001. -pp. 318−325.
  23. Liu Xiaoyu, Balasubramanian K., Munk M.E. Computational Techniques for Vertex Partitioning of Graphs. // J. Chem. Inf. Comput. Sci. 1990, 30. pp. 263−269.
  24. McKay B. D. nauty User’s Guide (Version 2.2), 2004. 33 p.
  25. McKay B. D., Praeger С. E. Vertex-Transitive Graphs Which Are Not Cayley Graphs. I II J. Austral. Math. Soc. Ser. A 56, 1994. -pp. 53−63.
  26. McKay B.D. Practical graph isomorphism. II Congressus Numerantium 30, 1981. -pp. 45−87.
  27. McKay, Brendan D.- Royle, Gordon F. The transitive graphs with at most 26 vertices. II Ars Combin. 30 (1990). -pp. 161−176.
  28. Messmer B.T., Bunke H., A decision tree approach to graph and subgraph isomorphism detection, Pattern Recognition, vol. 32, 1999. -pp. 1979−1998.
  29. Messmer B.T., Bunke H., Subgraph isomorphism in polynomial time. II Technical Report TR-IAM-95−003, 1995. 33 p.
  30. MSDN (.Microsoft Developer Network) Library и MSDN online — http://msdn.microsoft.com.
  31. P. Dickinson, H. Bunke, A. Dadej and M. Kraetzl. On Graphs with unique node labels. E. Hancock, M. Vento (eds.): Graph Based Representations in Pattern Recognition in Proc. 4th Int. Workshop GBR2003, Springer, LNCS2126, pp. 13−23.
  32. P. Foggia, C. Sansone, M. Vento. A Performance Comparison of Five Algorithms for Graph Isomorphism. II International Workshop on Graph-based Representation in Pattern Recognition, Ischia, Italy, pp. 188−199, 23−25 May, 2001.
  33. Raymond J.W., Willett P. Maximum common subgraph isomorphism algorithms for the matching of chemical structures. II Journal of Computer-Aided Molecular Design, 16, 2002. -pp. 521−533.
  34. Robert F. Bailey. Distance-Transitive Graphs, Department of Pure Mathematics, University of Leeds (2002). 125 p.
  35. Ronald С. Read, Robin J. Wilson. An Atlas of Graphs. — Oxford University Press, 1998.-464 p.
  36. Royle, Gordon F.- Praeger, Cheryl E. Constructing the vertex-transitive graphs of order 24. II J. Symbolic Comput. 8 (1989), no. 4. -pp. 309−326.
  37. To His I., Di Battista G., Eades P., Tamassia R. Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall- Is/ edition (1998). 397 p.
  38. V. Arvind, P. Kurur. Graph isomorphism is in SPP. II Electronic Colloquium on Computational Complexity (.ECCQ TR02−037, 2002. 12 p.
  39. Willett P., Willett J. Similarity and Clustering in Chemical Information Systems.1. John Wiley & Sons, 1987.
  40. Алгоритмические исследования в комбинаторике. Под ред. Фараджева И.А.1. М.: Наука, 1978.- 188 с.
  41. Арлазаров BJL, Зуев И. И., Усков А. В., Фараджев И. А. Алгоритм приведения конечных неориентированных графов к каноническому виду. // Журнал вычислит, мат. и мат. физ., 1974, Т. 14, № 3. С. 737−743.
  42. Г. Т., Тюрин В. Д. Топология сетей ЭВМ и многопроцессорных систем. — М.: Радио и связь, 1991. 248 с.
  43. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы.: Пер. с англ.: Уч. пос. — М.: «Вильяме», 2000. 384 с.
  44. К. Теория графов и её применения. — М.: Изд-во иностр. лит., 1967. -320 с.
  45. С. Математическая модель молекулярной сложности. // Химические приложения топологии и теории графов. — М.: Мир, 1987.
  46. К. В. Локальные базисы в алгебраическом подходе к проблеме распознавания. — Диссертация на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН, 1999.- 122 с.
  47. М., Джонсон Д. Вычислительные машины и труднорещаемые задачи.1. М.:Мир, 1982.-416 с.
  48. B.C., Перетурин А. Ф. Симметрия и асимметрия как категории познания. // Симметрия, инвариантность, структура. Философские очерки. М.: Высшая школа, 1967. — С. 3−70.
  49. А.Б. Разработка методов структурного различения графовых моделей дискретных систем. Дисс. на соискание уч. степени канд.техн. наук. М. МЭИ. 1987.- 163 с.
  50. А.Б., Кохов В. А. Метод сокращения перебора на основе учета симметрии при решении iVP-полных задач на графах // Моск. Энерг. ин-т. -М, 1987. 58 с. деп. ВИНИТИ, 18.08.87, № 6029-В87.
  51. А.Б., Кохов В. А. Эффективные алгоритмы изоморфного вложения и пересечения графов. // Тезисы докл. межвузовской конференции «Молекулярные графы в химических исследованиях». Калинин, 1990. С. 15−16.
  52. А.А., Скоробогатов В. А. Метрические инварианты подграфов молекулярных графов. // Математические методы в структурной информатике. — Новосибирск, 1991. С. 3−62.
  53. С. А., Пономаренко И. Н. Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время. // Алгебра и анализ, Т. 15, вып. 6, 2003.-С. 1−34.
  54. В.А. Применение теории графов в программировании. — М.: Наука, 1985.
  55. Ю. И. Об алгебраических методах в задачах распознавания и классификации. // Распознавание, классификация, прогноз, Т. 1, 1988. -С. 9−16.
  56. Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации. // Проблемы кибернетики, Т. 33, 1978. С. 5−68.
  57. B.C. Справочник программиста. Базовые методы решения графовых задач и сортировки. — М.: ФИЛИНЪ, 1999. 256 с.
  58. А.А. Основы теории графов. ¦— М: Вузовская кн., 2004. 664 с.
  59. Исследования по алгебраической теории комбинаторных объектов. Под ред. Фараджева И. А. —М.: ВНИИСИ, 1985.- 187 с.
  60. Исследования по общей теории систем. Сборник переводов. Общая редакция и вступит, статья Садовского В. Н. и Юдина Э. Г. М.: «Прогресс», 1969.
  61. В.Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. 1104 с.
  62. Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.
  63. М.: Издательский дом «Вильяме», 2000. 720 с.
  64. Д. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд. — М.: «Вильяме», 2000. 832 с.
  65. Д. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.
  66. М.: «Вильяме», 2000. 832 с.
  67. А.Н. Три подхода к определению понятия «количество информации». — Проблемы передачи информации. 1965. Вып. 1. Т.1. С. 1−7.
  68. Е.В., Скоробогатов В. А. Структурные и численные инварианты обыкновенных и молекулярных графов. // Математические методы в структурной информатике. —Новосибирск, 1991. С. 87−129.
  69. В.А. Граф-модели в структурном спектральном анализе систем. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2004), Т.1, Москва, 2004. С. 211−214.
  70. В.А. Диаграммы, числа стабильности и цикловые индексы групп автоморфизмов транзитивных графов. // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд., 1986. С. 97−125.
  71. В.А. Исследование на ЭВМ симметрии транзитивных сильно регулярных графов. // Системное моделирование-10. — Новосибирск: ВЦ СО АН СССР, 1984.-С. 35−44.
  72. В.А. Концептуальные и математические модели сложности графов. // М. Издательство МЭИ, 2002. 160 с.
  73. В.А. Некоторые инварианты конечных графов и их применение. Ав-тореф. диссертации на соискание уч. степени канд. техн. наук. М.:МЭИ. 1976.-20с.
  74. В.А. Основы структурной информатики. // Доклады международной конференции «Информационные средства и технологии». (МФИ-98), Т.З. — Москва, 1998.
  75. В.А. Основы химической структурной информатики. // Тезисы докладов международной конференции «Информационные средства и технологии» международного форума информатизации (МФИ-97), ТЗ, Москва, 1997. -С. 37- 42.
  76. В.А. Решение задач анализа графов и их групп автоморфизмов с помощью ППП «GMW-2.0» — М.: Издательство МЭИ, 2002. 64 с.
  77. В.А. Структурная информатика: методы различения расположения фрагментов графа. // Доклады международной конференции «Информационные средства и технологии» (МФИ-2002), Т2, Москва, МЭИ, 2002. С. 51−54.
  78. В.А. Число тождественности графа. // Моделирование в информатике и вычислительной технике (Системное моделирование-13). — Новосибирск: ВЦ СО АН СССР, 1988. С. 49−63.
  79. В.А., Грызунов А. Б., Картовицкий A.JI. ППП структурного анализа и синтеза молекулярных графов. // Тезисы докладов межвузовской конференции «Молекулярные графы в химических исследованиях». Калинин, 1990. -С. 43−44.
  80. В.А., Незнанов А. А., Горшков С. А. ППП «СТРИН+»: Подсистема сравнительного анализа структур. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2004), Т.1, Москва, 2004. -С. 215−218.
  81. В.А., Незнанов А. А., Ткаченко С. В. Новые программные средства для поиска структурной информации. // Труды международной научно-технической конференции «Информационные средства и технологии». (МФИ-2005), Т.2, Москва, 2005. С. 83−86.
  82. В.А., Незнанов А. А., Ткаченко С. В. «СТРИН». // ПСУН по разделу «Структурная информатика» дисциплины «Информатика» / Паспорт от 16.03.2005 г. М., МЭИ, 2005.
  83. В.А., Незнанов А. А., Ткаченко С. В. «Полигон алгоритмов структурной информатики». // ПСУН по разделу «Структурная информатика» дисциплины «Информатика» / Паспорт от 16.03.2005 г. М., МЭИ, 2005.
  84. В.А., Ткаченко С. В. Редактор структур, автоматическая прорисовка диаграмм и методы анализа сложности и сходства графов: Лабораторный практикум. — М.: Издательство МЭИ, 2001. 120 с.
  85. В.А., Ткаченко С. В., Незнанов А. А. Построение алгоритмов и программ быстрой обработки физико-химической информации. — Отчёт по НИР, выполненной на кафедре ПМ. Зарегистрированная тема НИР МЭИ № 1 147 970, 2001.- 124 с.
  86. В.А., Ткаченко С. В., Незнанов А. А. Решение базовых задач структурной информатики с помощью ППП «ПОЛИГОН-СТРИН»: лабораторный практикум. — М.: Издательство МЭИ, 2005. 120 с.
  87. Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. -432 с.
  88. Ю.М. Изоморфизм графов с ограниченными степенями вершин может быть установлен за полиномиальное время — Киберн. сб. М., 1985. N 22. С. 72−101.
  89. В. Комбинаторика для программистов. — М.: Мир, 1988. 213 с.
  90. Э. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981. -323 с.
  91. А.А. Разработка и исследование методов анализа расположения и взаимного расположения фрагментов в топологии графовых моделей систем. — Магистерская диссертация, МЭИ, 2002. 106 с.
  92. А.А., Кохов В. А. Алгебраический подход к анализу симметрии расположения фрагментов графа. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2003), Т.1, Москва, 2003. -С. 216−219.
  93. А.А., Кохов В. А. Справочник по теории графов. Характеристики симметрии и сложности связных транзитивных графов степени 4 с числом вершин до 30 включительно. — М. Деп. в ВИНИТИ, № 1094-В2004, 2004. -418 с.
  94. А.А., Кохов В. А. Структурная информатика: симметрия структур. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2001), Т. З, — Москва, 2001. С. 38−42.
  95. М.И., Попков В. К., Кохов В. А. и др. Алгоритмы и программы решения задач на графах и сетях. — Новосибирск: Наука, 1990. 515 с.
  96. И.В. Системный подход и общесистемные закономерности. Серия «Системы и проблемы управления». — М.: СИНТЕГ, 2000. 528 с.
  97. А.В. Алгоритм поиска приближенного решения задачи проверки изоморфизма подграфов. // Математические структуры и моделирование: Сб. научн. тр. Под ред. А. К. Гуца. Омск: Омск. гос. университет, 2003. Вып. 10.-С. 59−66.
  98. Ш. Рихтер Дж. Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows, 4-е изд. — СПб: Питер- М.: «Русская редакция», 2001. 752 с.
  99. М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.
  100. Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах: Пер. с англ. — СПб: ООО «ДиаСофтЮП», 2002. 496 с.
  101. М. И. Общие принципы организации систем и их методологическое значение. М. 1975. — 132 с.
  102. В.А. О распознавании изоморфизма неориентированных графов. // Вычислительные системы. Новосибирск, 1969. Вып. 33 — С. 3−10.
  103. В.А., Хворостов П. В. Анализ метрических свойств графов. // Методы обнаружения закономерностей с помощью ЭВМ. Новосибирск, 1981. -С. 3−20.
  104. В.А., Хворостов П. В. Методы и алгоритмы анализа симмет-рий графов. // Алгоритмы анализа структурной информации, выпуск 103. Новосибирск, 1984.-С. 6−25.
  105. С.В., Незнанов А. А., Кохов В. А. Компьютерная поддержка курса «Основы Структурной информатики». // Доклады международной конференции «Информационные средства и технологии» (МФИ-2002), Т.2, Москва, 2002.-С. 55−58.
  106. Узоры симметрии. Под ред. М. Сенешаль и Дж. Флека. — М.: Мир, 1980. -269 с.
  107. Ф. Теория графов. — М:. Едиториал УРСС, 2003. 296 с.
  108. Ф., Палмер Э. Перечисление графов. Пер. с англ. — М.: Мир, 1977, -324 с.
  109. К. Работы по теории информации и кибернетике. —М.: Изд. ин. лит., 1963.
  110. Ю.А. Равенство, сходство, порядок. —М.: Наука, 1971. 256 с.
Заполнить форму текущей работой

Заказал и сдал!