ГлавнаяАрхивАсимптотика вероятности связности графа с низконадёжными рёбрами

Асимптотика вероятности связности графа с низконадёжными рёбрами | Прикладная дискретная математика. 2013. № 1(19).

Для графов с низконадёжными ребрами построены асимптотики вероятностей связности всего графа и любой пары его вершин. Параметрами полученных соотношений являются характеристики остовных деревьев графа и кратчайших путей. Для вычисления характеристик остовных деревьев получены формулы с помощью теорем Кирхгофа — Трента, а для вычисления характеристик кратчайших путей разработаны модификации классических алгоритмов.
  • Title Асимптотика вероятности связности графа с низконадёжными рёбрами
  • Headline Асимптотика вероятности связности графа с низконадёжными рёбрами
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 1(19)
  • Date:
  • DOI
Ключевые слова
остовное дерево, матрица Кирхгофа, кратчайший путь, вероятность связности, вычислительная сложность, spanning tree, Kirchhoff's matrix, shortest path, connectivity probability, calculation complexity
Авторы
Ссылки
Tsitsiashvili G. Sh.Complete calculation of disconnection probability in planar graphs // Reliability: Theory and Applications. 2012. V. 1. No. 1. P. 154-159.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 893 c.
Ильин В. А, Позняк Э. Г. Линейная алгебра. М.: Физматлит, 2004. 280 с.
Floid R. W. and Steinberg L. An adaptive algorithm for spatial grayscale // SID 75 Digest. New York, N.Y.: Lewis Winner, 1975. P. 36-37.
Чеботарев П. Ю., Шамис Е. В. Матричная теорема о лесах и измерение связей в малых социальных группах // Автоматика и телемеханика. 1997. Т. 9. С. 125-137.
Райгородский А. М. Модели случайных графов и их применение // Труды МФТИ. 2010. Т. 2. №4. С. 130-140.
Ломоносов М. В., Полесский В. П. Нижняя оценка надежности сетей // Проблемы передачи информации. 1972. Т. 8. №2. С. 47-53.
Мигов Д. А. Расчет надежности сети с ограничением на диаметр с использованием сочленений // Проблемы информатики. 2011. №3. С. 4-9.
Харари Ф. Теория графов. М.: Мир, 1973. 314с.
Мигов Д. А. Расчет надежности сети с ограничением на диаметр с применением точек сочленения // Автоматика и телемеханика. 2011. №7. С. 69-74.
Whithney H. Nonseparable and planar graphs // Transact. Amer. Math. Soc. 1932. V. 34. P. 339-369.
Буртин Ю., Питтель Б. Асимптотические оценки надёжности сложных систем // Техническая кибернетика. 1972. Т. 10. №3. С. 90-96.
Асимптотика вероятности связности графа с низконадёжными рёбрами | Прикладная дискретная математика. 2013. № 1(19).
Асимптотика вероятности связности графа с низконадёжными рёбрами | Прикладная дискретная математика. 2013. № 1(19).
Полнотекстовая версия