Journal influence
Bookmark
Next issue
Abstract:
Аннотация:
Authors: () - , () - | |
Ключевое слово: |
|
Page views: 12663 |
Print version Full issue in PDF (1.30Mb) |
Одной из важных проблем теории графов является распознавание изоморфизма, или эквивалентности двух графов. Задача состоит в том, чтобы между множествами вершин заданных графов определить существование взаимно однозначного соответствия, сохраняющего отношение смежности вершин [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. |
Permanent link: http://swsys.ru/index.php?page=article&id=714&lang=&lang=en |
Print version Full issue in PDF (1.30Mb) |
The article was published in issue no. № 1, 2002 |
Perhaps, you might be interested in the following articles of similar topics:
- Эвристические и точные методы программной конвейеризации циклов
- Инженерная программа трехмерного моделирования магнитных систем LittleMag
- О программной реализации геоинформационных систем
- Компьютерный тренажер для операторов технологических процессов доменного производства
- Системное тестирование программных изделий
Back to the list of articles