Итак, семантическую сеть можно представить в виде ориентированного графа G без контуров с весами на вершинах. Каждый орграф можно разбить на полупути-фрагменты, длина которых не превышает числа, заданного исследователем. На основании вложения этих фрагментов в орграф можно подсчитать индекс сложности орграфа, вектор-индекс сложности и полный структурный спектр. Ниже представлена формализация задачи определения сходства структур на основе их сложности.

Определим понятия пути и полупути. Знаковые графы и орграфы и их применение при моделировании и анализе сложных проблем в экологии, психологии и политике;

http: //www.allmath.ru/highermath/algebra/diskret-dubna/Ll10_11.html Под путем в ориентированном графе G = (V, E) понимается последовательность вершин и дуг v₁, e₁, v₂, e₂,., v_t, e_t, v_t+1, где t ? 0, причем каждая вершина v_i О V, а каждая дуга e_i О E, и e_i всегда является дугой (v_i, v_i+1). Полупуть в ориентированном графе G = (V, E) есть последовательность вершин и дуг v₁, e₁, v₂, e₂,., v_t, e_t, v_t+1, где t ? 0, причем каждая вершина v_i О V, а каждая дуга e_iО E, и e_i всегда является либо дугой (v_i, v_i+1), либо дугой (v_i+1, v_i). Важно заметить, что каждая дуга может входить в путь или полупуть не более одного раза, т.е. для любого пути или полупути любых v₁, a₁, v₂, a₂,., v_t, a_t, v_t+1, где t ? 0 и любых i, j таких, что

0 < i, j ? t, справедливо u_i ? u_j. При этом любая вершина есть путь и полупуть длины 0, а любая дуга также является и путем, и полупутем длины 1.

Пусть L обозначает множество весов для вершин и дуг ориентированного графа без контуров (ОГБК). Под ациклическим орграфом (АОГ) будем понимать орграф G= (V,E,,) без контуров, в котором: (1) V - конечное множество вершин; (2) E VЧV - множество дуг; (3) : V L есть функция соотнесения весов вершинам ОГБК; (4) : E L есть функция соотнесения весов дугам ОГБК. Джасим Малатх Рахим Разработка методов и программных средств для решения задач различения и анализа сложности ациклических структур. Автореферат диссертации к. т. н., М. МЭИ. 2010, 20 с.

Орграф G^S= (V^S,E^S,^S,^S) будем называть подграфом (порожденным подграфом) G= (V,E,,), то есть G^SG, если: (1) V^SV; (2) vV^S [ (v) =^S (v)]; (3) E^S=E (V^SЧV^S); (4) eE^S [ (e) =^S (e)].

Орграф G^P= (V^P,E^P,^P,^P) будем называть частичным орграфом G= (V,E,,), то есть G^PPG, если: (1) V^P=V; (2) vV^P [ (v) =^P (v)]; (3) E^PE; (4) eE^P [ (e) =^P (e)].

Орграф G^PS= (V^PS,E^PS,^PS,^PS) будем называть частичным подграфом орграфа G= (V,E,,), то есть G^PSG, если: (1) V^PSV; (2) vV^PS [ (v) =^PS (v)]; (3) E^PSE (V^PSЧV^PS); (4) eE^PS [ (e) = ^PS (e)].

Под изоморфизмом (GG*) двух взвешенным по вершинам и дугам орграфов G= (V,E,,) и G*= (V*,E*,*,*) будем понимать 1-1 соответствие : VV*, такое, что: (1) vV [ (v) =* ( (v))]; (2) e= (u,w) E e*= ( (u), (w)) E*, такое что [ (e) = (e*)] и e*= (u*,w*) существует дуга e= (¹ (u), ¹ (w)) E, такая что (e) =* (e*)].

Если : VV* есть изоморфизм между орграфами G и G* и G*^SG** (G*^PG**, G*^PSG**), то будем называть изоморфизмом подграфу (частичному графу, частичному подграфу) орграфа G**. Общий случай, связанный с объединением изоморфизма частичному графу и частичному подграфу будем называть изоморфизмом фрагменту и обозначать ^f.

Пусть B=<b₁, b₂,,…,b_i,…,b_k1> обозначает базис структурных дескрипторов (СД), определяющий точность характеризации ориентированного графа. Тогда под структурным спектром G в базисе СД B=<b₁, b₂,,…,b_i,…,b_k1> будем понимать запись следующего вида SS (G/B) =в₁b₁, в₂b₂, …, в_ib_i, в_k1b_k1, где в_i=1, если фрагмент b_i?B изоморфно вкладывается в G и в_i=0 в противном случае.

Пусть для орграфа G построен его полный структурный спектр (ПСС) в базисе СД: В= (b₁, b₂,., b_i,., b_k1): FSS (G/B) = (w₁b₁, w₂b₂,., w_ib_i,., w_k1b_k1), где b_i - фрагмент базиса; w_i - число канонических изоморфных вложений фрагмента b_i в G; k1 число фрагментов базиса B, относительно которого характеризуется сложность G.

Пусть HP=<HP₁, HP₂,…, HP_i,…HP_n> обозначает базис полупутей-фрагментов, где i - порядковый номер полупути. Тогда можно вычислить следующие величины и векторы значений:

SS (G/HP) - вектор значений <ss₁,…, ss_i>, где ss_i = 1, если фрагмент базиса присутствует в графе G, и 0 в противном случае.

FSS (G/HP) - вектор значений <fss₁,…, fss_i>, где fss_i показывает число вхождений фрагмента i-ого базиса полупутей в граф G.

