BC/NW 2009; №2 (15):10.3

 

СТРУКТУРНАЯ ИНФОРМАТИКА: ЗАДАЧИ РАЗЛИЧЕНИЯ И ОПРЕДЕЛЕНИЯ СХОДСТВА РАСПОЛОЖЕНИЯ ФРАГМЕНТОВ В ГРАФАХ

Кохов В.А., Кохов В.В.

(ГОУВПО «Московский энергетический институт (технический университет)», Россия)

Структурная информатика – новый раздел информатики актуальный для изучения студентами в университетах [1]. В докладе выделены задачи различения расположения и определения сходства расположения фрагментов в графах и приведены методы их решения. Методы программно реализованы в АСНИ «GMW» и используется в учебном процессе МЭИ (ТУ) (www.graphmodel.com).

Приведем формализованную постановку задач различения расположения фрагментов графа. Пусть G – обыкновенный  граф (G =(V, E), |V|=p, |E|=q). Обозначим через Â^l(G) (Â(G)) множество помеченных фрагментов (фрагментов) графа G, а через f_i ^lt, f_j ^ltÎÂ^l(G) - произвольные помеченные фрагменты типа t. Задача различения расположения двух однотипных помеченных фрагментов f^lt_i, f ^lt_j в графе G определяется следующими параметрами:

где x^t - отношение принадлежности фрагментов к одной орбите t-группы (Aut ^t(G)) автоморфного расположения фрагментов типа t.

Решение задачи DP1 сводится к установлению истинности утверждения:

t-группа индуцирована группой Aut(G), то есть группой автоморфизмов вершин графа G. В табл.1 приведены все автоморфизмы t-группы расположения цепей длины 2 и орбиты t-группы для графа G (рис.1).

Первым обобщением в разнообразии видов задач DP1 является задача автоморфного разбиения множества фрагментов типа t в графе G с параметрами:

где F ^lt – множество помеченных фрагментов типа t, вкладываемых в G.

 

Таблица 1.
Все автоморфизмы t-группы расположения цепей длины 2

 

Рис. 1. Диаграмма графа, его трансграфа цепей и графа сходства

расположения цепей

 

Результатом решения задачи DP является построение орбит Aut ^t(G).

Следующий вид задачи различения связан с различением расположения фрагментов f ^lt_i, f  ^lt_j типа t относительно выделенного фрагмента f ^lt_k того же типа t. Эта задача определяется следующими параметрами:

где  f  ^lt_i, f  ^lt_j, f  ^lt_kÎF ^l t; x ^t – отношение принадлежности фрагмента к одной орбите фиксатора t-группы относительно фрагмента f ^lt_k. Решением задачи DP2 является ответ на вопрос, связаны ли f  ^lt_i и  f  ^lt_j отношением x ^t, то есть, принадлежат ли f  ^lt_i и  f ^lt_j к одной орбите фиксатора t-группы относительно f ^lt_k . Обобщением задачи DP2 является задача автоморфного разбиения множества F^lt относительно выделенного фрагмента f ^lt_k с параметрами:

Обобщением задачи DP1 является задача различения расположения двух помеченных фрагментов f ^lt1_i, f ^lt2_j  разных типов t1 и t2 в графе G. Она определяется следующими параметрами:

где f ^lt1_iÎF ^lt1, f ^lt2_jÎF ^lt2; x ^t1Ít2 – отношение вида «некоторый элемент орбиты помеченного фрагмента f ^lt1_i изоморфно вкладывается в некоторый элемент орбиты помеченного фрагмента f  ^lt2_j», то есть

где Q( Aut ^t(G), f  ^lt ) – орбита  f  ^lt относительно t-группы.

Обобщением задачи DP4 является задача различения расположения всех помеченных фрагментов типа t1 и t2 в графе G:

Заметим, что для решения задач DP4 и DP5 требуется сначала решить две задачи DP (для фрагментов типа t1 и фрагментов типа t2).

Следующий вид задачи – задачи различения расположения f  ^lt1_i, f ^lt2_j  относительно выделенного фрагмента f ^lt2_k  типа t2 в графе G определяется следующими параметрами:

