Приведены результаты вычислительных экспериментов по определению вероятности несвязности планарных графов с высоконадёжными рёбрами. Полученныерезультаты подтверждают теоретическую, не более чем кубическую, оценку сложности проводимых вычислений, основанных на рассмотрении двойственных графов и построении асимптотических соотношений. Приведены результаты сравнения используемого методы с методом Монте-Карло, которые свидетельствуют осущественном сокращении числа арифметических операций и времени счета.
Скачать электронную версию публикации
Загружен, раз: 60
- Title Связность планарного графа с высоконадёжными рёбрами
- Headline Связность планарного графа с высоконадёжными рёбрами
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 3(17)
- Date:
- DOI
Ключевые слова
вероятность связности, двойственный граф, минимальный разрез, connectivity probability, dual graph, minimal cross sectionАвторы
Ссылки
Золотухин И. В. Углеродные нанотрубки / / Соросовский образовательный журнал. 1999. №3. С. 111-115.
Harary F. and Manvel B. On the Number of Cycles in a Graph / / Matematickycasopis. 1971. V. 21. No. 1. P. 55-63.
Прасолов В. В. Элементы комбинаторной и дифференциальной топологии. М.: МЦНМО, 2004. 352 с.
Whithney H. Nonseparable and planar graphs / / Trans. American Math. Soc. 1932. V. 34. P. 39-362.
Tsitsiashvili G. Sh. Complete calculation of disconnection probability in planar graphs // Reliability: Theory and Applications. 2012. V. 1(24). No. 1. P. 154-159.
Буртин Ю, Питтель Б. Асимптотические оценки надёжности сложных систем / / Техническая кибернетика. 1972. Т. 10. №3. С. 90-96.
Связность планарного графа с высоконадёжными рёбрами | Прикладная дискретная математика. 2012. № 3(17).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 247