Книги, научные публикации
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ МЕТОД РЕШЕНИЯ ЗАДАЧИ РАЗЛИЧЕНИЯ ОРГРАФОВ НА ОСНОВЕ СЛОЖНОСТИ В.А. Кохов, кандидат технических наук, доцент кафедры Высшей математики
на факультете экономики Национального исследовательского университета Высшая школа экономики.
В.В. Кохов, студент кафедры Прикладная математика Московского энергетического института, e-mail: viktorkokhov@rambler.ru.
Адрес: г. Москва, ул. Красноказарменная, д. 14.
Предложен метод решения задачи различения орграфов. Основу метода определяет матричная модель сложности, которая учитывает количественные и качественные харак теристики фрагментов орграфа. Модель впервые позволяет оценивать значимость каждого фрагмента орграфа в его общей сложности. Приведены результаты решения задач различения и определения сходства для орграфов.
Ключевые слова: орграф, сложность орграфа, проблема различения орграфов, модель сложности, сходство орграфов, расположение фрагментов.
Приведем краткий обзор по построению мо 1. Введение делей сложности графов. Одна из первых мо ложность системы, будучи ключевым поня делей была связана с построением теоретико тием системологии, требует глубоких и ин информационных индексов [4,5]. Пусть имеется С тенсивных исследований и ориентирована граф G=(V, E), где |V|=p, |E|=q и множество его вер на развитие подходов к анализу сходства систем. шин V, разбивается на k классов эквивалентности Сложность и сходство структурированных объ- Vi, i=1..k. В качестве отношения эквивалентности может выступать принадлежность вершин к одной ектов (корпоративных социальных сетей;
семанти орбите группы автоморфизмов графа. Тогда инфор ческих сетей, абстрактных графов, графов синтак мационное содержание (количество информации), сической структуры предложений и др.) наиболее приходящееся на одну вершину, будет определять востребована в таких областях, как системы искус ся следующей формулой:
ственного интеллекта, информационно-поисковые k системы структурной информации (семантическо IIC (G/V ) =- log2 Ci, C i го web-поиска текстовых документов) и др. [1-3]. i = БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ где Сi=|Vi|/|V|. Полное информационное содержание др. Показано, что к перспективным направлениям графа, рассчитанное на основе V, будет TIIC(G/V)= построения моделей сложности ГМС четвертого =|V|IIC(G/V). TIIC(G/V) рассматривается как ин- поколения следует отнести такие матричные моде тегральная количественная мера его структурной ли, которые учитывают три уровня характеризации сложности (неоднородности). На основе информа- в единой модели: (1) сложность ГМС как единого ционного содержания графа может быть построено целого;
(2) сложность фрагментов ГМС;
(3) слож множество различных индексов сложности, если ность расположения фрагментов ГМС в ее тополо вместо множества вершин анализировать другие гии с характеризацией вкладов в общую сложность.
множества однотипных фрагментов, например це Ниже предлагается матричная модель сложности пей с длиной два ( ). Из [6] известен орбитальный орграфов, позволяющая:
информационный индекс графа в базисе связок ( ):
учитывать как количественные, так и каче ственные характеристики систем, представленных k OII (G/P2 ) = 2 log2 - i log2 i орграфами;
i= обобщить индексы симметрии расположения связок до индексов симметрии расположения где k - число орбит группы расположения в G, любых фрагментов орграфа и вычислять их значе - количество связок в i-ой орбите. По сути, это ния все с большей и большей точностью;
полное информационное содержание графа, рас проводить иерархический анализ сложности считанное на основе связок, плюс л - ин log орграфов с уточнением результатов на каждом сле формация о размере графа (число связок).
дующем уровне иерархии;
В [7] для определения сложности графа G введена определять вклад любого фрагмента в общую функция сложность;
pq все более и более точно решать задачи различе CM (G) = (v,v ), i j p+q ния орграфов;
i< j все более и более точно решать задачи различе где (vi,vj ) - число простых цепей из вершины vi в ния расположения фрагментов в орграфах;
вершину vj. Указано, что эта функция соответству формировать и исследовать новые виды отно ет интуитивному понятию сложности графа. В [8] шений эквивалентности орграфов.
предложена функция, значение которой, равно числу остовных деревьев (каркасов) графа. В каче 2. Основные определения стве функции сложности в [9] используется число деревьев, изоморфно вкладываемых произвольным Пусть G=(V,E) орграф. Два орграфа G=(V,E) и образом в граф G.
G*=(V*,E*) изоморфны (G G*), если В [10] рассматривается топологическая сложность и u, v V u,v E, v E*, графовых моделей систем (ГМС), причем в наи где u, v V*.
более общем и системном виде. Выделены девять требований, предъявляемых к моделям (функциям) Орграф G*=(V*,E*) изоморфно вкладывается в сложности систем. В [11] приведен обзор подходов орграф G=(V,E) как порожденный подграф (G* ), к определению структурной сложности графов и (подграф (G* G)), если в G есть порожденный под выделены три этапа в построении моделей: (1) по граф (подграф) G*=(V*,E*), для которого справед строение индексов сложности, то есть числовых ливо отношение G* G.
инвариантов графов, отражающих одну из сторон сложности, например сложность в терминах цеп- Изоморфизм орграфа на себя называется авто морфизмом и обозначается через. Множество ных, циклических, древесных и др. характеристик;
всех автоморфизмов орграфа образует группу по (2) построение моделей сложности, основанных на мультииндексах, отражающих несколько сторон умножению автоморфизмов и обозначается через комплексного понятия сложность;
(3) построе- Aut(G). Порядок группы обозначим через Aut(G).
ние концептуальных и математических моделей, Под числом канонических изоморфных вложений G* включающих многоуровневое отражение сложно- в G будем понимать величину, определяемую сле сти, с привлечением достижений теории систем, дующим образом w(G*,G)=W(G*,G)/Aut(G), где теории графов, теории информации, топологии и W(G*,G) - число всех изоморфных вложений G* БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ в G. Орбитой вершины v V называется подмноже- ным с анализом Aut(G) (например, орбиты t-группы).
ство вершин орграфа G, которые могут t-группа точно характеризует симметрию расположе быть отображены на вершину v: ния фрагментов типа t в орграфе G. Все неопределяе мые ниже понятия можно найти в [12, 13].
.
3. Задачи различения орграфов и различения расположения Орбиты вершин орграфа определяют классы их их фрагментов эквивалентного расположения.
Абстрактный тип t - произвольный орграф, Пусть обозначает множество всех связных ор определённый с точностью до изоморфизма. Груп графов, на котором задано отношение R - быть пу его вершинных автоморфизмов обозначим через изоморфными. Тогда задача различения (установ Aut(t). Обозначим множество всех канонических ления факта изоморфизма) двух орграфов, изоморфных вложений абстрактного типа t в G че определяется следующими параметрами:
рез F t(G) = {f1t, f2t,... fmt}, а через обозначим ко личество фрагментов типа t в G. Если на множестве DG =< ;
Gi,G ;
R >.
j вершин типа фрагмента t и G задана нумерация, то фрагмент f t орграфа G может быть представлен по- Решением задачи DG является ответ на вопрос, меченными фрагментами f lt, когда каждой вершине являются ли и Gj изоморфными?
типа фрагмента t сопоставляется номер вершины Задача различения расположения двух фрагментов орграфа G, которой она соответствует при вложе-, типа t в орграфе G определяется следую нии. Число помеченных фрагментов, представляю- щими параметрами:
щих один и тот же фрагмент G, равно порядку груп пы вершинных автоморфизмов абстрактного типа., Пусть Aut t(G) является индуцированным пред где - отношение принадлежности фрагмента к ставлением группы Aut(G) и определяет симме одной орбите t-группы. Решением задачи является трию расположения фрагментов типа t в G. Под ответ на вопрос, принадлежат ли, одной и той t-автоморфизмом G будем понимать подстановку же орбите t-группы?
на множестве помеченных фрагментов типа t оргра фа G (или канонических изоморфных вложений) 4. Инварианты и их применение F lt (G), индуцированную некоторым вершинным ав для решения задач томорфизмом орграфа G. В процессе индуцирования различения орграфов помеченный фрагмент filt F lt (G), представленный ка ноническим изоморфным вложением ( ) Основным инструментом при решении задач раз орграфа G, переходит в помеченный фрагмент личения орграфов является понятие инварианта fj lt (G) F lt (G), каноническое представление кото орграфа. Пусть - непустое множество с отноше рого получено канонизацией вложения (,,Е, ), нием эквивалентности (множество чисел, векто где ui= - число вершин фрагмен ров, матриц, графов и т.д.). Функция IN, заданная та типа t. Группой t-автоморфизмов G (Aut t(G) или на множестве и принимающая значения в, t-группа) будет группа подстановок, носителем называется инвариантом орграфа G, если справед которой является всё множество t-автоморфизмов ливо условие:
для данного t, а групповой операцией - операция произведения подстановок. Тот факт, что мно Gi,G [Gi (R)G IN (Gi )()IN (G )] j j j.
жество t -автоморфизмов образует группу, непо средственно следует из свойств Aut(G). Степень Графы Gi,Gj IN-эквивалентные (Gi (IN )G ), t-группы равна числу канонических изоморфных j если IN (Gi )()IN (G ).
вложений абстрактного типа t в орграф, j а порядок меньше или равен порядку Aut(G), так Инвариант IN называется полным инвариантом как два различных нетождественных вершинных орграфа, если выполняется условие:
автоморфизма могут индуцировать один и тот же t-автоморфизм. Все понятия, связанные с анализом Gi,G [IN (Gi )()IN (G ) Gi (R)G ].
j j j Aut t(G), определяются аналогично понятиям, связан БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Под чувствительностью инварианта орграфа G в как локальные (пути малой длины), так и глобаль множестве будем понимать отношение вида: ные (пути большой длины) свойства орграфов;
(3) (IN,R)=|T (IN )| / |T (R)|, где обозначает пути - наиболее легко конструктивно перечислимые число классов IN-эквивалентности орграфов, а фрагменты в сравнении с другими фрагментами - число неизоморфных орграфов в множе- орграфов;
(4) пути относятся к классу монотонно стве T. Чувствительность инварианта определяет наращиваемых по сложности базисов СД для харак точность решения задачи различения орграфов в теризации орграфов.
множестве T. Границей вырождаемости инварианта IN в множестве называется наименьшее число вершин G T, при котором инвариант IN становится неполным.
5. Матрица достроек фрагментов 4 как инвариант характеризации орграфа и характеризации расположения его фрагментов Пусть Рис. 1.
F t(G)={F 1, F 2,... F t,...F T} (F l(G)={F l1, F l2, F tt,... F lT}) обозначает множество всех собственных фраг Для орграфа G (рис. 1) приведены примеры двух ви ментов (помеченных фрагментов) орграфа G, а дов матриц EM(G/V P) (табл. 1, выделены серым цве F lt(G)={f1lt, f2lt,... fjlt,...frtlt} множество помеченных том), в которых в качестве строк выступают вершины фрагментов типа t, j - номер фрагмента, rt - чис- G, а в качестве базиса СД - базис путей P =
любые орграфы включают пути;
(2) пути отражают Таблица 1.
Вершина концевая достраивается до путей Вершина достраивается до путей irc irc irc irc V P0 P1 P2 P3 (f t(C.n)) (f t(C)) V P0 P1 P2 P3 (f t(C.n)) (f t(C)) 5 1 3 3 2 0,3846 0,3846 2 1 4 5 2 0,2885 0, 1 1 1 3 2 0,3616 0,3616 5 1 3 3 2 0,2308 0, 2 1 4 2 0 0,1231 0,1231 1 1 1 3 2 0,2077 0, 3 1 2 1 0 0,0654 3 1 2 2 1 0, 0,1308 0, 4 1 2 1 0 0,0654 4 1 2 2 1 0, Slw 5 12 10 4 1 Slw 5 12 15 8 40 Sw 1 2 2 2 Sw 1 2 3 4 WF 5 6 5 2 WF 5 6 5 2 ISC 5 18 45 62 ISC(G/P)=130 ISC 5 18 45 62 ISC(G/P)= БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ 6. Расширенная матрица EM (G / Pl e P);
EM (G / Pl P);
достроек фрагментов EM (G / Pl Se P);
EM (G / Pl S P).
и матрица вкладов фрагментов в общую сложность орграфа l В наиболее общем виде матрица EM (G / F F ) Эта матрица определяет основу иерархического в качестве строк включает все подграфы из множе метода анализа сложности орграфа с вычислением ства Fl(G), а в качестве столбцов - все подграфы из вкладов фрагментов, вкладов каждого класса экви множества F(G). Таким образом, получаем страти валентно расположенных фрагментов для каждого фицированную систему матриц от EM (G /V P) l типа t и вкладов фрагментов в сложность орграфа.
до EM (G / F F ), расширяемую по трем направ l l Добавим к матрице EM (G / F B) пять новых лениям: (1) от V до F ;
(2) от P0 до F;
(3) одновре строк:
менно по (1) и (2). Это приводит к формированию и исследованию новых систем уточняемых отношений 1. Строки с номером нуль для вектор-индекса слож эквивалентности орграфов. ности элементов b B:
Чтобы упорядочить фрагменты из F(G) по возрас V_ISC (G / B) =< ISC (b1 ),..., ISC (bj ),..., ISC (bk1) >.
танию сложности, определим индекс сложности орграфа. Под структурным спектром G в базисе СД 2. Строки с номером (k+1) со значениями элементов В=
ij G и =0 в противном случае [14].
i lt l i= f F Пусть для G построен его полный структурный спектр (ПСС) в базисе СД 3. Строки с номером (k+2), значения элементов которой Sw(bj), равны суммарному числу канони В=
где bi - фрагмент базиса;
wi - число канонических изоморфных вложений фрагмента bi в G. Очевид- ll l l Sw(F / B) =< Sw(F / b1 ),..., Sw(F / bj ),..., Sw(F / bk1) > но, что w(K1)=p, а w(K2)=q. Примем ISC(K1)=1, t ISC(K2)=3. Так как для любого фрагмента fi орграфа TT f (bj ) l G можно определить его ПСС, а для каждого фраг- где Sw(F / bj ) == f / bj ).
w( t t Aut( f ) t =1 t = мента от фрагмента G, можно построить его ПСС и т.д., то рекурсивным методом всегда можно вычис 4. Строки с номером (k+3) со значениями элементов лить индекс спектральной сложности (ISC) (ниже сложности) и вектор-индекс сложности (V_ISC) ll w (bj ) = Slw(F / bj ) / Sw(F / bj ).
j орграфа G в базисе СД B:
5. Строки с номером (k+4) со значениями элементов ISC (G / B) = w1ISC (b1) + + w2ISC (b2),..., w ISC (bj ),..., wk1ISC (bk1) ;
j V_ISC (G / bj ) = w (bj )ISC (bj ).
j V_ISC (G / B) =< w1ISC (b1);
w2ISC (b2 );
... ;
В результате построим расширенную матрицу до w ISC (bj );
... ;
wk1ISC (bk1) >.
j строек фрагментов l Для G (рис. 1) при использовании базиса путей EM* (G / F B).
подграфов P=
l На основе EM* (G / F B) построим матрицу ISC(G/P)=5 1+6 3+5 9+2 31=130;
V_ISC(G/P)=<5;
18;
45;
62>;
l MIRC (F B(G)) = irc( fit /bj ), i = 0..k + 4;
j = 1..k1+ SS(G/P)=<1, 1, 1, 1>;
FS(G/P)=<5, 6, 5, 2>. относительных вкладов фрагментов в сложность G.
БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ 7. Метод иерархического анализа Значения элементов матрицы вычисляются по сложности орграфов формуле Вычисление матриц MIRC(F l B(G)) позволяет mij ISC(bj ) проводить иерархический анализ сложности, вклю irc( fit / bj ) = l ISC (G / B) Sw(F / bj ).
чающий пять основных уровней, с последователь ным уточнением результатов на основе:
Тогда величина irc( fit / B), вычисляемая по фор- 1. Индексов сложности - ISC(G/B);
муле 2. Вектор-индексов сложности - V_ISC(G/B);
3. Вектор-индексов относительных вкладов каждого k ISC (bj ) 1 типа фрагментов t (вершины, дуги, пути с длиной irc( fit / B) = m l / bj ) и т.д.) - V_irc(G, F t), где t = 1..T;
ij ISC (G / B) Sw(F j =1, 4. Вектор-индексов относительных вкладов классов фрагментов в каждом типе фрагментов определяет относительный вклад fit в общую слож ность при использовании базиса B.
V_irc(G, F t (C)), Фрагменты fit, имеющие одинаковые значения где C - номер класса фрагментов типа t и t = 1..T;
вкладов irc( fit / B), образуют класс f t(C) эквива 5. Вектор-индексов относительных вкладов каждого лентных по расположению фрагментов типа t с об фрагмента с номером n в классе C типа t - щим вкладом irc( fit (C ) / B). Сумма относительных вкладов по всем фрагментам одного типа t образует V_irc(F t (C.n)/B), где t = 1..T.
t вклад irc( f / B). Расширенную матрицу достроек Дополнительные уровни анализа сложности фрагментов, дополненную тремя столбцами:
определяются на основе вектор-индексов относи t (k1+1) со значениями irc( f (C.n) / B) для каж тельных вкладов каждого фрагмента с номером n в дого типа t;
классе C типа t по каждому элементу bj B - t (k1+2) со значениями irc( f (C ) / B) для каждо V_irc(F t (C.n)/bj), где t=1..T, j=k1, (k1Ц1),Е, 1.
го типа t;
t (k1+3) со значениями irc( f / B) для каждого Для трех орграфов (рис. 2) в табл. 2 приведены типа t, матрицы, упорядоченные по убы l обозначим MIRC (F B(G )).
ванию значений вкладов всех путей по каждому типу t, где t=P0 - P2.
Пример матрицы MIRC (V P (G )) без значений Приведем результаты сравнительного анализа t irc( f (C.n) / bj ) для орграфа G (рис. 1) приведен трех орграфов по иерархической схеме:
l в табл. 1. На основе MIRC (F F (G )) легко по на первом уровне строить матрицу абсолютных вкладов фрагментов в l ISC(G1 /P)=ISC(G2 /P)=ISC(G3 /P);
сложность G, т.е. матрицу MIAC (F F (G )).
2 4 3 1 3 3 1 2 4 1 Рис. 2.
БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Таблица 2.
irc irc irc irc irc irc 1 3 9 1 3 Pl(G1) Pl(G2) Pl(G3) (P t(C.n)) (P t(C)) (P t) (P t(C.n)) (P t(C)) (P t) 3 2 1 3 3 7 4 1 3 3 14 4 1 1 3 3 7 1 1 3 3 23 1 4 1 2 1,5 4,5 3 1 2 1,5 4, 9 2 3 1 2 1,5 4,5 2 1 2 1,5 4, 34 12 0 1 3 4 4 13 0 1 1,5 2, 13 23 0 1 1,5 2,5 34 0 1 1,5 2, 5 23 24 0 1 1,5 2,5 11 12 0 1 1,5 2,5 14 13 0 1 0 1 24 0 1 1,5 2, 24 14 0 1 0 1 14 0 1 0 1 134 124 0 0 1,5 1,5 124 0 0 1,5 1, 3 3 3 234 123 0 0 1,5 1,5 134 0 0 1,5 1, Slw(bj) 4 15 18 37 37 37 Slw(bj) 4 15 18 37 37 Sw(bj) 1 3 9 10 Sw(bj) 1 3 9 WF(bj) 4 5 2 11 WF(bj) 4 5 2 ISC(G/P)=37 ISC(G/P)= V_ISC(bj) 4 15 18 37 V_ISC(bj) 4 15 18 P(p 1) P0 P на втором уровне Aut (G ), Aut (G ),..., Aut (G ), V_ISC(G1 /P)=V_ISC(G2/P)=V_ISC(G3 /P);
то нетрудно доказать, что справедливы следующие на третьем уровне утверждения.
Утверждение 1. Индекс TIIC(G/V) и индексы V_irc(G1,P t(C))=V_irc(G2,P t(C))=V_irc(G3,P t(C));
TIIC(G/P1),Е,TIIC(G/P(p-1)) являются восстанавли на четвертом уровне ваемыми характеристиками из для орграфа G.
V_irc(G1,P t(C.n)/B)= =V_irc(G1,P t(C.n)/B) V_irc(G1,P t(C.n)/B).
Действительно, например, для орграфа G1 (рис. 2) имеем Таким образом, на четвертом уровне выявлено различие по сложности орграфов G1 и G2 с G3. Для G | P0(C1) | и G2 значения матриц одинаковые, TIIC(G1 /V ) =WF (b1) log2 (| P (C1) |) + следовательно, G1 и G2 IN-эквивалентные орграфы WF (b1) по. Заметим, что полученные клас | P (C2 ) | сы эквивалентно расположенных путей в G1ЦG3, + log2 (| P (C2 ) |).
WF (b1) являются орбитами групп P0 P1 P Aut (G), Aut (G ), Aut (G ).
Утверждение 2. Индекс OIIC(G/P2) и индексы OIIC(G/P3),Е,OIIC(G/P(p-1)) являются восстанавли Если базис путей является достаточным для того, ваемыми характеристиками из для чтобы классы эквивалентно расположенных путей орграфа G.
стали орбитами групп БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Действительно, например, для орграфа G1 (рис. 2) MIRC(P l P(G)), получим: 10 классов:
имеем (G1)>(G2)>(G3)>(G4)>(G5)>(G6,G7)>(G8,G9)>(G10)>(G11)>(G12,G13).
OII (G / P2 ) = 2WF (b2 ) | P (C ) | log2 (| P (C1) |) + ( Следовательно, точность решения задачи разли 22 чения орграфов + | P (C2 ) | log2 (| P (C2 ) |)+ | P (C3) | log2 (| P (C3) |).
) (MIRC (Pl P(G)),R) = 0,769.
Утверждение 3. Индекс CM(G) являются восста Заметим, что все пары орграфов, образующие навливаемой характеристикой из классы эквивалентности, имеют инверсную ориен для орграфа G.
тацию дуг. Такие орграфы будем называть инверс Действительно, например, для орграфа G1 (рис. 2) ными. Для них справедливо имеем Утверждение 4. Неизоморфные инверсные пары WF (b1)WF (b2 ) OII (G1 / P2 ) = WF (b2 ) +WF (b3).
() орграфов являются IN-эквивалентными по значе WF (b1) +WF (b2 ) ниям матрицы.
Следовательно, справедливо Если классы расположения путей не являются орбитами, то мы имеем метод приближенного вы- Утверждение 5. Матрица MIRC(P l P(G)) не яв числения рассмотренных индексов. Для точного ляется полным инвариантом орграфов и граница ее вычисления индексов необходимо базис путей вырождаемости равна трем.
наращивать элементами типа полупути, контура, В табл. 3 приведены результаты определения точ ордеревья и т.д. Выделим, что добавляя к базису ности решения задач различения для орграфов, се путей, например, один полупуть вида K1,2, мы по тей, графов по ISC(G/P) и MIRC(P l P(G)).
строим и определим не Использованы следующие обозначения: ND, NS, изоморфизм G1 и G2 (рис. 2).
NG - число соответственно орграфов, сетей, гра фов;
(D,ISC), (S,ISC), (G,ISC) - чувствитель 8. Результаты определения ность по ISC соответственно для орграфов, сетей, точности решения задач графов;
(D,MIRC), (S,MIRC), (G,MIRC) - чув различения орграфов ствительность по MIRC соответственно для оргра На рис. 3 приведены диаграммы всех орграфов с p=3. фов, сетей, графов.
Сравнивая орграфы по значениям относительных Анализ результатов приводит к следующим вы вкладов путей в сложность (irc(P l (C.n))) из матриц водам: (1) граница вырождаемости ISC(G/P) для G1 G2 G3 G4 G G6 G7 G8 G9 G G11 G12 G Рис. 3.
БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Таблица 3.
p ND (D,ISC) (D,MIRC) NS (S,ISC) (S,MIRC) NG (G,ISC) (G,MIRC) 3 13 0,615 0,769 4 0,750 0,75 2 4 199 0,407 0,638 24 0,542 0,64 6 5 9364 0,183 0,533 267 0,269 0,51 21 0,947 6 1530843 0,064 0,596 5647 0,094 0,47 112 0,938 7 237317 0,019 0,47 852 0,977 8 11117 0,983 9 261080 0,989 орграфов (сетей, графов) равна 3 (3, 5);
(2) грани- ll DGi,G ) = V (F B(Gi )) + E (F B(Gi )) + ( j ца вырождаемости MIRC(P l P(G)) для орграфов ll (сетей, графов) равна 3 (3, больше 9);
(3) каждый + V (F B(G )) + E (F B(G )) jj класс эквивалентности орграфов включает инверс ll -2 V (mcf (F B(G),F B(G ))), ные пары орграфов;
(4) для более точного решения j задач различения орграфов (сетей) необходимо базис путей расширять полупутями.
где F l B(G) - двудольная граф-модель с весами на дугах, соответствующая EM(G/F l F), 9. Новые методы анализа mcf(F l B(Gi), F l B(Gj)) - максимальный общий под сходства орграфов граф по числу дуг для двух граф-моделей F l B(Gi), F l B(Gj) или коэффициент сходства Задача вычисления сходства орграфов включает следующие параметры:
ll MSI (Gi,G ) = (V (mcf (F B(Gi ),F B(G ))) + j j 1. M={G1, G2,..., Gi,Е, G } - множество орграфов, n анализируемых на сходство.
ll + E (mcf (F B(Gi),F B(G ))) / B(Gi) j 2. В=
/ (V (F B(Gi )) + E (F B(Gi )) )(V (F B(G )) + j 5. ISC(B)= ISC(b2); ...; ISC (bj); ISC (bk1)> - l + E (F B(G )) ). j набор весов СД для учета их качественных харак теристик. Приведем результаты анализа сходства на основе 4. D(Gi,Gj) - метрика (псевдометрика) или функция EM(G/P l SF) по второму подходу для 13 орграфов для вычисления коэффициентов сходства (несход (рис. 3) и результаты их кластеризации. В графе по ства) (SC). парных расстояний получено 19 разных значений Необходимо построить матрицу (граф) попарных расстояний (весов ребер) в диапазоне от 0 до 48. расстояний или коэффициентов сходства (несходства). При кластеризации из графа попарных расстоя Выделим два метода решения задачи на основе ний последовательно удалялись ребра, значения матричных моделей: веса которых, превышали соответственно следую 1. Метод иерархического уточняющего анализа, щие границы 9; 8; 6; 3; 2; 0. В результате выделено использующий в качестве метрик: 7 одноэлементных кластеров и 3 двухэлементных, на первом уровне - |ISC(Gi / B) - ISC(Gj / B)| ; состоящих из неизоморфных инверсных орграфов на 2-5 уровнях - метрику Евклида для соответству- (рис. 4). Такие же кластеры выделены на этапе 4 по методу подхода 1. ющих вектор-индексов вкладов из MIRC(F l B(G)), для каждого класса, полученного на предыдущем Заметим, что использование ПП, основанного на уровне. определении mcf для всех пар орграфов при одина 2. Метод анализа на основе подструктурного под- ковом числе вершин, не позволяет проводить класте хода (ПП), использующего вычисление попарных ризацию, из-за недостаточного диапазона значе расстояний ний весов ребер в графах попарного сходства. БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г. МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Выделим, что, используя метрику Евклида для вы- трицы MIRC(F l F(G)), мы решаем задачу определения числения попарных расстояний между строками ма- попарного сходства расположения фрагментов орграфа. 3 10 12 6 11 6 2 2 3 3 9 8 2 8 9 3 5 5 3 2 8 2 кластера 4 кластера 10 12 6 10 12 2 13 3 0 8 5 3 5 3 5 кластеров 6 кластеров 10 12 2 12 11 0 13 9 1 9 0 8 7 5 0 5 3 4 3 6 8 кластеров 10 кластеров Рис. 4. 10. Экспериментальные оценки полиномиальную оценку Т=О(p3) вычислительной вычислительной сложности задачи сложности алгоритма построения MIRC(P l P(G)) построения матрицы относительных вкладов для ордеревьев. Основу алгоритма составляет ме фрагментов в сложность орграфов тод достройки вершины ордерева до пути, задан ной длины. На рис. 5 приведены графики ЭОВС Экспериментальные оценки вычислительной алгоритма построения MIRC(P l P(G))для ордере сложности (ЭОВС) решения задачи построения ма вьев со средними значениями индексов сложности трицы MIRC(P l P(G)) получены на основе исполь (ISC(G/P)) и числами вершин от 108 до 508. зования новых программных подсистем, включен ных в АСНИ Мастерская граф-моделей [16, 17]. В общем случае задача построения MIRC(P l P(G)) Эксперименты проводились на ноутбуке (SONY, для орграфов (сетей) является NP-полной про Intel Core i5, 2.67 GHz, память 4 Gb, Windows 7). блемой, так как число путей всех длин в орграфах (сетях) растет экспоненциально и частным случаем Учитывая особенность ордеревьев, связанную с существованием для каждой пары вершин толь- для нее является класическая NP-полная проблема ко одного пути, нетрудно получить теоретическую определения гамильтонова пути в орграфе (сети) БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г. МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ y = 3247,8x4 - 16612x3 + R2 = 0, 108 158 208 258 308 358 408 458 ЧИСЛО ВЕРШИН Рис. 5. [15]. Сокращение перебора при построении ма- рем. Были построены матрицы MIRC следующих трицы MIRC(P l P(G)) методом достройки вершин размеров (число строк число столбцов): 1) у1 от до путей, заданной длины, осуществляется за счет 10013 до 52013; 2) у2 от 62213 до 339513; 3) у3 от учета симметрии (орбит стабилизаторов Aut(G)) и 196213 до 1236913; 4) у4 от 494513 до 3967513; инвариантов вершин орграфов [13]. 5) x1 от 10021 до 52021; 6) x2 от 62221 до 339521; 7) x3 от 196221 до 1236921; 8) x4 от 494521 до На рис. 6-9 приведены ЭОВС алгоритма построе 3967521. ния восьми видов матриц: Необходимо выделить, что задача вычисления MIRC(P l SP0-12(G)); MIRC(P l SP0-12(G)); 0-0 0- сходства пары орграфов на основе поиска МОФ MIRC(P l SP0-12(G)); MIRC(P l SP0-12(G)); 0-4 0- их матриц MIRC(P l P(G)) имеет полиномиальную вычислительную сложность при условии, что ис MIRC(P l SP0-20(G)); MIRC(P l SP0-20(G)); 0-0 0- пользуется один и тот же базис P. Это обосновано MIRC(P l SP0-20(G)); MIRC(P l SP0-20(G)); 0-4 0- возможностью сведения задачи поиска МОФ двух l Анализировались случайные орграфы с числа- матриц MIRC(P P(G)) к задаче поиска макси ми вершин от 100 до 600 и средней степенью (сум- мального паросочетания в двудольном орграфе с мой полустепеней исхода и захода) равной четы- весами на дугах. y1 = 35,52x4 - 473,1x3 + x1 = 2378,x4 - 30780x3 + 2184,x2 - 3729,x + 13856x2 - 23958,x + R2 = 0, R2 = 0, 100 200 300 400 500 600 100 200 300 400 500 ЧИСЛО ВЕРШИН ЧИСЛО ВЕРШИН Рис. 6. БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г. ВРЕМЯ, (мс) ВРЕМЯ, (мс) ВРЕМЯ, (мс) МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ 350000 x2 = 6663,x4 - 86081x3 + y2 = 102,8x4 - 1367,x3 + 38713x2 - 66908x + 6314,x2 - 10802x + R2 = 0, R2 = 0, 100 200 300 400 500 600 100 200 300 400 500 ЧИСЛО ВЕРШИН ЧИСЛО ВЕРШИН Рис. 7. y3 = 169,8x4 - 2263,x3 + x3 = 10830x4 - 13952x3 + 10479x2 - 18008x + 500000 62632x2 - 1E + 06x + R2 = 0, R2 = 0, 100 200 300 400 500 600 100 200 300 400 500 ЧИСЛО ВЕРШИН ЧИСЛО ВЕРШИН Рис. 8. y4 = 137,1x4 - 3157x3 + x4 = 15203x4 - 19592x3 + 14588x2 - 24943x + 13584 87972x2 - 2E + 06x + R2 = 0, 12000 R2 = 0, 100 200 300 400 500 600 100 200 300 400 500 ЧИСЛО ВЕРШИН ЧИСЛО ВЕРШИН Рис. 9. БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г. ВРЕМЯ, (мс) ВРЕМЯ, (мс) ВРЕМЯ, (мс) ВРЕМЯ, (мс) ВРЕМЯ, (мс) ВРЕМЯ, (мс) МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Заключение задач, связанных с определением границ вырожда емости матричных моделей в базисе путей для ор Предложены матричные модели, позволяю графов, сетей и графов. Модели полезны для реше щие проводить иерархический уточняющий ана ния прикладных задач различения и определения лиз сложности и сходства с учетом количествен сходства ГМС, например, логико-вычислительных ных и качественных характеристик фрагментов сетей, представляющих знания, сетей коммуни орграфов. Эти модели позволили расширить и до каций, компьютерных сетей и др. Предложенные полнить теоретико-информационный подход к методы анализа сложности и сходства программно определению сложности орграфов качественными реализованы и используются в учебном процессе характеристиками его фрагментов. Рассмотрено применение моделей для решения теоретических НИУ ВШЭ, МЭИ (ТУ). Литература 1. Финн В.К. Индуктивный метод соединенного сходства-различия и процедурная семантика ДСМ метода.//НТИ, сер. 2, №4, 2010. 2. Кузнецов С.О. Финн В.К. Распространение процедур ЭС типа ДСМ на графы. //Техн.кибернетика, 1988, №5, С.4-11. 3. Игнатов Д.И., Кузнецов С.О. О поиске сходства интернет-документов с помощью частых замкнутых множеств признаков. Десятая национальная конференция по искусственному интеллекту с междуна родным участием. КИИ-2006: Труды конференции. В 3-х т. М.: Физматлит, 2006. С. 245-249. 4. Шеннон К. Работы по теории информации и кибернетике. Ч М.: Изд. ин. лит., 1963. 5. Бончев Д.Г. Характеризация химических структур с помощью теории информации и теории графов. Автореферат дисс. докт. хим. наук. - Бургас, 1983. - 48 с. 6. Бертц С. Математическая модель молекулярной сложности. Химические приложения топологии и теории графов /Под ред. Р. Кинга, М.: Мир, 1987. - С. 236-258. 7. Minoly D. Combinatorial graph complexity. // Atti. Acad. Waz. Li. Rend. A. Sci. fis. mat. l'natur, vol. 59, no. 6. рр. 154-171, 1975. 8. Grone R., Herris R. A Bound for the Complexity of a Simple Graph. //Discrete Math., vol. 69, no. 1, рр. 97-99, 1988. 9. Загорянская А.А., Кохов В.А. Структурная сложность информационных систем и ее характеризация в базисе деревьев. Труды НТК студентов и аспирантов вузов России, Т1, Москва, 1998. - С.180-182. 10. Bonchev D., Polansky O.E. On the Topological Complexity on Chemical Systems // Studies in Physical and Theoretical Chemistry, 1987.V.51. P. 126-158. 11. Кохов В.А. Концептуальные и математические модели сложности графов. М.: Издательство МЭИ, 2002. - 160 с. 12. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. - Спб.: БХВ-Петербург, 2003. - 1104 с. 13. Алгоритмы и программы решения задач на графах и сетях //Нечепуренко М.И., Попков В.К., Кохов В.А. и др. Новосибирск: Наука. 1990. - 515 с. 14. Кохов В.А. Метод количественного определения сходства графов на основе структурных спектров. Известия АН СССР, сер. Техническая кибернетика. N5, 1994. - С.143-160. 15. Гэри М, Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982. - 416 с. 16. Кохов В.А., Ткаченко С.В. Программная система для исследования вычислительной сложности реше ния задач на графовых моделях. // Программные продукты и системы. N4, 2009. С. 137-140. 17. Незнанов А.А., Кохов В.А. Программный комплекс анализа структурного сходства систем с учетом расположения фрагментов. // Программные продукты и системы. N4, 2009. С. 147-150. БИЗНЕС-ИНФОРМАТИКА №1(15)Ц2011 г.