Asymp-totics of connectivity probabilities for complete graphs with the low reliable arcs and for all pairs of nodes in them are constructed. Parameters of these asymptotics are characteristics of spanning trees and shortest paths. The calculation of the spanning trees characteristics is based on the Kirchhoff — Trent theorem. Modifications of classical algorithms are applied to calculate the characteristics of shortest paths.
Download file
Counter downloads: 63
- Title Asymptotics for connectivity probability of graph with low reliable arcs
- Headline Asymptotics for connectivity probability of graph with low reliable arcs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(19)
- Date:
- DOI
Keywords
остовное дерево, матрица Кирхгофа, кратчайший путь, вероятность связности, вычислительная сложность, spanning tree, Kirchhoff's matrix, shortest path, connectivity probability, calculation complexityAuthors
References
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.
Asymptotics for connectivity probability of graph with low reliable arcs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 1(19).
Download full-text version
Download fileCounter downloads: 234