Программные продукты и системы

Одной из важных проблем теории графов является распознавание изоморфизма, или эквивалентности двух графов. Задача состоит в том, чтобы между множествами вершин заданных графов определить существование взаимно однозначного соответствия, сохраняющего отношение смежности вершин [1]. В случае нечетких графов понятие изоморфизма является нечетким.

Рассмотрим нечеткие ориентированные графы [2]  и , где X и Y – множества вершин, а   – нечеткие множества ребер с функциями принадлежности соответственно,  и . Пусть число вершин в графах совпадает, то есть .

В работе [3] рассматривалось понятие нечет- кого изоморфизма нечетких графов в виде  и решалась задача нахождения (или доказательства его отсутствия) такого взаимно однозначного соответствия , при котором величина f достигала некоторого заранее заданного значения . Здесь под  подразумевается операция минимум, а эквивалентность определяется как , где  – операция нечеткой импликации, в частности, определяемая в логике Лукасевича (a®b=min{1,1–a+b}).

Нечеткие графы являются обобщением четких графов, которые, в свою очередь, можно рассматривать как квазинечеткие, у которых функции принадлежности принимают два значения – 0 и 1 и, следовательно, значение изоморфизма fÎ{0,1}. Если f=1, то четкие графы изоморфны, если f=0, то нет. Четкие графы характеризуются инвариантами, такими как числа внутренней и внешней устойчивости, хроматическое число и пр. [1]. Если четкие графы изоморфны (f=1), то их инварианты совпадают. Если те или иные инварианты рассматриваемых графов совпадают, то это не значит, что графы изоморфны. В этом смысле совпадение инвариантов является необходимым, но не достаточным условием изоморфизма четких графов. Если инварианты не совпадают, то рассматриваемые графы не являются изоморф- ными.

При рассмотрении нечетких графов их инварианты также являются нечеткими величинами. В связи с этим возникает задача оценки влияния нечетких инвариантов на величину возможного изоморфизма f рассматриваемых нечетких графов.

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

Рассмотрим произвольный подграф   нечеткого графа  на k вершин ().

Определение 1 [4]. Степенью внутренней устойчивости  подграфа  назовем величину, определяемую как  .

Определение 2 [4]. Подмножество  называется максимальным нечетким внутренне устойчивым множеством со степенью внутренней устойчивости , если справедливо неравенство .

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

Определение 3. Множество   назовем нечетким множеством внутренней устойчивости нечеткого графа .

Свойство 1. Из определения 3 непосредственно вытекает неравенство:

.

Заметим, что величина  равна 1, если в графе существует хотя бы одна вершина без петли, а величина  равна 0, если в графе существует хотя бы одно ребро со степенью 1.

Определение 4. Подмножество вершин  назовем нечеткой кликой со степенью .

Определение 5. Подмножество вершин  назовем максимальной кликой со степенью , если справедливо выражение: , иначе говоря, если любое подмножество  включающее в себя подмножество , является кликой со степенью меньшей величины .

Как и для внутренне устойчивых множеств, рассмотрим семейство всех максимальных нечетких клик , содержащих ровно k вершин со степенями  соответственно. Обозначим через . Если семейство , то положим . Величина  означает, что в графе  существует k-вершинный подграф, в котором между любыми двумя вершинами существует ребро со степенью не менее  и не существует никакого другого подграфа с k вершинами, чья степень была бы больше величины .

Определение 6. Множество   назовем нечетким множеством клик нечеткого графа .

Свойство 2. Из определения 6 непосредственно вытекает неравенство:

.

Величина  равна 0, если любой k-вершинный подграф содержит хотя бы одну пару вершин, например , между которыми нет никакого ребра, то есть .

Построим дополнительный неориентирован- ный нечеткий граф , для которого справедливо:  .

Свойство 3. Семейство максимальных нечетких клик исходного графа  совпадает с семейством максимальных нечетких внутренне устойчивых множеств дополнительного графа  .

Данное свойство непосредственно вытекает из определений максимальной нечеткой клики и максимального нечеткого внутренне устойчивого множества. Из свойства 3 непосредственно вытекает следующее следствие: нечеткое множество клик нечеткого графа  совпадает с нечетким множеством внутренней устойчивости дополнительного графа .

Рассмотрим теперь некоторое взаимно однозначное соответствие  между множествами вершин X и Y, в результате которого нечеткие графы и изоморфны со степенью f. Пусть  – произвольный нечеткий подграф на k вершин. Обозначим через  нечеткий подграф графа , вершины которого  соответствуют вершинам  подграфа . Обозначим через fk степень изоморфизма нечетких подграфов  и .

