BC/NW 2007, №1, (10) :4.1

ПРОГраммный Комплекс ДЛЯ СТРУКТУРНОГО СПЕКТРАЛЬНОГО АНАЛИЗА АЦИКЛИЧЕСКИХ ГРАФОВ

А.Р. Ибрахим, М.Р. Джасим, В.А. Кохов

(Москва, Московский энергетический институт (технический университет), Россия)

В рамках внедрения новых информационных технологий в учебный процесс разработан программный комплекс, включающий 9 программных расширений для ППП «СТРИН», позволяющих решать задачи, входящие в инвариантное ядро задач структурного спектрального анализа и синтеза деревьев [1]:

1. Построение g-моделей и b-моделей, характеризующих деревья в расширяемых базисах структурных

дескрипторов (СД) с учетом расположения фрагментов заданного вида [2,3];

2. Анализ симметрии деревьев: (2.1) Построение порождающего множества и всей группы автоморфиз-

мов дерева (Aut(G)). Вычисление основных характеристик Aut(G); (2.2) Построение порождающего множества и всей t-группы автоморфизмов дерева (Aut ^t(G)). Вычисление характеристик Aut ^t(G);

3. Различение деревьев: (3.1) Изоморфизм деревьев; (3.2) Изоморфное вложение дерева в дерево; (3.3)

Определение всех изоморфных и канонических изоморфных вложений дерева в дерево;

4. Различение расположения фрагментов в топологии деревьев: (4.1) Различение расположения

фрагментов типа t с точностью до орбит Aut ^t(G); (4.2) Различение расположения фрагментов типа t с точностью до классов t-эквивалентности. Отношение t-эквивалентности задается базисом СД; (4.3) Различение расположения фрагментов с точностью до вложения орбит фрагмента типа t1 в орбиты фрагмента типа t2; (4.4) Различение расположения фрагментов с точностью до вложения классов t-эквивалентности расположения фрагмента типа t1 в классы t-эквивалентности расположения фрагмента типа t2, где t1Í t2;

5. Анализ сложности деревьев: (5.1) Вычисление индексов; (5.2) Вычисление вектор-индексов; (5.3)

Вычисление расширенной матрицы b-модели;

6. Анализ сходства деревьев: (6.1) По подструктурному подходу на основе максимального общего фраг-

мента; (6.2) По обобщенному подструктурному подходу на основе g-, b-, и b(g)-моделей;

7. Анализ сходства расположения фрагментов в дереве: (7.1) С точностью до орбит фрагментов заданного

типа; (7.2) С точностью до классов t-эквивалентного расположения фрагментов заданного типа;

8. Прорисовка диаграмм деревьев и их g-моделей с учетом симметрии;

9. Конструктивное перечисление деревьев и генерация семейств деревьев с заданными ограничениями.

Программный комплекс включает 7 DLL, общим объемом 5 Мб, созданных в средах Microsoft Visual С++ .NET, С++ Builder 6 и Delphi 7 и позволяет анализировать базы деревьев с числом вершин до 5000 на современных ПЭВМ.

ППП «СТРИН» входит в учебно-методический комплекс «Основы структурной информатики» и используется для обучения студентов первого и второго курсов всех направлений обучения в МЭИ [2]

Литература

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

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