Нечеткие неориентированные графы

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

Граф G = (X, U) называется нечетким, если для каждой вершины x_i Î X множество U является нечетким множеством. Множество U характеризуется функцией принадлежности m _u, принимающей значения из отрезка [0, 1]. Значение m (u) показывает степень принадлежности ребра u к множеству U. Очевидно, что если m _u (х) для любых х, у Î Х принимает значение 0 или 1, то нечеткий граф G становится обыкновенным.

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

Нечетким неориентированным графом первого рода называется и через  = (X, ) обозначается пара множеств, у которого X = { x_i }, i Î I = {1, 2,..., n } – четкое множество вершин, а  = {< m _U(х _i, х _k)/(х _i, х _k)>} – нечеткое множество ребер, где х _i, х _k Î Х, m _U(х _i, х _k) – значение функции принадлежности m _U для ребра (х _i, х _k).

Как четкие, так и нечеткие неориентированные графы удобно задавать в виде нечетких матриц смежности R _x = || r_ik || _n, где r_ik = m _U(х _i, х _k).

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

Дадим определение нечеткого неориентированного графа второго вида. Пусть имеется некоторое универсальное множество А и задано нечеткое множество  в А, имеющее вид  = {< m _x (x)/ x >}, x Î А.

Нечеткий граф  = (, ) является нечетким неориентированным графом второго вида, если  = {< m _x (x)/ x >}, x Î А, | | = n,  = {< m _U(х _i, х _k)/(х _i, х _k)>}, х _i, х _k Î X, где X – носитель множества .

Примеры РЕШЕНИЯ ЗАДАЧ

Пример 1. Для графа, показанного на рис. 15.15, записать множества ориентированных и неориентированных ребер и дуг.

Рис. 15нка 1.15, граф содержит 8 вершин и 15 ребер: |X| = 8; |U| =15,тогда множество реберU =  È  Ç  включает в себя следующие подмножества:  = { u ₁, u ₄, u ₆, u ₁₀, u ₁₂, u ₁₄};  = { u ₂, u ₃, u ₅, u ₇, u ₉, u ₁₃};  = { u ₈, u ₁₁, u ₁₅}.

Пример 2. Привести пример мультиграфа с мультичислом, равным 4.

Ответ: Мультиграф, удовлетворяющий заданным требованиям, приведен на рис. 15.16.

Рис. 15.16. Искомый мультиграф

Пример 3. Пусть граф G = (X, U) (рис. 15.17)задан графическим способом. Задать тот же граф аналитическим и матричным способом.

Рис. 15.17. Граф G

Решение: Граф, заданный на рис. 15.17, можно задать аналитическим способом следующим образом: |X| = 7; X = { x ₁, x ₂, x ₃, x ₄, x ₅, x ₆, x ₇}; Г = {Г x ₁, Г x ₂, Г x ₃, Г x ₄, Г x ₅, Г x ₆, Г x ₇}; Г x ₁ = { x ₂, x ₃, x ₄, x ₅, x ₇}; Г x ₂ = { x ₁, x ₃, x ₄, x ₅, x ₆, x ₇}; Г x ₃ = { x ₁, x ₂, x ₅, x ₆, x ₇}; Г x ₄ = { x ₁, x ₂}; Г x ₅ = { x ₁, x ₂, x ₃, x ₆}; Г x ₆ = { x ₂, x ₃, x ₅}; Г x ₇ = { x ₁, x ₂, x ₃}.

Очевидно, что такой способ задания содержит слишком много избыточной информации. Для устранения этого недостатка достаточно использовать Г x_{n -1} ─ образ и не включать в Г x_{i -1}элементы х _i,определяющие Г x_i.

Тогда получим: Г x ₁ = { x ₂, x ₃, x ₄, x ₅, x ₇}; Г x ₂ = { x ₃, x ₄, x ₅, x ₆, x ₇}; Г x ₃ = { x ₅, x ₆, x ₇}; Г x ₄ = Æ; Г x ₅ = { x ₆}; Г x ₆ = Æ; Г x ₇ = Æ.

Граф, изображенный на рис. 15.17, можно задать также в виде специальной матрицы (матрицы смежности).

.

При этом для задания неориентированного графа вполне достаточно треугольной матрицы типа R’:

.

