ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ == И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 681.51
ОЦЕНКА ИЗОМОРФИЗМА НЕЧЕТКИХ ГРАФОВ НА ОСНОВЕ НЕЧЕТКИХ ИНВАРИАНТОВ
© 2005 г. Л.С. Берштейн1, A.B. Боженюк1
В данной статье рассматриваются вопросы оценки степени изоморфизма нечетких графов. Определения и свойства нечетких инвариантов нечетких графов также представлены в данной статье. Приведен пример оценки степени изоморфизма нечетких графов на основе оценки их инвариантов.
Одной из важных проблем теории графов является распознавание изоморфизма, или эквивалентности двух графов. Она состоит в том, чтобы между множествами вершин заданных графов определить существование взаимно-однозначного соответствия, сохраняющего отношение смежности вершин [1]. В случае нечетких графов понятие изоморфизма является нечетким.
Рассмотрим нечеткие ориентированные графы [2] Gx = (X, Üx) и ÓY= (X, ÜY), где X и Y -множества вершин, a Üx=\<\jLx(xn х])/{х1, х;)> >|(*,., х})еX2}, ÜY = {< iiY(y¡, y.)/(y¡, y¡)> >|(y¿, yj) e F21 - нечеткие множества ребер с
функциями принадлежности соответственно, Рх : X2 [ОД] и : Y1 -» [ОД]. Пусть число вершин в графах совпадают, т.е. 1X1 = 1У1 = п. В работе [3] рассматривалось понятие степени нечеткого изоморфизма нечетких графов в виде / =
= &_ & ÍM*¿> *,■)<"» Mtt» У,)) и решалась
1=1, п ;'=1, и 4 '
задача нахождения (или доказательства его отсутствия) такого взаимно-однозначного соответствия F : X -*• Y, при котором величина/достигала некоторого, заранее заданного значения/0 Е Е [ОД]. Здесь под & подразумевается операция минимум, а эквивалентность определяется как Ь = = (а -» b) & (Ь -* а), где -» - операция нечеткой импликации, в частности, определяемая в логике Лукасевича (а -» Ъ) -» = min{l,l - {а + Ь)).
Нечеткие графы являются обобщением четких графов, которые в свою очередь можно рас-
1 Таганрогский государственный радиотехнический уни-
верситет, г. Таганрог.
сматривать как квазинечеткие, у которых функции принадлежности принимают два значения: 0 и 1 и, следовательно, значение изоморфизма / Е Е {ОД}. Если/= 1, то четкие графы изоморфны, если / = 0, то нет. Четкие графы характеризуются инвариантами, такими как числа внутренней и внешней устойчивости, хроматическое число и пр. [1]. Если четкие графы изоморфны (/= 1), то их инварианты совпадают. Если те или иные инварианты рассматриваемых графов совпадают, то это не значит, что графы изоморфны. В этом смысле совпадение инвариантов является необходимым, но не достаточным условием изоморфизма четких графов. Если инварианты не совпадают, то рассматриваемые графы не являются изоморфными. При рассмотрении нечетких графов их инварианты также являются нечеткими величинами. В связи с этим возникает задача оценки влияния нечетких инвариантов на величину возможного изоморфизма/рассматриваемых нечетких графов.
В данной работе рассматривается взаимосвязь между возможной степенью изоморфизма нечетких графов и их нечеткими инвариантами.
Рассмотрим произвольный подграф
СХк = (Хк, 0Хк) нечеткого графа 6Х = (X, 0Х)
на к вершин (к = 1, п ).
Степенью внутренней устойчивости аХк е [0,1]
подграфа (¡х называется величина, определяемая как ах = 1- тах ^1х(х¡, хЛ.
к х,,х^Хк
Подмножество XkQX называется максимальным нечетким внутренне устойчивым множеством со степенью внутренней устойчивости а^, если
справедливо неравенство (УХ' ~лХк) (ах, < а!Хк).
Пусть хк- j^Y^ , ■■■, XKi | - семейство максимальных нечетких внутренне устойчивых к вершинных множеств со степенями внутренней устойчивости а0,, а0,,...,а0, соответственно. Х1 Х1 Х1
Обозначим через а™ах = max-J а0,, а°2,..., а0, к
к х к хк хк J
Если семейство хк = 0, то положим а™ах = а™^ . Величина а™ах означает, что в графе
Gx = (X, Uх) существует подграф на к вершин со степенью внутренней устойчивости ах™ и не существует никакого другого подграфа с к вершинами, чья степень внутренней устойчивости была
бы больше величины а уах.
лк
Множество Äx={<a™x/l), <«""/2,..., < ах™/п)} называется нечетким множеством внутренней устойчивости нечеткого графа Gx.
Свойство 1. Для нечеткого множества внутренней устойчивости справедливо неравенство:
1 > аГ ^ атах >... > аТх ^ О-
Величина а™3* равна 1, если в графе существует хотя бы одна вершина без петли, а величина а у" равна 0, если в графе существует хотя бы
одно ребро со степенью 1.
Степенью внешней устойчивости ß^ е[0Д]
подграфа GXk называется величина, определяемая как ß^ = min max |ix(Xj, x,).
* V*jeX\Xk VXjeXk
Подмножество ХкСХ является минимальным нечетким внешне устойчивым множеством со степенью внешней устойчивости $хк, если справедливо неравенство (\/Xr с Хк)($х, < ).
Обозначим через РГ= max jß°,, ß°,,..., ß°, j,
где ß0,, ß°2,...,ß0/ - степени внешней устойчи-Xk Xk Xk
вости минимальных нечетких внешне устойчивых множеств XKi, XK2,...,XKi, имеющих ровно к
элементов. Величина ß™ax означает, что в графе
Gx = (X, Uх) существует подграф на к вершин со
степенью внешней устойчивости ß™n и не существует никакого другого подграфа с к вершинами,
чья степень внутренней устойчивости была бы больше величины (3™п.
Множество tx = {<P™x/l>, <Р™х/2,..., <Р™х/и)} называется нечетким множеством внешней устойчивости нечеткого графа Gx.
Свойство 2. Для нечеткого множества внешней устойчивости справедливо неравенство
0 < < р™х <... < р™ах = 1.
Подмножество вершин X' С X называется
нечеткой кликой со степенью = mm, max (М^, *y)vM*,> *,.)).
vXj 6 л чХ j €л Xj*Xt
Подмножество вершин X' С X является максимальной кликой со степенью е [0,1], если справедливо выражение (W'c Х)(Х"^>Х'—> 8х,<дх.),
иначе говоря, если любое подмножество X", включающее в себя подмножество X', является кликой со степенью меньшей величины 8^,.
Как и для внутренне устойчивых множеств, рассмотрим семейство всех максимальных нечетких клик хк= ХКг,..., ХК)}, содержащих ровно к вершин со степенями 5°,, 6°2,...,5°,
Хк Хк Хк
соответственно. Обозначим через 8™ах =
= тах<5°!, 8°2,..., 6°, [. Если семейство хк = 0, то
I хк хк Хк J
положим 8™ах = 8™х . Величина 8™х означает,
что в графе Gx существует ^-вершинный подграф, в котором между любыми двумя вершинами существует ребро со степенью не менее 8™ах и не существует никакого другого подграфа с к вершинами,
чья степень была бы больше величины 8уах.
лк
Множество К = {<8™x/l>, <5™х/2,..., <8™ах/я)} называется нечетким множеством
клик нечеткого графа Gx.
Свойство 3. Для нечеткого множества клик справедливо неравенство
1 = 8уах 8уах >... > 8уах = 0.
Xl Х2 х„
Величина 8™ах равна 0, если любой ^-вершинный подграф содержит хотя бы одну пару вер-
шин, например (х,-, xj), между которыми нет никакого ребра, т.е. |л(/(х„ xj) - \i,j(xr х-) = 0.
Построим дополнительный неориентированный нечеткий граф G х = (X, U'), для которого справедливо (Vx„ х; G X) (ц(/.(х,, xj) = ¡1,,-Ц, х,) = = min{ 1-ц(/(а-„ Xj), \-\iuiXj, х,)}).
Свойство 4. Семейство максимальных нечетких клик исходного графа G = (X, U) совпадает
с семейством максимальных нечетких внутренне устойчивых множеств дополнительного графа
Gx=(X, U').
Данное свойство непосредственно вытекает из определений максимальной нечеткой клики и максимального нечеткого внутренне устойчивого множества. Из свойства 4 непосредственно вытекает следующее следствие.
Следствие. Нечеткое множество клик нечеткого графа Gx = (X, Uх) совпадает с нечетким множеством внутренней устойчивости дополнительного графа Gx-(X, U').
Подмножество XkQX является нечеткой базой со степенью b G [0,1], если любая вершина х* G е Х\Хк достижима из некоторой вершины х0 G Хк со степенью b и существует вершина х' g X \ Хк, недостижимая из любой вершины х0 G Хк со степенью Ь' > Ь.
Подмножество Х™т с X является минимальной нечеткой базой со степенью Ь, если оно является минимальным в том смысле, что не существует подмножества X' С X™", обладающего таким же свойством достижимости.
Пусть хХк = {Xki, Хк2,..., Хк[} - семейство
нечетких баз, состоящих из к вершин со степенями bki, bk2,...,bkr Обозначим через Ь™х =
= max{b^, bki,...,bki}. Величина bx'" означает,
что в графе Gx=(X, Ux) существует подмножество, состоящее из к вершин, из которого достижимы все оставшиеся вершины со степенью не
менее Ьх™ и не существует подмножества, состоящего из к вершин, из которого достижимы все оставшиеся вершины со степенью более Ь™х. Если семейство хХк =0, то определим Ьх*х = Ьх^ .
Множество Вх = {(Ь™х /1), (Ь™х/2,...,
< Ь'х'х/и)] называется нечетким множеством баз
нечеткого графа С1Х.
Аналогично понятиям нечеткой базы, нечеткого множества баз рассмотрим понятия нечеткой антибазы и нечеткого множества антибаз.
Подмножество Хк С X является нечеткой антибазой со степенью Ь G [0,1], если из любой вершины х, еХ\Хк достижима некоторая вершина х0 С Хк со степенью Ь и существует вершина х*€.Х\Хк, из которой не достижима никакая вершина х0 Е Хк со степенью Ь' >Ь.
Подмножество Х™ш с X является минимальной нечеткой антибазой со степенью Ь, если оно минимально в том смысле, что не существует подмножества Гс!™, обладающего таким же свойством достижимости.
Пусть %Хк = {Х^, Хк2,...,Хк1} - семейство нечетких антибаз^ состоящих из к вершин со степенями Ьк1, Ьк2,...,Ьк1. Обозначим через
й ™х = т-лх{Ьк], Ьк ,...,Ьк}. Величина Б™™ означает, что в графе (}х = (X, 0Х) существует подмножество, состоящее из к вершин, достижимое из всех оставшихся вершин со степенью не менее ЬХкх и не существует подмножества, состоящего из к вершин, достижимого из всех оставшихся вершин со степенью более ЬХкх. Если семейство тХк = 0, то также, как и для нечетких баз, определим Ь™Х=Ь™Х.
Множество Вх = {(Ь™х /1>, (Ь™х / 2,..., (Ь™х/п)} называется нечетким множеством антибаз нечеткого графа Сгх={Х, их).
Свойство 5. Из определений нечеткого множества баз и антибаз непосредственно вытекают
неравенства: 0 * Ь™х < Ь™х <... < = 1 и 0
< ЬГХ<ЬГХ<...<ЬГХ= 1.
Л\ Л2 Лп
Окрасим каждую вершину х Е. X в один из к цветов (1 £ & £ л) и рассмотрим подграф
д1=(х1, и гу
Здесь X,- - подмножество вершин, окрашенных в одинаковый 1-й цвет. Тогда величина а, = = 1 - V Цс (х, у) определит степень внутренней
х,уеХ1
усто
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.