Введение к работе
Актуальность работы. В работе рассматривается задача расчета вероятности связности случайного графа с ненадежными ребрами и абсолютно надежными вершинами. Эта характеристика является одним из основных показателей структурной надежности сетей связи, в которых надежность узлов на порядки превосходит надежность каналов связи. Задача расчета над ежн ости возникает при проектировании и структурной оптимизации таких сетей. В зависимости от сложности вычислений (размерности задачи) для этого могут быть использованы как точные, так и приближенные методы.
Так как задача точного расчета NP-трудна, ранее на практике использовали различные приближенные методы, тогда как точные методы представляли в большей степени академический интерес. Однако развитие вычислительной техники привело к возрождению интереса к использованию этих методов на практике, потому что появилась возможность за разумное время рассчитывать надежность сетей малой и средней размерности (десятки и сотни узлов). С другой стороны, проверка приближенных методов на точность их работы также вызывает необходимость дальнейшего исследования точных методов.
Цель работы — разработка методов для повышения эффективности работы точных алгоритмов расчета вероятности связности случайного графа.
Методы исследования базируются на теории графов и методах теории вероятностей.
Научная новизна работы состоит в следующем:
Установлено, что вероятность связности графа может быть выражена через вероятности связности производных от подграфов, на которые граф разделяется сечением. Получены формулы для вероятности связности графов с сечениями из двух, трех и четырех вершин.
Разработана методика получения формул с небольшим числом операций (по сравнению с известными формулами) для
вероятности связности подмножества вершин в графах малой размерности, что существенно ускоряет процесс расчета на графах произвольной размерности методом ветвления.
Практическая значимость работы. Предложенные методы могут быть использованы на практике для проектирования, анализа и структурной оптимизации сетей различного назначения.
Апробация работы. Основные научные результаты диссертации докладывались и обсуждались на следующих конференциях и семинарах:
9-я, 10-я, 11-я Конференции молодых ученых ИВМиМГ СО РАН. Новосибирск, 2004, 2005, 2006. Два доклада (2004, 2006) отмечены премиями.
МНПК "Связь-2004". Международный семинар "Вычислительные методы и решение оптимизационных задач". Озеро Иссык-Куль, Кыргызская респ., 2004.
5-я и 6-я Всероссийские конференции молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых). Новосибирск и Кемерово, 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 таблиц.
