BC/NW 2012; №1 (20): 8.1

 

СТРУКТУРНАЯ ИНФОРМАТИКА: ТРАНСГРАФЫ ПОЛУПУТЕЙ ДЛЯ ОРДЕРЕВЬЕВ И ИХ СВОЙСТВА

В.В. Кохов, В.Н.Фальк

 

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

В докладе предложена система эффективных методов для построения нового класса моделей – трансграфов полупутей. Методы предназначены для более точного анализа сложности и сходства ордеревьев.  Предложенные модели расширяют функциональные возможности ПСУН, используемого при обучении студентов АВТИ [1,2].

Применение трансграфов полупутей позволило создать два более точных подхода к анализу сходства ордеревьев на основе: (1) вычисления и учета вклада каждого полупути в общую сложность ордерева; (2) расширения возможностей поструктурно-метрического подхода, учитывающего не только расположение путей, но и полупутей в ордереве. Кроме того, построение трансграфов полупутей позволяет: (1) визуализировать каждый полупуть вершиной трансграфа полупутей ghp(dt) ордерева dt; (2) исследовать все группы автоморфного расположения полупутейhpвсех типов как одну группу автоморфизмов вершин ghp(dt); (3) для каждого ордерева dt на основе единой методики решать задачи построения семейств неизоморфных орграфов с изоморфными группами; (4) внедрять новые информационные технологии в обучение студентов университетов при изучении графовых моделей систем, их сходства и сложности [1].

На рис. 1 приведены три ордерева (dt₁=(V₁,E₁), dt₂=(V₂,E₂), dt₃=(V₃,E₃)) и их трансграфы полупутей (ghp(dt₁),ghp(dt₂),ghp(dt₃)).

Рис. 1. Примеры трансграфов полупутей для ордеревьев

Вершины, соответствующие путям ордерева длиной больше нуля обозначены квадратами, а полупутям – ромбами.В докладе выделены три основных свойства трансграфов полупутей для ордеревьев: (1) каждому полупути взаимнооднозначно соответствует вершина в трансграфе полупутей; (2) для любого ордерева группа автоморфизмов вершин ордерева изоморфна группе автоморфизмов вершин трансграфа полупутей; (3) группа, характеризующая расположение полупутей в ордереве, изоморфна группе автоморфизмов вершин в трансграфе полупутей. Заметим, что в общем случае пути ордерева являются частным случаем его полупутей.

Пусть gp(dt) обозначает трансграф путей ордерева dt, а MCS(dt_i,dt_j) - максимальный общий подграф ордеревьв dt_i и dt_j. В таблице приведены результаты определения попарных расстояний (D₁, D₂, D₃), полученные при анализе сходства трех анализируемых ордеревьев на основе структурно-метрического подхода, где

D₁(dt_i,dt_j)=÷V(dt_i)ç+÷V(dt_j)ç-2÷V(MCS(dt_i,dt_j))ç;

D₂(gp(dt_i,dt_j))=÷V(gp(dt_i))ç+÷V(gp(dt_j))ç-2÷V(MCS(gp(dt_i),gp(dt_j))ç;

D₃(dt_i,dt_j)=÷V(ghp(dt_i))ç+÷V(ghp(dt_j))ç-2÷V(MCS(ghp(dt_i),ghp(dt_j))ç.

Таблица

	dt1	dt2	dt3	gp(dt1)	gp(dt2)	gp(dt3)	ghp(dt1)	ghp(dt2)	ghp(dt3)
dt1	0	4	4	4	8	8	4	14	13
dt2	4	0	2	8	4	6	8	10	11
dt3	4	2	0	8	6	4	8	12	9
gp(dt1)	4	8	8	0	8	8	0	14	13
gp(dt2)	8	4	6	8	0	4	8	6	9
gp(dt3)	8	6	4	8	4	0	8	10	5
ghp(dt1)	4	8	8	0	8	8	0	14	13
ghp(dt2)	14	10	12	14	6	10	14	0	7
ghp(dt3)	13	11	9	13	9	5	13	7	0

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

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

 

Литература

1. Кохов В.А., Джасим М.Р., Кохов В.В. Интегрированная среда визуального и алгоритмического решения задач поиска, сравнительного анализа и определения сложности ациклических графовых моделей систем. // ПСУН. Паспорт от 18.06.2009 г. – М., МЭИ, 2009.

2. Кохов В.В., Фальк В.Н. Структурная информатика: трансграфы деревьев, ордеревьев и их свойства : Тр. 17-ой международной НТК. М.: МЭИ, 2011. Т1. С. 372-373.