Об увеличении живучести нечетких графов

УДК 681.51

Л.С.Берштейн, А.В.Боженюк, И.Н.Розенберг ОБ УВЕЛИЧЕНИИ ЖИВУЧЕСТИ НЕЧЕТКИХ ГРАФОВ

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

В общем случае решение такой задачи сводится к большому перебору и может привести к значительным временным затратам. В данном докладе рассматривается подход к уменьшению такого перебора путем выделения компонент сильной связности нечеткого графа с необходимой степенью живучести. Пусть G = (X,Г) - нечеткий граф. Для произвольной вершины xi е X

) ад

обозначим через Г^ ) = У ГJ ^) нечеткое транзитивное замыкание и через

г0

) ад

Г- (Х! ) = и Г"ЧХ!) - обратное нечеткое транзитивное замыкание. Пусть V -

г0

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

1. Берем произвольную вершину xi е X и находим для нее нечеткое множество

С ^ ) = Г ^) пГ ^)={<а^ /xJ >}. Далее, находим подмножество вершин

Y1 = {хк} , для которых соответствующие функции принадлежности ак > V ,

мы тем самым определяем семейство максимальных нечетких подграфов {&^} со степенью связности а j.

2. Исключаем из графа О подмножество вершин Y1. Получаем подграф G' = (X', Г) где Х' = Х/71. Опять выбираем произвольную вершину х' е X' и действуем аналогично.

3. Продолжаем процесс до тех пор, пока это возможно, то есть, пока подмножество вершин X' не окажется пустым.

Построим нечеткий граф GY = (Y, Г'), у которого вершины у=У соответствуют выделенным максимальным нечетким подграфам {У}, а ребра соединяют соответствующие вершины, если в исходном графе существует ребро между вершинами, входящими в соответствующие компоненты связности с заданным значением функции принадлежности.

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