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

Оглавление
Введение
Глава 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. Выводы.
Заключение
Литература