автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Расчет вероятности связности случайного графа с применением сечений

На правах рукописи

Мигов Денис Александрович

РАСЧЕТ ВЕРОЯТНОСТИ СВЯЗНОСТИ СЛУЧАЙНОГО ГРАФА С ПРИМЕНЕНИЕМ СЕЧЕНИЙ

05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск — 2008

003450690

Работа выполнена в Институте вычислительной математики и математической геофизики СО РАН.

Научный руководитель: доктор технических наук,

доцент Родионов Алексей Сергеевич Официальные оппоненты: доктор физико-математических наук,

профессор Ерзин Адиль Ильясович

кандидат физико-математических наук, доцент Рогазинский Сергей Валентинович

Ведущая организация: Сибирский государственный университет

телекоммуникаций и информатики (г. Новосибирск)

Защита состоится 11 ноября 2008 г. в 16 часов на заседании диссертационного совета Д 003.061.02 при Институте вычислительной математики и математической геофизики СО РАН по адресу: 630090, Новосибирск, проспект Лаврентьева, 6.

С диссертацией можно ознакомиться библиотеке Института вычислительной математики и математической геофизики СО РАН.

Автореферат разослан 10 октября 2008 г.

Ученый секретарь диссертационного совета д.ф.-м.н.

С.Б. Сорокин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Так как задача точного расчета КР-трудна, ранее на практике использовали различные приближенные методы, тогда как точные методы представляли в большей степени академический интерес. Однако развитие вычислительной техники привело к возрождению интереса к использованию этих методов на практике, потому что появилась возможность за разумное время рассчитывать надежность сетей малой и средней размерности (десятки и сотни узлов). С другой стороны, проверка приближенных методов на точность их работы также вызывает необходимость дальнейшего исследования точных методов.

Цель работы — разработка методов для повышения эффективности работы точных алгоритмов расчета вероятности связности случайного графа.

Методы исследования базируются на теории графов и методах теории вероятностей.

Научная новизна работы состоит в следующем:

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

• Разработана методика получения формул с небольшим числом операций (по сравнению с известными формулами) для

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

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

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

• 9-я, 10-я, 11-я Конференции молодых ученых ИВМиМГ СО РАН. Новосибирск, 2004, 2005, 2006. Два доклада (2004, 2006) отмечены премиями.

• МНПК "Связь-2004". Международный семинар "Вычислительные методы и решение оптимизационных задач". Озеро Иссык-Куль, Кыргызская респ., 2004.

• 5-я и б-я Всероссийские конференции молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых). Новосибирск и Кемерово, 2004 и 2005. За доклад в 2004 награжден почетной грамотой.

• Всероссийская конференция по математической безопасности информационных технологий МаБИТ-04. Москва, 2004.

• 1-я, 2-я, 3-я, 4-я Азиатские международные школы-семинары по проблемам оптимизации сложных систем. Новосибирск, 2005 ,2006; озеро Иссык-Куль, 2007; респ. Алтай, 2008.

• 8-я Всероссийская конференция с участием иностранных ученых "Современные методы математического моделирования природных и антропогенных катастроф". Кемерово, 2005.

• The 2006 IFIP International Conference on Embedded And Ubiquitous Computing. Korea, 2006.

• 9-я и 10-я Международные конференции "Проблемы функционирования информационных сетей". Новосибирск, 2006, 2008.

• Международная конференция "Вычислительные и информационные технологии в науке, технике и образовании". Павлодар, Казахстан, 2006.

• Семинар "Моделирование инфо-коммуникационных систем" под руководством д.ф.-м.н. В.К. Попкова, ИВМиМГ СО РАН.

• Семинар "Дискретный анализ" под руководством к.ф.-м.н. А. А. Евдокимова и д.ф.-м.н. А. Д. Коршунова, ИМ СО РАН.

Публикации. По материалам данной работы опубликовано 15 печатных работ, список которых приведен в конце автореферата.

Структура и объем работы.

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Диссертация изложена на 97 страницах, включает библиографический список из 61 наименования работ, 23 рисунка, 8 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обсуждается актуальность темы диссертации, а также сделан обзор всех разделов диссертационной работы.

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

С ее помощью получены формулы для вероятности связности 4-х и 5-и вершинных графов. Для 4-х вершинного графа (рис. 1) формула имеет вид:

1 - Л(С?) =6а'Ь'с'(1'е'/' + а'Ь'е' + а'сИ? + У с'/' + с'с1'е'-

