Расчет вероятности связности случайного графа с применением сечений

• Автор: Мигов, Денис Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Новосибирск
• Количество страниц: 97 с. : ил.

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

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

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

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

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

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

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

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

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

1.6.1. Формула вероятности связности подмножества вершин в графе произвольной размерности.
1.6.2. Вероятность связности подмножества вершин в 4х вершинном графе.
1.7. Прочие методы.
1.8. Выводы
Глава 2. Использование сечений в расчете вероятности связности случайного графа
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. Выводы.
Заключение
Литература


В последнее время широко распространено мнение, что в ряде промышленных отраслей с экономической точки зрения выгодней применять системы повышенной надежности. Например, это экономически оправданно в телекоммуникационных сетях, банковских системах, сетях подтверждения кредитоспособности, и системах оформления заказов. Основной целью исследований в области сетевой надежности является стремление разработать методы для инженеров-проектировщиков, чтобы упростить проектирование сетей, требующих повышенной надежности. В процессе проектирования перебираются различные технически допустимые варианты топологии сети, для которых необходимо будет вычислить значение меры надежности. В зависимости от сложности вычислений (размерности задачи) для этого могут использованы как точные, так и приближенные методы. При рассмотрении задач, связанных с надежностью сетей, сеть обычно описывается случайным графом, где ребра отображают сетевые каналы, а в качестве узлов выступают рабочие станции, серверы, переключатели, маршрутизаторы или другие устройства. Каждый элемент графа присутствует с определенной вероятностью, что выражает надежность соответствующего элемента сети. Под надежностью сети понимается вероятность связности заданного подмножества вершин графа. Возможны различные варианты: абсолютно надежные вершины (с вероятностью присутствия, равной еденице) и ненадежные ребра, ненадежные вершины и абсолютно надежные ребра, ненадежные вершины и ребра, вероятности присутствия элементов зависят от времени, ориентированные или неориентированные ребра и т. В данной работе рассматриваются неориентированные графы с абсолютно надежными вершинами и ненадежными ребрами. Задача состоит в вычислении вероятности связности заданного подмножества вершин графа. Данная задача является КР-трудной [, ], поэтому ранее на практике использовали различные приближенные методы, тогда как точные методы представляли в большей степени академический интерес. Однако развитие вычислительной техники привело к возрождению интереса к использованию этих методов на практике, так как появилась возможность за разумное время рассчитывать надежность сетей малой 1? С другой стороны, проверка приближенных методов на точность их работы также вызывает необходимость дальнейшего исследования точных методов. Вопросом вычисления или оценки различных характеристик связности подмножества узлов сетей различной природы на моделях случайных графов (особенно в частных случаях, когда это подмножество состоит из двух или из всех узлов) занимались и занимаются многие исследователи как в России, так и за рубежом. Из отечественных прежде всего надо упомянуть Артамонова Г. Т., Вишневского В. М., Егунова М. М., Епн-хпна В. В., Кауля С. Б., Кельманса А. К., Литвака В. И., Ломоносова М. В., Майнагашева С. М., Нечепуренко М. И., Полесского В. П., Попкова В. К, Родионова A. C., Родионову O. K., Скоробо^това В. A., Толчана А. Я, Хар-кевича А. Д. Из зарубежных исследователей это Colbourn C. J., Moor E. Satyanarayana A. Sherinon K. Shooman A. M., Van Slyke M. Wood R. В диссертационной работе предлагаются новые методы понижения размерности для поставленной задачи, основанные на использовании сечений, то есть вершинных разрезов. Также предложена методика получения формул с относительно небольшим числом операций для вероятности связности подмножества вершин в графах малой размерности; такие формулы необходимы для расчета искомой характеристики для графов произвольной размерности методом ветвления. Глава 1 содержит формальное описание задачи и обзор известных методов се решения. Кроме этого, в данной главе получены формулы для вероятности связности 4-х и 5-и вершинных графов. Эти формулы основаны на переборе несвязных частных реализаций графа, причем за основу перебора берутся случаи полного отсечения каждой из вершин. Полученные таким образом формулы содержат меньшее количество операций, чем известные формулы, которые были получены перебором всех связных реализаций графа. Результаты автора, изложенные в данной главе, опубликованы в [, , ]. В Главе 2 изложены результаты автора для задачи расчета вероятности связности всех вершин случайного графа.