Реферат: Под живучестью нечеткого графа понимается его чувствительность к повреждениям с точки зрения удаления некоторых ребер или вершин [1]

УДК 004.896(06) Интеллектуальные системы и технологии


Д.Н. ЯСТРЕБИНСКАЯ

Таганрогский технологический институт Южного федерального университета


АЛГОРИТМ НАХОЖДЕНИЯ СТЕПЕНИ ЖИВУЧЕСТИ НЕЧЕТКОГО ГРАФА ВТОРОГО РОДА


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


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

Рассмотрим алгоритм нахождения степени живучести нечеткого графа второго рода . Пусть нечеткий граф задан в виде - матрицы , где -матрица смежности вершин нечеткого графа, -диагональная матрица, у которой элементами главной диагонали являются значения функции принадлежности для вершин нечеткого графа.

Введем в рассмотрение четыре вектора-столбца и четыре вектора-строки размерностью (n´1) и (1´n) соответственно: вектор-столбец L – длина пути (количество ребер) от первой до рассматриваемой вершины; вектор-столбец предшествующих вершин Xpred; вектор-столбец транзитивного замыкания ; вектор-столбец просмотренных вершин ; вектор-строка – длина пути (количество ребер) от рассматриваемой до первой вершины; вектор-строка предшествующих вершин ; вектор-строка обратного транзитивного замыкания ; вектор-строка просмотренных вершин . Тогда алгоритм будет иметь следующий вид:

Шаг 1. Положить для всех , : , ,, ,, , , .

Шаг 2. Положить (число ребер в нечетком пути от до); (степень достижимости от до ) и перейти к шагу 3.

Шаг 3. Если для всех ,выполняется неравенство , то положить , иначе . При этом , , и (т.е. вершина xi просмотрена).

Шаг 4. Определить такую вершину xk графа , для которой выполняется условие: (т.е. транзитивное замыкание вершины больше чем у всех остальных не просмотренных вершин).

Шаг 5. Если такая вершина xk существует, то полагаем i=k и возвращаемся к шагу 3, иначе переходим к шагу 6.

Шаг 6. Положить (число ребер в нечетком пути от до); (степень достижимости от до ) и перейти к шагу 3.

Шаг 7. Если для всех , выполняется неравенство , то положить , иначе . При этом , , и (т.е. вершина xi просмотрена).

Шаг 8. Определить такую вершину xk графа , для которой выполняется условие (обратное транзитивное замыкание вершины больше чем у всех остальных не просмотренных вершин). Если же , то до перехода к шагу 7, присвоить значение .

Шаг 9. Если такая вершина xk существует, то полагаем i=k и возвращаемся к шагу 7, иначе переходим к шагу 10.

Шаг 10. Определить степень живучести нечеткого графа : .


Список литературы


Фрэнк Г., Фриш И. Сети, связь и потоки.- М.: Связь, 1978, С. 280-411.

Боженюк А.В., Розенберг И.Н., Старостина Т.А. Анализ и исследование потоков и живучести в транспортных сетях при нечетких данных.- М.: Научный мир, 2006, С. 70-102.




ISBN 978-5-7262-0883-1. НАУЧНАЯ СЕССИЯ МИФИ-2008. Том 10