2{Ь'й'е'¡'{а! + с' - 0,5) + а'с'е'1'{Ъ' + сИ - 0,5)+ (1) а'Ь'с'(1'(е' + /' — О,5)).

Данная формула содержит 20 операций сложения-вычитания и 27 операций умножения, что существенно меньше чем 38 и 110 операций соответственно, которые содержатся в ранее известной формуле. Формула для 5-и вершинного графа содержит 55 операций сложения-вычитания и 96 операций умножения, поэтому здесь не приводится. Также получены формулы для вероятности связности двух и трех вершин в 4-х вершинном графе.

В Главе 2 изложены результаты автора для задачи расчета, вероятности связности всех вершин случайного графа.

У

Рис. 2: Граф с двухвершинным сечением

Подробно описывается случай, когда граф содержит двухвершинное сечение (рис. 2).

Для этого случая доказана формула:

Через Сг обозначен граф, полученный из слиянием вершин сечения. Использование формулы (2) снижает вычислительную сложность расчета вероятности связности графа с величины по-

рядка 0(2м) = 0(2М^+М*) до 0(2М1+1) + 0(2М2+1), где Мх и М2

— количество ребер в двух подграфах 0\ и на которые граф разделяется двухвершинным сечением. Также получена формула на случай, если граф разделяется двухвершинным сечением на произвольное количество подграфов. Сделано замечание, что формула (2) будет верна также для недвусвязных графов, то есть графов, связность которых равна 0 или 1.

Далее рассматриваются так называемые циклические (рис. 3) и продольные графы (рис. 4). Эти графы являются двусвязны-ми и содержат сразу группу двухвершинных сечений. Непосредственное рекурсивное применение формулы (2) к такому графу приведет к многократному пересчитыванию вероятности связности каждого подграфа, а также вероятности связности каждого подграфа, склееного по разрезающим вершинам. Предлагаемые формулы позволяют избежать этого. Формула для вероятности связности циклического графа имеет вид:

Я(0) =Л(С1)-(Л(С'2)-Д(С2)) +

ЩС2) ■ (Я(0[) - ЩОг)) + ЩС,) • Я(Сз).

(2)

Д(С) ={р[ -р1)Р2---Рк+Р1(Р2 -Р2)РЗ---Рк + ••• + р\---рк-\(р'к -Рк) +Р№---Рк,

Рис. 3: Пример циклического графа

XI Х2 Хк-2 Хк-1

У Сн Л

У1 У-' УЬ2 ук-1

Рис. 4: Продольный граф

где рг — вероятность связности подграфа 67,, р'г — вероятность связности 0'г, т.е. графа, полученного из слиянием двух вершин из рассматриваемого сечения (каждая компонента содержит ровно две такие вершины).

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

Метод с использованием двухвершинных сечений развивает-

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

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

Таким способом получены формулы в явном виде для вероятности связности графов с трехвершинным и четырехвершинным сечениями. Ниже приведена формула для трехвершинного сечения:

ЩС) + Д(^312) - Л(6?;5))+

Е{0\213){Е{в2|23) + Я^3'2) - Л((322|3))+

д(с?13|2)(д(с 22'3) + д(<^123) - д(<?23'2))-я^нд^213) + Д(с5312) + Я(С2|23)Ь (4)

.ВДХЯ^213) + Я(С}312) + Я(<^|23))+ Д((?1 )Я(С2)]+

В данной формуле принято следующие обозначение: через <?г12'3 обозначается подграф бг, стянутый по разрезающим вершинам 1 и 2; соответственно С]23 — подграф стянутый по всем разрезающим вершинам 1, 2, 3.

Формула для четырехвершинного сечения содержит 101 операцию сложения-вычитания и 16 операций умножения, поэтому здесь не приводится. При этом в случае двухвершинного сечения вероятность связности исходного графа выражается через вероятности связности 4 стянутых подграфов, в случае трехвершинного сечения эта цифра равна 10, а в случае четырехвершинного сечения — 30.

В Главе 3 изложены результаты автора для задачи расчета вероятности связности выделенного подмножества вершин случайного графа.

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

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

= ДЯ*(С2) + Д52/(Сх)^(С2) - Дяг/((?1)Д^(С2),

в)Ян(в) = Лв4(С?1) + Ян(С2) - ЯАО^Н^),

г)ЯАС) = ^(С?!)^^) - Лв4((?2)) + Яз№2).

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