ISC (HP_i) - величина, характеризующая сложность полупути HP_i или индекс сложности фрагмента-полупути.

Итак, пусть заданы два оргафа без контуров G₁= (V₁,E₁), G₂= (V₂,E₂). Необходимо выяснить, существует ли взаимно однозначное соответствие между множествами V_1,V_2, которое сохраняет отношение смежности, то есть G*G₂, или:

: V₁V₂ и v_i,v_jV₁ [ (v_i,v_j) E₁ ( (v_i), (v_j)) E₂], где (v_i), (v_j) V₂?

Поскольку данная задача принадлежит к классу NP Андерсон, Джеймс А., Дискретная математика и комбинаторика: Пер. с англ. - М.: Издательский дом "Вильямс", 2003. ,

Обычно полупути, содержащему только одну вершину, сопоставлен порядковый номер базиса полупути i=1, а полупути содержащему одну дугу - порядковый номер i=2. Тогда ISC (HP₁) и ISC (HP₂) - индексы сложности, соответствующие полупути вида "вершина" и вида "дуга". Они задаются исследователем, и, зная их, можно вычислить все ISC (HP_i) для i > 2. Для того, чтобы это сделать необходимо воспользоваться аналогичными характеристиками для индекса сложности в базисе путей-фрагментов. Кохов В.А., Кохов В.В., Метод решения задачи различения орграфов на основе сложности, БИЗНЕС-ИНФОРМАТИКА №1 (15) - 2011 г.

Пусть P=<P₀, P₁,…, P_i,…, P _(p-1) > обозначает базис путей-фрагментов, где P_i - путь с числом дуг i Зададим ISC (P₀) и ISC (P₁).

Тогда можно выразить ISC (P₂) = 3ISC (P₀) +2ISC (P₁).

Для i > 3 можно рекурсивно вычислить ISC (P_i) по следующей формуле:

ISC (P_i) = 2 * ISC (P_i-1) + 3 * ISC (P_i-2) + 4 * ISC (P_i-3) +. + (n+1) * ISC (P_i-n),

для всех n таких, что i - n ? 0. В целях упрощения программной реализации можно заметить, что

ISC (P_i-1) = 2 * ISC (P_i-2) + 3 * ISC (P_i-3) +. + n * ISC (P_i-n).

Тогда получаем:

ISC (P_i) = 3 * ISC (P_i-1) +

Приведем пример. Пусть задано, что ISC (P₀) = 1, ISC (P₁) = 3, тогда:

ISC (P₂) = 3 * ISC (P₀) +2 * ISC (P₁) = 9;

ISC (P₃) = 2 * ISC (P₂) + 3 * ISC (P₁) + 4 * ISC (P₀) = 2*9 + 3*3 + 4*1 = 31;

или воспользовавшись второй формулой:

ISC (P₃) = 3 * ISC (P₂) + = 3*9 + 3 + 1 = 31;

также можно вычислить и все другие результаты:

ISC (P₄) = 3 * 31 + 9 + 3 + 1 = 106;

ISC (P₅) = 3 * 106 + 31 + 9 + 3 + 1 = 362;

Рис.2.1 Вложенность фрагментов-путей в путь длины 4.

Теперь можем вернуться к базису полупутей. Для вычисления индекса сложности полупути необходимо подсчитать сумму индексов сложности входящих в него путей. Таким образом, для произвольного полупути длины n необходимо найти все входящие в него пути длины от 0 до n. Математическая постановка задачи не предполагает решения в виде конкретной формулы, а программная реализация будет предложена в работе позже.

Рис.2.2 Вычисление индекса сложности полупути на 8 вершинах.

Заметим, что нам неважно направление пути, а важна только его длина. Таким образом, можно задать максимальную длину полупути l и вычислить для всех полупутей длины от 0 до l включительно соответствующие индексы сложности. Стоит сказать, что с ростом l число различных полупутей увеличивается экспоненциально. Если l нечетно, то число неповторяющихся полупутей длины l будет 2^l-1. Если же l четно, то это будет число, несколько превосходящее 2^l-1, но сравнительно малое по сравнению с этой величиной. (Эксперименты показали, что эта величина составляет 2^{l/2 - 1}) Это происходит из-за того, что для каждого полупути нечетной длины существует симметричный ему полупуть. Симметричность в данном случае означает, что если этот полупуть перевернуть и каждую дугу поменять на дугу с противоположным направлением, то получим ровно тот же полупуть. Однако для l четной длины существует некоторое количество полупутей, симметричные которым представляют собой эти же самые полупути. На основании сделанного предположения о числе "дополнительных" по отношению к количеству 2^l-1 полупутей, можно утверждать, что число таких полупутей, для которых симметричные им полупути отсутствуют, составляет величину 2^l/2.

Рис.2.3 Базис полупутей длины l=3. Рис.2.4 Базис полупутей длины l=2.

Зная число изоморфных вложений каждого из полупутей в орграфе, можно подсчитать вектор индексов сложности полупутей. То есть количество вхождений каждого из фрагментов в орграф умножить на соответствующий ему индекс сложности в базисе полупутей. Имея вектор частоты вхождений соответствующих фрагментов в орграф FSS и вектор - индекс сложности V_ISC (HP), проведем их покоординатное умножение. Полученный вектор есть вектор индексов сложности полупутей V_ISC (G/HP). Сложив все координаты полученного вектора V_ISC (G/HP), получим ISC (G/HP) - индекс сложности орграфа G.

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

2.3 Метод решения задач различения и определения сходства семантических сетей на основе индексов сложности