Для любого графа, в том числе заданного на рис. 15.17, можно задать еще одну специальную матрицу ─ матрицу инцидентности. Любой элемент i_pq матрицы инцидентности будет равен 1, в случае если p -я вершина в исходном графе инцидентна q -му ребру. Таким образом, матрица инцидентности для графа, заданного на рис. 15.17, примет следующий вид:

.

Пример 4. Привести примеры подграфа, суграфа и дополнения до полного для графа, заданного на рис. 15.17.

На рис.15.18. изображен подграф G’ графа G, полученный удалением из графа G вершин x ₂, x ₃ и инцидентных им ребер.

На рис.15.19. изображен граф G’ = (X’, U’), являющийся суграфом графа G: |X’| = 7, |U’| = 8.

На рис.15.20. изображен граф  = K \ G являющийся дополнением до полного графа G.

Рис. 15.18. Подграф графа G

Рис.15.19. Суграф графа G

Рис.15.20. Дополнение графа G

Пример 5. Для графа G, заданного на рис. 15.21 а), построить двойственный ему граф G_S.

Рис. 15.21. а) Пример графа G

Решение: Зададим смежностный (двойственный) граф G_S = (U, V) для графа G = (X, U). Для построения G_S по G на каждом ребре u_i Î U графа G выбирают среднюю точку и считают ее вершиной u_i Î U графа G_S. Граф G содержит 8 ребер, следовательно, двойственный ему граф Gs будет иметь 8 вершин.

Затем пару (u_i, u_j) соединяем ребром v_k = (u_i, u_j), если ребра u_i, u_j имеют общую вершину в G. То есть для графа G_S вершина u _1, например, будет иметь общие ребра с вершинами u ₂, u ₃, u ₄, u ₇, u ₈, так как эти ребра в исходном графе G имели общие вершины (x ₁ и x ₃). Далее продолжаем строить ребра для других вершин графа Gs.

Ответ: В результате получим следующий двойственный граф G_S (рис 15.21 б).

Рис. 15.21. б) Двойственный граф G_S

Пример 6. Задать нечеткий граф  = (X, ), у которого X = { х ₁, х ₂, х ₃, х ₄, х ₅}, a  = {<0,3/(х ₁, х ₁)>, <0,7/(х ₁, х ₂)>, <1/(х ₁, х ₅)>, <0,6/(х ₂, х ₄)>, <0,4/(х ₂, х ₅)>, <0,9/(х ₃, х ₄)>, <0,8/(х ₃, х ₃)>}.

Решение: Граф  показан на рис. 15.22.

Рис. 1522. Нечеткий граф

Пример 7. Записать матрицу смежности нечеткого неориентированного графа  = (X, ), заданного в примере 1.

Решение: Матрица смежности R _x ¹ нечеткого неориентированного графа , рассмотренного в примере 1, запишется следующим образом:

 

		x 1	x 2	x 3	x 4	x 5
R x 1 =	x 1	0,3	0,7	0	0	1	.
	x 2	0,7	0	0	0,6	0,4
	x 3	0	0	0,8	0,9	0
	x 4	0	0,6	0.9	0	0
	x 5	1	0,4	0	0	0

 

Пример 8. Записать нечеткий неориентированный граф второго вида.

Решение: Зададим нечеткий неорграф второго вида  = (, ), у которого  = {<1/ x ₁>,<0,4/ x ₂>,<0,7/ х ₃>,<0,5/ x ₄>, <0,9/ х ₅>},  = {<0,3/(х ₁, х ₁)>, <0,7/(х ₁, х ₂)>, <1/(х ₁, х ₅)>, <0,6/(х ₂, х ₄)>.<0,4/(х ₂, х ₅)>, <0,9/(х ₃, х ₄)>, <0,8/(х ₃, х ₃)>}.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Что такое граф? Приведите пример. Назовите известные вам типы графов.

2. В чем состоит различие между ориентированными и неориентированными графами?

3. Опишите известные вам способы задания графов.

4. Что называется подграфом и суграфом графа?

5. Что называется дополнением графа?

6. Какой граф называется двойственным?

7. Какие операции могут выполняться над графами?

8. Что такое мультиграф и как определяется его мультичисло?

9. Дайте определение регулярного графа.

10. Дайте определение нечеткого графа. В чем состоит отличие нечеткого неориентированного графа первого и второго рода?