Далее рассматривается случай, когда множество выделенных вершин состоит из более чем двух элементов. Существуют два варианта расположения целевых вершин в подграфах как показано на рисунке 6. В первом множество целевых вершин, попавших в (?!, будем обозначать Я, а множество вершин, попавших в С2 — Т. Во втором варианте все множество целевых вершин К находится в (7 х- Кроме этого, отдельно выделен вариант, когда 15*1 — 1; обозначим его как вариант в).

У а)

У б)

У у

а) б)

Рис. 6: Варианты расположения целевых вершин в графе Доказаны формулы

а)Як{0) = Л5и{ж}(С1) • Яти{г}(С2) + Л5и{у}((?1) • ДГиы(С2)+ Я5и{г}{0'х) ■ Лги{х>2/}(С2) + Ляи{*,„}(<?!) ■ ЯТи{,}(0'2)-■ Яти{х,у}^2) - -Й5и{;г,2/}(С!1) • Дги{х}(С2)-

п80{х,у

}(01)

6)RK(G) = Rxy(Gi) • {Rk(G'2) - RK(G2)) + Rk(G2)\ e)Rx(G) - Rsu{x}(Gi)' Rtu{x}{G2) + Rsu{y}(Gi) ■ Rru{y}{G2)+

Rsu{x,y}{Gl) • Rtu{z}{G'2)~ 2 • Rsu{x,y}(Gl) • Rru{x,y}(G2)-

Глава 4 содержит описание алгоритмов, основанных на полученных в предыдущих главах результатах, а также анализ результатов численных экспериментов. Наряду со временем расчета отслеживалось также количество рекурсий для каждого метода. Расчеты проводились на ПЭВМ с процессором AMD Athlon 3500-f, 2,2GHz, RAM: 3Gb. Экспериментально показано, что для некоторых классов графов использование полученных в диссертационной работе формул даёт существенное сокращение времени вычислений.

В таблице 1 приведены результаты экспериментов для проверки эффекта, который дает применение полученных в первой главе формул для графов малой размерности. Эксперименты проводились на полных графах Kl размерности 10,11,12. В первом столбце — показатели работы метода ветвления с продолжением рекурсий до четырехвершинных графов (алгоритм Factoring4 Old), во Втором столбце — показатели работы метода ветвления с продолжением рекурсий до четырехвершинных графов (алгоритм Factoring4) с использованием формулы (1), в третьем столбце — показатели работы метода ветвления с продолжением рекурсий до пятивершинных графов (алгоритм Factoring5) с использованием полученной формулы. Все алгоритмы усилены последовательно-параллельным преобразованием на каждом шаге и предварительным удалением "прикрепленных деревьев".

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

Таблица 1: Результаты расчетов для полных графов Kj,

L Factoring40ld Время Рекурсии Factoring4 Время Рекурсии Factoring5 Время Рекурсии

10 11 12 0,23 с 40319 2,03 с 362879 20,4 с 3628799 0,2 с 40319 2 с 362879 20,2 с 36228799 0,09 с 1349 0,76 с 120959 7,6 с 1257599

графа ускоряет процесс расчета почти в три раза.

Для метода с использованием формулы (2) были проведены эксперименты на графах, полученных объединением двух полных графов одной размерности с двумя общими вершинами. Из этих графов выкидывается ребро между общими вершинами, для того, чтобы их можно было быстрей обсчитать методом ветвления. Будем обозначать такие графы K'L, на рисунке 7 представлены графы и K'Fi. Результаты эксперимента приведены в таблице 2. В первом столбце — показатели работы метода ветвления (алгоритм Factoring), во втором столбце — показатели работы метода ветвления с предварительной проверкой каждого блока графа на наличие двухвершинного сечения и рекурсивной декомпозицией по формуле (2) в случае, если сечение есть (Алгоритмы 2Cuts). Все алгоритмы усилены последовательно-параллельным преобразованием на каждом шаге, предварительным удалением "прикрепленных деревьев" и разложением на блоки.

Для алгоритмов с использованием формулы в случае четы-рехвершинного сечения были проведены эксперименты решетках ширины 4, с длиной менялась от 7 до 11. Обозначать такие графы будем как GridA х L. Алгоритм с использованием формулы для четырехвершинного сечения обозначен как Factoring. Также рас-

Таблица 2: Результаты расчетов для графов К'ь

L Factoring 2 Cuts

Время Рекурсии Время Рекурсии

8 2 с 305487 <0,01 с 477

9 2 мин 27 с 13394427 0,01 с 3357

10 7 часов 1,7-1011 0,17 с 26877

11 — — 1,5 с 241917

12 — — 15,5 с 2419197

Таблица 3: Результаты расчетов для решеток GridA х L

L Factoring FactoringForZGut' 4Cuts

Время Рекурсии Время Рекурсии Время Рекурсии

7 0,39 с 39605 0,36 с 35189 0,06 с 961

9 22 с 2473799 17 с 1916021 0,37 с 7351

10 2 мин 50 с 19527443 2 мни 14 с 15125909 0,65 с 9271

11 22 мин 30 с 154117959 18 мин 14 с 95175949 1,5 с 57661

сматривается алгоритм Factoring For 2 Cut', суть которого заключается в нахождении четырехвершинного сечения и направленного ветвления до получения дувхвершинного сечения, для которого можно использовать формулу (2). Результаты приведены в таблице 3.

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

В заключении сформулированы результаты, выносимые автором на защиту:

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

2. Предложены методы расчета вероятности связности выделенного подмножества вершин случайного графа (для двухвершинных сечений) и вероятности связности всех его вер-

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

3. Разработан комплекс программ, реализующих предложенные алгоритмы и экспериментально показывающий их преимущество по отношению к существующим.

Публикации в журналах списка ВАК

1. Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer-Verlag LNCS, Vol. 4097, 2006. - P. 702-709.

Публикации в прочих рецензируемых журналах

2. Родионов A.C., Родионова O.K., Мигов Д.А., Мурзин М.Ю. Использование метода ветвления для точного расчёта вероятности связности случайного графа// Математика и безопасность информационных технологий. — М-.-. МГУ-МЦНМО, 2005. С. - 333-341.

3. Мигов Д.А. Расчет вероятности связности двухполюсной сети с применением двухвершинных разрезов// Труды ИВМиМГ СО РАН, Серия Информатика, 5. Мат. 1-ой Азиатской межд. школы-семинара "Проблемы оптимизации сложных систем". — Новосибирск: ИВМиМГ СО РАН, 2005. - С. 32-38.

4. Мигов Д.А. Вычисление вероятности связности подмножества узлов сети с использованием двухвершинных разрезов// Труды ИВМиМГ СО РАН, Серия Информатика, 6. Мат. 2-ой Азиатской межд. школы-семинара "Проблемы оптимизации сложных систем". — Новосибирск: ИВМиМГ СО РАН, 2006. - С. 134-138.

5. Мигов Д.А. Расчет вероятности связности случайного графа с применением сечений// Труды ИВМиМГ СО РАН, Се-

рия Информатика, 7. Мат. 3-ой Азиатской межд. школы-семинара "Проблемы оптимизации сложных систем" (Кыргызская респ., оз. Иссык-Куль). — Новосибирск: ИВМиМГ СО РАН, 2007. - С. 81-86.

Публикации в трудах конференций

6. Мигов Д. А. Использование разрезов случайного графа для вычисления вероятности его связности// Труды конф. молодых ученых ИВМиМГ СО РАН. — Новосибирск: ИВМиМГ СО РАН, 2004. - С. 133-140.

7. Мигов Д.А. Вероятность связности 5-и вершинного графа// Мат. Межд. семинара "Выч. методы и решение оптимизационных задач"(Кыргызская респ., Бишкек). — Новосибирск, 2004. - С. 113-116.

8. Мигов Д.А. Расчет вероятности связности сети с применением вершинных разрезов специального вида// Тезисы докладов V Всерос. конф. молодых ученых по мат. моделированию и инф. технологиям. — Новосибирск: ИВТ СО РАН, 2004. — С. 24-25. (Полный текст доклада на http://www.ict. nsc.ru/ws/YM2004).

9. Мигов Д.А. Расчет вероятности связности /¿"-полюсной сети с применением двухвершинных разрезов// Труды конф. молодых ученых ИВМиМГ СО РАН. — Новосибирск: ИВМиМГ СО РАН, 2005. - С. 95-101.

10. Мигов Д.А. Формулы вероятности связности к вершин для графов небольшой размерности// Тезисы Тез. докл. VI Веер, конф. молодых ученых по мат. моделированию и инф. технологиям. — Кемерово: КГУ, 2005. — С. 42. (Полный текст доклада на http://www.ict.nsc.ru/ws/YM2005).

11. Мигов Д.А. Расчет вероятности связности сети с применением продольных разрезов// Труды конф. молодых ученых ИВМиМГ СО РАН. - Новосибирск: ИВМиМГ СО РАН, 2006. - С. 144-151.

12. Мигов Д.А. Методы ускорения расчета надежности К-

полюсной сети, основанные на рассмотрении вершинных разрезов// Мат. IX межд. конф. "Проблемы функционирования информационных сетей". — Новосибирск: ИВМиМГ СО РАН, 2006. - С. 205-209.

13. Мигов Д.А. Использование вершинных разрезов для точного вычисления вероятности связности сети// Труды межд. конф. "Вычислительные и информационные технологии в науке, технике и образовании". — Казахстан, Павлодар: ПГУ, 2006. - С. 51-56.

14. Мигов Д.А. Стратегия выбора разрешающего ребра в методе ветвления и применение сечений при вычислении вероятности связности графа// Мат. 4-ой Азиатской межд. школы-семинара "Проблемы оптимизации сложных систем" (респ. Алтай), 2008. В печати.

15. Мигов Д.А. Выбор разрешающего ребра в методе ветвления и применение сечений для расчета надежности сетей// Мат. X межд. конф. "Проблемы функционирования информационных сетей". - Новосибирск: ИВМиМГ СО РАН, 2008. - С. 73-75.

Подписано в печать 08.10.2008г. Формат 60 х 841/1б- Уч.-изд. л. 1 Тираж 80 экз. Заказ № 193

ООО "Омега Принт" Новосибирск-90, пр. Лаврентьева, 6

Введение

Глава 1. Существующие методы расчета вероятности связности случайного графа и возможности их ускорения

1.1. Основные определения и обозначения.

1.2. Методы редукции.

1.3. Учет точек сочленения и мостов.

1.4. Метод ветвления (Мура-Шеннона).

1.5. Вероятность связности графов малой размерности.

1.5.1. Вероятность связности 4-х вершинного графа.

1.5.2. Вероятность связности 5-и вершинного rpacba.

1.6. Вероятность связности подмножества вершин в графах малой размерности.

1.6.1. Формула вероятности связности подмножества вершин в графе произвольной размерности.

1.6.2. Вероятность связности подмножества вершин в 4-х вершинном графе.

1.7. Прочие методы.

1.8. Выводы.

Глава 2. Использование сечений в расчете вероятности связности случайного графа 34 2.1. Расчет с использованием двухвершинных сечений.

2.1.1. Формула вероятности связности графа с двухвершинным сечением.

2.1.2. Случай недвусвязного графа.

2.1.3. Расчет вероятности связности графа с использованием формулы (2.1).

2.1.4. Обобщение на произвольное количество компонент, получаемых при удалении сечения.

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

2.2.1. Циклические графы.

2.2.2. Продольные графы.

2.3. Расчет с использованием сечений произвольной мощности

2.3.1. Обозначения и определения.

2.3.2. Вероятности отделений.

2.3.3. Формула для вероятности связности с использованием сечения

2.3.4. Случай двухвершинного сечения

2.3.5. Случай трехвершинного сечения.

2.3.6. Случай четырехвершинного сечения.

2.4. Выводы.

Глава 3. Использование сечений в расчете вероятности связности подмножества вершин случайного графа ТО

3.1. Использование двухвершинных сечений для расчета вероятности двухвершинной связности.

3.1.1. Случай разделения графа двухвершинным сечением на два подграфа

3.1.2. Случай разделения графа двухвершинным сечением на произвольное количество подграфов.

3.2. Использование двухвершинных сечений для расчета вероятности связности произвольного подмножества вершин.

3.3. Выводы.

Глава 4. Экспериментальное исследование алгоритмов

4.1. Алгоритмы с использованием формул для графов малой размерности

4.2. Алгоритмы с использованием двухвершинных сечений

4.2.1. Формулировка алгоритмов.

4.2.2. Результаты численных экспериментов

4.3. Алгоритмы с использованием трехвершинных сечений.

4.4. Алгоритмы с использованием четырехвершинных сечений

4.5. Выводы.

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

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

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

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

Данная задача является NP-трудной [35, 47], поэтому ранее на практике использовали различные приближенные методы, тогда как точные методы представляли в большей степени академический интерес. Однако развитие вычислительной техники привело к возрождению интереса к использованию этих методов на практике, так как появилась возможность за разумное время рассчитывать надежность сетей малой и средней размерности (десятки узлов). С другой стороны, проверка приближенных методов на точность их работы также вызывает необходимость дальнейшего исследования точных методов.

Вопросом вычисления или оценки различных характеристик связности подмножества узлов сетей различной природы на моделях случайных графов (особенно в частных случаях, когда это подмножество состоит из двух или из всех узлов) занимались и занимаются многие исследователи как в России, так и за рубежом. Из отечественных прежде всего надо упомянуть Артамонова Г.Т., Вишневского В.М., Егунова М.М., Епи-хина В.В., Кауля С.Б., Кельманса А.К., Литвака В.И., Ломоносова М.В., Майнагашева С.М., Нечепуренко М.И., Полесского В.П., Попкова В.К, Родионова А.С., Родионову O.K., Скоробогатова В.А., Толчана А.Я, Хар-кевича А.Д. Из зарубежных исследователей это Colbourn C.J., Moor Е., Satyanarayana A., Shennon К., Shooman A.M., Van Slyke R., Wood R.K.

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

Изложение материала организованно следующим образом:

4.5. Выводы

В главе экспериментально проверены предложенные методы. Основные выводы заключаются в следующем:

1) Полученные в первой главе формулы для графов малой размерности существенно ускрояют процесс расчета вероятности связности графа произвольной размерности методом ветвления. Так, на полных графах использование формулы (1.8) дает ускорение приблизительно в три раза по сравнению с использованием ранее известной формулы для 4-х вершинного графа из [27], и приблизительно в пять раз по сравнению с методом ветвления до 2-х вершинных графов.

2) Полученные во второй и в третьей главах формулы для вероятности связности графа с сечением из двух, трех и четырех вершин существенно сокращают время вычислений для графов, в которых такое сечение имеется. Так, решетка 4 х 11 обсчитывается предложенным методом за 1,5 секунды, а методом ветвления (усиленным всеми возможными способами) — за 22,5 минуты. При этом, если подобное сечение отсутствует, время работы предложенного метода незначительно больше времени работы алгоритма ветвления.

Заключение

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

На защиту выносятся следующие результаты.

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

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

3. Разработан комплекс программ, реализующих предложенные алгоритмы и экспериментально показывающий их преимущество по отношению к существующим.

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

1. Ахо А.В., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — М.: Мир, 2001.

2. Кауль С.Б. Оценка вероятности связности случайного графа // Эффективность и структурная надёжность информационных систем (СМ-7). — Новосибирск, 1982. С. 3-6.

3. Кельманс А.К. Некоторые вопросы надёжности сетей // Автоматика и телемеханика. — 1965, т. 26, № 3. С. 567-574.

4. Краковская О. С., Толчан А. Я. Оценки вероятности связности графа сети связи // Информационные сети и коммутация. — М.: Наука, 1968. С. 138-141.

5. Литвак Е.И. О вероятности связности графа // Изв. АН СССР. Техн. Кибернетика.- 1975. — № 5. С. 161-165.

6. Ломоносов М.В., Полесский В.П. Верхняя граница надежности информационных сетей // Проблемы передачи информации. — 1971. Т. 7, вып. 4. С. 78-81.

7. Ломоносов М.В., Полесский В.П. Нижняя оценка надежности сетей // Проблемы передачи информации. — 1972. Т. 8, вып. 2. С. 567-574.

8. Ломоносов М.В., Полесский В.П. О максимуме вероятности съязности // Проблемы передачи информации. — 1972. Т. 8, вып. 1. С. 68-73.

9. Мигов Д.А. Использование разрезов случайного графа для вычисления вероятности его связности// Труды конф. молодых ученых ИВМиМГ СО РАН. — Новосибирск: ИВМиМГ СО РАН, 2004. С. 133-140.

10. Мигов Д.А. Вероятность связности 5-и вершинного графа// Мат. Межд. семинара "Выч. методы и решение оптимизационных задач"(Кыргызская респ., Бишкек).

11. Новосибирск, 2004. — С. 113-116.

12. Мигов Д.А. Расчет вероятности связности .ЙГ-полюсной сети с применением двухвершинных разрезов// Труды конф. молодых ученых ИВМиМГ СО РАН. — Новосибирск: ИВМиМГ СО РАН, 2005. С. 95-101.

13. Мигов Д.А. Расчет вероятности связности сети с применением продольных разрезов// Труды конф. молодых ученых ИВМиМГ СО РАН. — Новосибирск: ИВМиМГ СО РАН, 2006. — С. 144-151.

14. Мигов Д.А. Методы ускорения расчета надежности Л'-полюсной сети, основанные на рассмотрении вершинных разрезов// Мат. IX межд. конф. "Проблемы функционирования информационных сетей". — Новосибирск: ИВМиМГ СО РАН, 2006. — С. 205-209.

15. Мигов Д.А. Использование вершинных разрезов для точного вычисления вероятности связности сети// Труды межд. конф. "Вычислительные и информационные технологии в науке, технике и образовании". — Казахстан, Павлодар: ПГУ, 2006. С. 51-56.

16. Мигов Д.А. Вычисление вероятности связности подмножества узлов сети с использованием двухвершинных разрезов// Мат. 2-ой Азиатской межд. школы-семинара "Проблемы оптимизации сложных систем". — Новосибирск: ИВМиМГ СО РАН, 2006. С. 134-138.

17. Мигов Д.А. Стратегия выбора разрешающего ребра в методе ветвления и применение сечений при вычислении вероятности связности графа// Мат. 4-ой Азиатской межд. школы-семинара "Проблемы оптимизации сложных систем"(респ. Алтай), 2008. В печати.

18. Мигов Д.А. Выбор разрешающего ребра в методе ветвления и применение сечений для расчета надежности сетей// Мат. X межд. конф. "Проблемы функционирования информационных сетей". — Новосибирск: ИВМиМГ СО РАН, 2008. — С. 73-75.

19. Мур Э., Шеннон К. Надежные схемы из ненадежных реле // Кибернетический сб.

20. М.: Иностр. лит., 1960. — Вып. 1. — С. 109-148.

21. Попков В. К. Математические модели связности. Ч. 1-3. — Новосибирск: Изд. ИВМиМГ СО РАН, 2000-2002.

22. Родионов А.С., Родионова O.K., Мигов Д.А., Мурзин М.Ю. Использование метода ветвления для точного расчёта вероятности связности случайного графа// Математика и безопас-ность информационных технологий. — М.: МГУ MIIHMO. 2005. С. — 333-341.

23. Родионов А.С., Родионова O.K. О точном вычислении вероятности связности графа // Тр. Междунар. конф. "Вычичлительные технологии и математические модели в науке, технике и образовании", Алма-Ата, Казахстан, 2002. — Т. 5. — С. 140-147. (

24. Родионов А.С., Родионова O.K. Некоторые методы ускорения расчета надежности информационных сетей // Мат, 30 Междунар. конф. "Информационные технологии в науке, образовании, телекоммуникации и бизнесе", Гурзуф, Украина, 2003.- С. 215-217.

25. Родионова O.K. Исследование и разработка методов анализа и синтеза оптимально-связных информационных сетей: Дис. . канд. физ.-мат. наук: 05.13.18. — Новосибирск, 2003.

26. Степанов В.Е. О вероятности связности случайного графа // Теория вероятностей и её применения. — 1970. т. 15, вып. 1. — С. 56-68.

27. Baoding, Liu К. Topological Optimization Models for Communication Network- with Multiple Reliability Goals // Computers and Mathematics with Applications. — 2000. Volume 39, Issues 7-8. P 59-69.

28. Buzacott J.A., Chang S.K. Cut set intersection and node partition // IEEE Trans. Reliab. R-33, 1984. P. 385-389.

29. Birnbaum Z.W., Esary J.D. Modules of coherent binary systems // SIAM J. Appl. Math. 1965. Vol. 13. P. 444-462.

30. Cancela H., Petingi L. Reliability of communication networks with delay constraints: computational complexity and complete topologies // IJMMS. — 2004. Vol 29. P. 15511562.

31. Chat Srivaree-ratana, Abdullah Konak and Alice E. Smith. Estimation of all-terminal network reliability using an artificial neural network // Computers and Operations Research, Volume 29, Issue 7, June 2002, p. 849-868

32. Charles J. Colbourn. The Combinatorics of Network Reliability. — Oxford University Press, New York, 1987.

33. Eiselt H.A., Michel Gendreau and Gilbert Laporte. Optimal location of facilities on a network with an unreliable node or link // Information Processing Letters. — 1996. Vol. 58, Issue 2. P. 71-74.

34. Fang-Ming Shao, Lian-Chang Zhao. Topological Optimization of Computer Network Expansion with Reliability Constraint // Computers and Mathematics with Applications. — 1998. Volume 35, Issue 11. P. 17-26

35. Fard N., Tae-Han Lee Spanning tree approach in all-terminal network reliability expansion // Computer Communications. — 2001. Volume 24, Issue 13. P. 1348-1353.

36. Jacques Carlier, Corinne Lucet. A decomposition algorithm for network reliability evaluation // Discrete Applied Mathematics. — March 1996. Vol. 65, no. 1-3. P. 141156.

37. Jacques Carlier, Li Yu and Jean-luc Lutton // Reliability evaluation of large telecommunication networks. Discrete Applied Mathematics. — 1997. Volume 76, Issues 1-3. P. 61-80.

38. John Lee. Reliability models of a class of self-healing rings // Microelectronics and Reliability. 1997. Vol. 37, Issue 8. P. 1179-1183.

39. Kansal M.L., Arun Kumar P.B. Reliability analysis of water distribution systems under uncertainty // Reliability Engineering and System Safety. — 1995. Volume 50, Issue 1. P. 51-59

40. Koide Т., Shinmori S. and Ishii H. Topological optimization with a network reliability-constraint // Discrete Applied Mathematics. — 2001. Vol. 115, Issues 1-3. P. 135-149.

41. Lehman A. Wye-delta transformation in probabilistic // J. SIAM, 1963. V. 11. P. 713825.

42. J. Levendovszky, L. Jereb, Zs. Elek and Gy. Vesztergombi. Adaptive statistical algorithms in network reliability analysis // Performance Evaluation, Volume 48, Issues 1-4, May 2002, p. 225-236.

43. Yubin Chen, Jiandong Li, Jiamo Chen. A new algorithm for network probabilistic connectivity // Military Communications Conference Proceedings, 1999. Vol. 2. P. 920923.

44. Li Ying. Analysis method of survivability of probabilistic Networks// Military Comm. Technology Magazine. Vol. 48, 1993.

45. Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer-Verlag LNCS, Vol. 4097, 2006.— P. 702-709.

46. Nahman J. Fuzzy logic based network reliability evaluation // Microelectronics and Reliability. — 1997. Volume 37, Issue 8. P. 1161-1164.

47. Rodionov A.S., Choo H. On Generating Random Network Structures: Connected Graphs // Proc. Intern. Conf. On Information Netwotking ICOIN 2004. Vol 3. P. 11451152.

48. Rosenthal A. Computing the realiability of comlex networks // SIAM J. Appl. Math. 1977. Vol 32. P. 133-152.

49. Peter Tittmann. Partitions and network reliability // Discrete Applied Mathematics. Vol. 95, Issues 1-3, 1999. P. 445-453.

50. Shaio J. A family of algorithms for network reliability problems // Communications — 2002. Vol 4. P. 2167 -2173.

51. Shao Fang-Ming and Zhao Lian-Chang. Optimal design improving a communication network reliability // Microelectronics and Reliability. — 1977. Vol. 37, Issue 4. P. 591595.

52. Rodionova O.K., Rodionov A.S. and Choo H. Network Probabilistic Connectivity: Exact Calculation with Use of Chains // ICCSA-2004, Springer Lecture Notes in Computer Sciences. Vol. 3046. P. 315-324.

53. Satyanarayana A., Wood R.K. A linear-time algorithm for computing K-terminal 1 reliability in series-parallel networks // SIAM. J. Comput. — 1985. Vol. 14. P. 818

54. Shooman A.M., Kershenbaum A. Exact graph-reduction algorithms for network reliability analysis // GLOBECOM '91. Countdown to the New Millennium. Featuring a Mini-Theme on: Personal Communications Services. — 1991. Vol 2. — P. 1412 -1420.

55. Shooman A.M., Kershenbaum A. Methods for communication-network reliability analysis: probabilistic graph reduction // Reliability and Maintainability Symposium, 1992. Proceedings. P. 441-448.

56. Shooman A.M. Algorithms for network reliability and connection availability analysis // Electro/95 International. Professional Program Proceedings. — 1995. — P. 309-333.

57. Wang Wenyi, Zhang Hongfen. The methods of reduction in network reliability computing // Microelectronics and Reliability. — 1997. Vol. 37, Issue 3. P. 461-465.

58. Wood R.K. Triconnected Decomposition for Computing K-Terminal Network Reliability // Networks. 1989. Vol. 19. P. 203-220.883.