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

Вид материала

Документы

Подобный материал:

• Лекция №19, 121.08kb.
• Анализ связи между курсовой политикой ЦБ и процентными ставками, 158.63kb.
• Понятие финансового менеджмента, его цели и задачи (вопрос, 438.51kb.
• Книга искусство сновидения, 11021.17kb.
• Книга искусство сновидения, 11028.86kb.
• Книга искусство сновидения, 9655.85kb.
• Реферат проблемы социализации подростков, 413.36kb.
• Научный к п. н. Орловский, 256.75kb.
• Вопросы к экзамену, 14.82kb.
• Пояснительная записка к курсовой работе на тему: "Разработка алгоритмов и программ, 280.45kb.

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

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


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


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


Под живучестью нечеткого графа понимается его чувствительность к повреждениям с точки зрения удаления некоторых ребер или вершин [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. Определить степень живучести нечеткого графа : .


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

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