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

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

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

Нечеткий ориентированный граф первого рода можно также удобно задавать в виде = (Х, ), где X = {x_i}, i  I = {1, 2, ..., n}, а - нечеткое многозначное отображение множества вершин X в себя, т.е. : X → X, задаваемое в виде системы нечетких образов элементов x  X при этом отображении, т.е. (x_i) = {<_Г (x_j)/x_j>}, x_j  Г(x_i), здесь Г(x_i) - четкое множество образов вершины x_i  X.

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

Нечетким ориентированным графом второго вида называется граф = ( , ), где – множество вершин является нечетким множеством в некотором универсальном множестве А, т.е. = {<_x(x)/x>}, x  А, | | = n, – нечеткое множество ориентированных ребер определяется как = {<_U<х_i, х_k>/<х_i, х_k>>}, <х_i, х_k>  X², где X – носитель множества .

Нечеткий ориентированный граф второго вида = ( , ) при необходимости можно однозначно преобразовать в нечеткий ориентированный граф первого вида G' = (X, ') следующим образом. В качестве множества вершин X принимается носитель множества , а нечеткое множество ориентированных ребер ' принимает вид: ' = {<_U'<х_i, х_k>/<х_i, х_k>>}, <х_i, х_k>  X², где функция _U'<х_i, х_k> = _U<х_i, х_k> & _X(х_i) & _X(х_k), в минимаксном базисе – _U'<х_i, х_k> = min(_U<х_i, х_k>, _X(х_i), _X(х_k)), и в вероятностном базисе – _U'<х_i, х_k> = _U<х_i, х_k>  _X(х_i)  _X(х_k). Графы и G' будем называть сопряженными.

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

Аналогичные преобразования можно выполнить и для преобразования нечеткого неориентированного графа второго вида к нечеткому неориентированному графу первого вида.

Примеры решения задач

Пример 1. Пусть задан орграф D, изображенный на рис. 17.21, а. Построить основание, матрицу смежности и матрицу инцидентности заданного графа.

Рис. 17.21, а. Ориентированный граф D

Решение: основание исходного графа D, полученное путем замены дуг соответствующими им ребрами, показано на рис. 17.21, б.

Рис. 17.21, б. Основание графа D

Матрица смежности исходного графа D будет иметь следующий вид:

		1	2	3	4	5	6	+(xj)	.
R(D) =	1	0	0	0	0	0	1	1
	2	1	0	1	1	0	0	3
	3	0	0	0		0	1	1
	4	0	0	0	0	1	1	2
	5	1	0	0	1	0	0	2
	6	1	0	0	0	0	0	1
	–(xj)	3	0	1	2	1	3

Таким образом, для вершины x₁, например, полустепень исхода ⁺(x₁) равна единице, а полустепень захода ^–(x₁) равна трем.

Матрица инцидентности для того же графа запишется следующим образом:

		u1	u2	u3	u4	u5	u6	u7	u8	u9	u10
I(D) =	х1	– 1	– 1	+ 1	– 1	0	0	0	0	0	0	.
	x2	+ 1	0	0	0	+ 1	+ 1	0	0	0	0
	х3	0	0	0	0	– 1	0	+ 1	0	0	0
	x4	0	0	0	0	0	0	0	+ 1	+ 1	– 1
	x5	0	+ 1	0	0	0	0	0	0	– 1	+ 1
	x6	0	0	– 1	+ 1	0	0	– 1	– 1	0	0

Пример 2. Пусть задан ориентированный граф D = (X, U) (рис. 17.22). Построить дерево, используя вышеописанный алгоритм.

Рис. 17.22. Орграф D

Решение: 1. Выбираем вершину x₁. Находим смежные ей вершины и получаем подмножество X’ = {x₁, x₂, x₄, x₆}. Поскольку X’  X, переходим к пункту 2.

2. Из подмножества X’ выбираем произвольную вершину, например x₂. Находим смежные ей вершины. Это вершины x₃, x₅, x₆. Добавляем в подмножество X’ вершины x₃, x₅. Вершина х₆ уже входит в подмножество X’, поэтому дугу <x₂, x₆> мы игнорируем.

3 После выполнения пункта 2 настоящего алгоритма получим подмножество X’ = {x₁, x₂, x₃, x₄, x₅, x₆}, таким образом, условие X’ = Х, выполнено, переходим к пункту 4.

4 Построено дерево Т = {<x₁, x₂>, <x₁, x₄>, <x₁, x₆>, <x₂, x₃>, <x₂, x₅>}. Алгоритм окончен.

Ответ: Построено дерево Т (рис. 17.23.).

Рис. 17.23. Дерево T

Пример 3. Разбить граф G = (X ,U), изображенный на рис. 17.24, на максимально связные подграфы и построить его конденсацию.

Рис. 17.24. Граф G

Решение: Используем алгоритм Мальгранжа.

Выбираем произвольную вершину. Пусть это будет вершина х₁. Строим матрицу смежности заданного графа.

		1	2	3	4	5	6	7	8	9	10
R =	1		1
	2	1						1	1
	3				1
	4									1
	5										1
	6	1		1				1
	7	1								1
	8					1		1			1
	9			1
	10					1				1

По матрице смежности определяем вершины, достижимые из вершины х₁:

Г⁺(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₅, x₁₀}.

У нас осталась всего одна невыделенная вершина - это вершина х₆. Следовательно, вершина х₆ образует последнюю сильную компоненту в графе G: X₄^* = {x₆}.

Итак, мы выделили в заданном графе все возможные сильные компоненты.

Теперь строим конденсацию графа G. В качестве вершин графа конденсации выступают сильные компоненты, при этом вершины, составляющие каждую сильную компоненту, стягиваются в одну. Все ребра, соединяющие стягиваемые вершины с вершинами, принадлежащими другим сильным компонентам, сохраняются. Таким образом, мы построили конденсацию D^* (рис. 17.25) исходного графа G.

Рис. 17.25. Конденсация D*

Пример 4. Для графа D = (X, U) на рис. 17.26 определить прямое и обратное транзитивные замыкания для вершины х₇.

Решение:

Г⁺х₇ = {х₇}  Г⁺х₇  Г⁺²х₇  Г⁺³х₇;

Г⁺х₇ = {х₇, х₄, х₆};

Г⁺²х₇ = Г⁺{Г⁺х₇} = Г⁺{х₇, х₄, х₆} = {х₇, х₄, х₆, х₂, х₅};

Г⁺³х₇ = Г⁺{Г⁺²х₇} =Г⁺{х₇, х₄, х₆, х₂, х₅} = {х₇, х₆, х₄, х₅, х₁, х₂, х₃};

Г^–х₇ = {х₇}  Г^–1х₇  Г^–2х₇;

Г^–х₇ = {х₇, х₂};

Г^–2х₇ = Г^–{Г^–х₇} = {х₇, х₂, х₄};

тогда Г^–х₇ = {х₂, х₄, х₇};

а Гх₇ = {х₁, х₂, х₃, х₄, х₅, х₆, х₇} = Х.

Пример 5. Построить разбиение на основе метода Мальгранжа ориентированного графа D = (X, U), заданного матрицей смежности R.

		х1	х2	х3	х4	х5	х6	х7		Г+х1	.
R =	х1	0	0	1	0	0	0	0		0
	х2	1	0	0	0	0	0	1		–
	х3	1	0	0	0	0	0	0		1
	х4	0	1	0	1	0	0	0		–
	х5	0	0	1	0	0	1	0		–
	х6	0	0	0	0	1	0	0		–
	х7	0	0	0	1	0	1	1		–
	Г–х1	0	1	1	2	2	3	3

Решение: Столбец Г⁺х₁ строится следующим образом. В клетке столбца против стрелки х₁ ставится 0. В клетку столбца против строки х₃ ставится 1, так как строка х₁ содержит 1 на месте х₃. Строка х₃ содержит 1 только на уже отмеченном месте х₁. Тогда в оставшиеся клетки столбца Г⁺х₁ проставляются знаки «–». Числа в клетках Г⁺х₁ — это количество путей из вершины х₁ в другие вершины графа D. Тогда Г⁺х₁ = {х₁, х₃}.

Аналогично заполняются клетки строки Г^–х₁. Против столбца х₁ в клетке Г^–х₁ ставится 0. В клетках строки Г^–х₁ против х₂ и х₃ ставится 1, так как столбец имеет 1 против х₂ и х₃. В столбце х₂ имеется 1 против строки х₄, следовательно, в клетку Г^–х₁ против х₄ записывается 2. В столбце х₃ имеем единицы против строк х₁ и х₅. Строка х₁ уже рассмотрена, а в клетке Г^–х₁, расположенной против х₅, ставится 2. Далее аналогично заполняются оставшиеся клетки Г^–х₁. Тогда Г^–х₁ = {х₁, х₂, х₃, х₅, х₆, х₇}, С(х₁) = Г⁺х₁  Г^–х₁ = {х₁, х₃}. Теперь удалим из графа D вершины х₁ и х₃. Получим матрицу R' оставшегося графа D'.

		х2	х4	х5	х6	х7		Г+х2	.
R' =	х2	0	0	0	0	1		0
	х4	1	1	0	0	0		2
	х5	0	0	0	1	0		3
	х6	0	0	1	0	0		2
	х7	0	1	0	1	1		1
	Г–х2	0	1	–	–	2

Аналогично, заполняя клетки Г⁺х₂ и Г^–х₂, определяем Г⁺х₂ = {х₂, х₄, х₅, х₆, х₇}, Г^–х₂ = {х₂, х₄, х₇}. Тогда С(х₂) = Г⁺х₂  Г^–х₂ = {х₂, х₄, х₇}. Снова удалим из D' вершины х₂, х₄, х₇, получим граф D". Запишем его матрицу смежности.

		х5	х6		Г+х5	.
R'' =	х5	0	1		0
	х6	1	0		1
	Г–х5	0	1

Получим Г⁺х₅ = {х₅, х₆}, Г^–х₅ = {х₅, х₆}, C(х₅) = {х₅, х₆}. Следовательно, в результате работы алгоритма получили разложение графа на три части, показанные на рис. 17.26 штриховыми линиями.

Рис. 17.26. Разложение графа на максимально связные подграфы

Пример 6. Зададим нечеткий ориентированный граф первого рода = (X, ), где X = {х₁, х₂, х₃, х₄, х₅}, а = {<1/<х₁, х₄>>, <0,5/<х₁, х₅>>, <0,1/<х₂, х₂>>, <0,9/<х₂, х₃>>, <0,8/<х₄, х₂>>, <0,2/<х₄, х₁>>, <0,6/<х₅, х₅>>}.

Граф показан на рис. 17.28.

Рис. 17.28. Нечеткий ориентированный граф первого рода

Пример 7. Зададим нечеткий граф из примера 1 в виде = (Х, ).

Решение: Получим X = {х₁, х₂, х₃, х₄, х₅}, (x₁) = {<1/х₄>,<0,5/х₅>}, (x₂) = {<0,1/х₂>,<0,9/х₃>}, (x₃) = , (x₄) = {<0,2/x₁>, <0,8/х₂>}, (x₅) = {<0,6/х₅>}.

Пример 8. Записать матрицу смежности R_x² графа, рассмотренного в примере 1.

Решение: Матрица смежности запишется следующим образом:

		x1	x2	x3	x4	x5
Rx2 =	x1	0	0	0	1	0,5	.
	x2	0	0,1	0,9	0	0
	x3	0	0	0	0	0
	x4	0,2	0,8	0	0	0
	x5	0	0	0	0	0,6

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

Решение: Граф = ( , ) приведен на рис.17.29.

Рис. 17.29. Нечеткий ориентированный граф второго вида = ( , )