Конференции ИВТ СО РАН

Тезисы докладов

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

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

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

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

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

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

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск