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

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

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

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

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

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

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

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

Нечеткий граф = ( , ) является нечетким неориентированным графом второго вида, если = {<_x(x)/x>}, x  А, | | = n, = {<_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, запишется следующим образом:

		x1	x2	x3	x4	x5
Rx1 =	x1	0,3	0,7	0	0	1	.
	x2	0,7	0	0	0,6	0,4
	x3	0	0	0,8	0,9	0
	x4	0	0,6	0.9	0	0
	x5	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/(х₃, х₃)>}.