где x ^t1Ít2 – отношение вида «некоторый элемент орбиты расположения f  ^lt1_i изоморфно вкладывается в некоторый элемент орбиты расположения f ^lt2_j относительно фиксатора f ^lt2_k  для фрагмента f  ^lt2_j, то есть

Её расширением является задача различения расположения всех помеченных фрагментов типов t1 и t2 относительно выделенного фрагмента f  ^lt2_k  типа t2 в G с параметрами:

Назовём все поставленные задачи классом задач различения расположения фрагментов (класс DPF). Заметим, что задача построения всех помеченных фрагментов графа, то есть поиск канонических изоморфных вложений фрагмента в граф G принадлежит классу NPC.

Нетрудно показать, что задачи различения графов являются частным случаем задач DPF. Действительно, пусть даны G1 и G2. Построим граф   H=G1ÈG2. Тогда задачи различения G1 и G2 можно рассматривать как задачи различения расположения фрагментов типов t(G1) и t(G2) в H.

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

Рассмотрим основные подходы к решению задач различения расположения фрагментов в графе. Схема классификации основных подходов к решению задач различения представлена на рис.2. Алгебраический подход основан на использовании информации о строении конкретных групп автоморфизмов и задействует глубокие результаты прикладной теории групп. Используется в теоретических исследованиях. Переборно-групповой подход (ПП) использует переборные алгоритмы анализа Aut(G) и t-групп для получения точного решения задач установления x-эквивалентности. Структурно-характеристический подход (СХП) использует для различения различные инварианты. Этот подход объединяет переборные и не переборные методы.

 

 

Таблица 2.
 Обозначения базовых задач из инвариантного ядра задач различения

 

 

 

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

 

Рис. 2. Классификация подходов к решению задач различения графов и различения расположения фрагментов в графе

 

Многие результаты, полученные при исследовании СХП, используются для повышения эффективности алгоритмов построения Aut(G) (трансграфовый подход), а орбиты t-групп служат для оценки точности полученных отношений t-эквивалентности. Он позволил построить методологию иерархического уточнения расположения фрагментов в графе, а ПП дал предел такого уточнения (орбиты t-групп). Приведем кратко метод, входящий в СХП, для решения задач различения и определения сходства расположения фрагментов на основе  b-моделей [2]. В табл.3 приведена матричная форма b-модели для графа G (рис.1), построенная на основе достройки всех помеченных цепей G до фрагментов G, изоморфных элементам базиса из поддеревьев G.

 

Таблица 3.
Матрица b-модели и вклады фрагментов в общую сложность графа

 

Оценкой точности решения задач DP1 является «чувствительность» инварианта (значений b-модели) a(f  ^lt/B, x^t)=NC/NO, где NC – число классов эквивалентного расположенных фрагментов f ^lt по значениям b‑модели;  NO – число орбит t-группы.          Точное решение задачи DP1 на основе трансграфового подхода требует построения g-модели [2], например трансграфа цепей (рис.1) и определения орбит вершин в трансграфе цепей. Для получения точного или приближенного решения задачи DP1 для цепей необходимо построить b-модель для трансграфа цепей в базисе B. Чем длиннее базис, тем точнее результат решения задачи.

Результатом вычисления сходства расположения фрагментов в G будем считать граф попарных расстояний классов, эквивалентно расположенных фрагментов, то есть фрагментов с одинаковыми значениями строк матрицы b-модели. Иерархический анализ все более и более точного сходства расположения классов фрагментов G включает: (1) определение попарных расстояний между фрагментами на основе вычисления модуля разности индексов относительных вкладов (irc(f ^t(c))) в сложность; (2) определение на основе метрики Евклида расстояний между расширяемыми по числу элементов базиса значениями строк матрицы b-модели.

На рис. 1 приведен пример графа сходства расположения классов цепей.

Предложенные методы программно реализованы в АСНИ «GMW» и используются студентами МЭИ (ТУ) при изучении четырех дисциплин.

ЛИТЕРАТУРА

1.     Кохов В.А. Основы структурной информатики. Тезисы докладов международной конференции «Информационные средства и технологии» международного форума информатизации МФИ-98, Т3. Москва, 1998. –  С.42-47.

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