Свойство 4. Справедливо выражение .

Доказательство. Перенумеруем вершины множеств X и Y следующим образом: присвоим номера 1,2,…,k вершинам, входящим в подмножества  и , а номера k+1,k+2,…,n – оставшимся вершинам из подмножеств  и . Тогда степень изоморфизма можно записать в виде:

Рис. 2

Свойство 4 доказано.

Свойство 5. Пусть  и  – степени внутренней устойчивости подграфов  и  соответственно. Тогда справедливо выражение:

                              (1)

Доказательство. Если  и  – степени внутренней устойчивости, тогда в подграфе  существует пара вершин , для которой справедливо , а в подграфе  существует пара вершин , для которых  (рис.1). Рассмотрим два взаимоисключающих случая.

Случай 1. Вершине  соответствует вершина , а вершине  соответствует вершина , то есть выполняются равенства  и . Тогда величина  оценится как  .

Случай 2. Вершине  соответствует вершина , а вершине  соответствует вершина , то есть выполняются равенства  и . Причем значения  и (или) . Тогда справедливо неравенство , откуда следует, что величина   (рис. 2). Опять рассмотрим два взаимоисключающих случая.

Случай 2.1. Справедливо неравенство  . Тогда величина  опять оценится как:  .

Случай 2.2. Справедливо неравенство

.                                     (2)

Рассмотрим вершины , соответствующие вершинам  ( и ). Справедливо неравенство  , откуда следует справедливость условия

.                                  (3)

Выполнение неравенства (2) при условии (3) непосредственно влечет за собой справедливость условия . В этом случае величину  опять можно оценить как:

В силу произвольного значения  свойство 5 доказано.

Пусть  и  – нечеткие множества внутренней устойчивости нечетких графов  и  соответственно; f – степень изоморфизма рассматриваемых графов. Тогда справедливо следующее свойство.

Свойство 6. Справедливо неравенство .

Доказательство. Пусть  и  – некоторые подграфы со степенями внутренней устойчивости соответственно  и . Рассмотрим два случая.

Случай 1. , то есть подмножество вершин  соответствует подмножеству вершин  (рис. 3). Тогда согласно свойствам 2 и 3 можно записать .

Рис. 3

Рис. 4

Рис. 5

Случай 2.  (рис. 4). Тогда степень внутренней устойчивости  подграфа  оценится как . Рассмотрим два подслучая.

Случай 2.1. Справедливо неравенство . Тогда степень изоморфизма оценится как  .

Случай 2.2. Справедливо неравенство

.                              (4)

Рассмотрим подмножество вершин , соответствующее подмножеству вершин  (). Пусть  – степень внутренней устойчивости подмножества . Можно записать, что . Если выполняется неравенство (4), то обяза- тельно выполнится неравенство  . В этом случае степень изоморфизма оценится как .

Рассмотрев все возможные случаи, мы тем самым доказали свойство 6.

Пусть   и   – не-четкие множества клик нечетких графов  и  соответственно. Тогда справедливо следующее свойство.

Свойство 7. Справедливо неравенство .

Данное свойство доказывается аналогично свойству 6.

Пример. Рассмотрим пример оценки изоморфизма нечетких графов  и , приведенных на рисунке 5.

Нечеткие множества внутренней устойчивости и клик графов  и  определятся соответственно как

,

,

,

.

Тогда степень изоморфизма рассматриваемых графов оценится как

Таким образом, степень изоморфизма нечетких графов, приведенных на рисунке 5, не может превышать значения 0,7.

Доказанные свойства 6 и 7 позволяют по нечетким множествам внутренней устойчивости и нечетким множествам клик оценивать возможную сте- пень изоморфизма нечетких графов. Необходимо отметить, что оценка степени изоморфизма нечет- ких графов возможна и с помощью других инвари- антов.

Список литературы

1. Зыков А.А. Основы теории графов. - М.: Наука. Гл.ред.физ.-мат.лит., 1987. – 384 с.

2. Кофман А. Введение в теорию нечетких множеств. - М.: Радио и связь, 1982.

3. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных интеллектуальных системах. - Р-н-Д: Изд-во Ростовского ун-та, 1999. – 278 с.

4. Берштейн Л.С., Боженюк А.В. Определение нечетких внутренне устойчивых, внешне устойчивых множеств и ядер нечетких ориентированных графов //ТиСУ.-1999.-№1. - С.161-165.