ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.04.2021
Просмотров: 2126
Скачиваний: 4
235
7.
Мищенко Е.Ф. Асимптотическое вычисление периодических решений систем диф-
ференциальных уравнений, содержащих малые параметры при производных// 1957.
Изв. АН СССР. Сер. мат. Т. 21, вып 5. С. 627-654.
8.
Цициашвили Г.Ш. Параметрическая и структурная оптимизации пропускной спо-
собности сети массового обслуживания// Автоматика и телемеханика, 2007, вып. 7,
с. 64-73.
9.
Боровков А.А. Вероятностные процессы в теории массового обслуживания. М.: На-
ука. 1971.
10.
Рыбко А.Н., Столяр А.Л. Об эргодичности случайных процессов, описывающих
функционирование открытых сетей массвого обслуживания// Проблемы передачи
информации. 1992. Том 28, выпуск 3. С. 3–26.
11.
Адаму А., Гайдамака Ю.В., Самуйлов А.К. К анализу состояния буфера пользо-
вателя одноранговой сети с потоковым трафиком// T-comm - Телекоммуникации и
транспорт. 2011. Вып 7. С. 8-12.
12.
Ширяев А.Н. Вероятность. М.: Наука. 1989.
13.
Ибрагимов И.А., Линник Ю.В. Независимые и стационарно связанные величины.
М.: Наука. 1969.
14.
Боровков А.А. Асимптотические методы в теории массового обслуживания. М.: На-
ука. 1980.
15.
Цициашвили Г.Ш. Исследование почти детерминированных систем массового обслу-
живания// ДВ мат. сборник. 1997. Вып. 3. C. 17-22.
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.
УДК 519.248:62-192+519.176
АСИМПТОТИКИ ВЕРОЯТНОСТЕЙ
СВЯЗНОСТИ ПАР ВЕРШИН ГРАФА
Г.Ш. Цициашвили
Институт прикладной математики ДВО РАН
Россия, 690041, Владивосток, Радио 7
E-mails:
guram@iam.dvo.ru
М.А. Осипова
ДВФУ
Россия, 690091, Владивосток, ул. Суханова 8
E-mail:
mao1975@list.ru
Ключевые слова:
кратчайший путь, вероятность связности, вычислитель-
ная сложность
Для графов с низконадежными ребрами построена асимптотика вероятности
связности любой пары его вершин. Параметрами полученного соотношения
являются характеристики кратчайших путей графа. Для вычисления этих
характеристик разработаны модификации классических алгоритмов. На ос-
нове полученных результатов был проведен вычислительный эксперимент,
который продемонстрировал преимущества предложенных алгоритмов.
Введение
Для случайных графов с низконадежными рёбрами построен удобный в реа-
лизации алгоритм вычисления вероятности связности любой пары его вершин на
основе доказанного асимптотического соотношения. Для параметров полученного
соотношения (характеристик кратчайших путей) разработаны модификации клас-
сических алгоритмов. Особенностью предлагаемых алгоритмов является тот факт,
что в них не требуется перечислять кратчайшие пути между узлами, а лишь опре-
делять их количество. Еще одним существенным фактором упрощения вычислений
является рассмотрение графов с ограниченным диаметром, которые в последние
годы вызывают большой теоретический и практический интерес. Проведенный вы-
числительный эксперимент подтвердил быстродействие построенной процедуры для
вероятности связности по сравнению с методом Монте-Карло.
1.
Основные результаты
Рассмотрим неориентированный связный простой граф
G
с множеством узлов
U
и множеством рёбер
V.
Предположим, что каждое ребро
v
графа
G
с вероятно-
стью
p
(
v
)
работоспособно, причём все ребра функционируют независимо. Обозна-
чим
D
(
i, j
)
минимальное число ребер в путях, соединяющих узлы
i, j
графа
G
, а
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.
237
C
(
i, j
)
число путей с
D
(
i, j
)
рёбрами. Для вероятности связности
P
ij
(
G
)
узлов
i, j
графа
G
доказаны следующие утверждения.
Теорема 1.
Если
p
(
v
) =
h, v
∈
V,
то
P
ij
(
G
)
∼
C
(
i, j
)
h
D
(
i,j
)
, h
→
0
.
(1)
Следствие 1.
Если
p
(
v
) =
h, v
∈
V,
то
min
1
6
i,j
6
n
P
ij
(
G
)
∼
Ch
D
, h
→
0
,
D
= max
1
6
i,j
6
n
D
(
i, j
)
, C
=
min
(
i,j
):
D
(
i,j
)=
D
C
(
i, j
)
.
Для нахождения всех элементов матриц
||
D
(
i, j
)
||
n
i,j
=1
,
||
C
(
i, j
)
||
n
i,j
=1
асимптотиче-
ской формулы (1) были построены модификации известных в теории графов алго-
ритмов (в том числе Флойда-Стейнберга). Такая процедура является более эконо-
мичной, чем последовательное определение элементов этих матриц, имеет вычис-
лительную сложность
O
(
n
3
ln
n
)
для матрицы
||
D
(
i, j
)
||
n
i,j
=1
||
и
O
(
n
4
)
для матри-
цы
||
C
(
i, j
)
||
n
i,j
=1
.
Зная матрицу
||
D
(
i, j
)
||
n
i,j
=1
, можно вычислить диаметр
D
гра-
фа
G.
Для сетей с ограниченным диаметром
D
сложность вычисления матриц
||
D
(
i, j
)
||
n
i,j
=1
,
||
C
s
(
i, j
)
||
n
i,j
=1
составляет
O
(
n
3
)
арифметических операций.
2.
Результаты вычислительного эксперимента
На основе построенного алгоритма для вероятности связности любой пары вер-
шин графа был проведён вычислительный эксперимент. Зададим граф
G
матрицей
смежности:
0
1
0
1
0
1
1
0
1
0
0
1
0
1
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
1
1
0
0
1
0
Полагаем, что работоспособность его рёбер
p
(
v
) =
h
= 0
.
01
. Используя модифици-
рованные алгоритмы, вычислим:
||
D
(
i, j
)
||
6
i,j
=1
=
0
1
2
1
2
1
1
0
1
2
2
1
2
1
0
1
2
2
1
2
1
0
1
2
2
2
2
1
0
1
1
1
2
2
1
0
,
||
C
(
i, j
)
||
6
i,j
=1
=
0
1
2
1
2
1
1
0
1
2
1
1
2
1
0
1
1
1
1
2
1
0
1
2
2
1
1
1
0
1
1
1
1
2
1
0
.
Результаты вычислений вероятностей связности пар вершин
P
ij
(
G
)
,
1
6
i, j
6
6
,
по формуле (1) и методом Монте-Карло, обозначим их
P
∗
ij
(
G
)
,
1
6
i, j
6
6
,
при
10
6
числе реализаций представлены ниже:
||
P
ij
(
G
)
||
6
i,j
=1
=
1
0,01
0,0002
0,01
0,0002
0,01
0,01
1
0,01
0,0002
0,0001
0,01
0,0002
0,01
1
0,01
0,0001
0,0001
0,01
0,0002
0,01
1
0,01
0,0002
0,0002
0,0001
0,0001
0,01
1
0,01
0,01
0,01
0,0001
0,0002
0,01
1
,
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.
238
||
P
∗
ij
(
G
)
||
6
i,j
=1
=
1
0,01035
0,000203
0,010027
0,000192
0,010205
0,01035
1
0,010001
0,000198
0,000095
0,009764
0,000203
0,010001
1
0,010083
0,000094
0,000103
0,010027
0,000198
0,010083
1
0,010051
0,000208
0,000192
0,000095
0,000094
0,010051
1
0,009973
0,010205
0,009764
0,000103
0,000208
0,009973
1
.
Время счета по формуле (1) составило 10 секунд, методом Монте-Карло - 6 часов.
Полученные по асимптотическому анализу вероятности связности узлов случайных
графов результаты опубликованы в работах [1-3]. Авторы болагодарят А.С. Лосева
за большую помощь в проведении вычислительных экспериментов.
Список литературы
1.
Цициашвили Г.Ш., Лосев А.С. Связность планарного графа с высоконадежными
ребрами// Прикладная дискретная математика. 2012. Вып. 3. С. 103-107.
2.
Цициашвили Г.Ш., Осипова М.А., Лосев А.С. Асимптотика вероятности связно-
сти графа с низконадежными ребрами// Прикладная дискретная математика. 2013.
Вып. №1. С. 93-98.
3.
Цициашвили Г.Ш., Осипова М.А., Лосев А.С. Асимптотические формулы для ве-
роятностей связности случайных графов// Автоматика и вычислительная техника.
2013. Вып. 2. С. 22-28.
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.
УДК 519.214
О ТОЧНОСТИ ПРИБЛИЖЕНИЯ
БИНОМИАЛЬНОГО РАСПРЕДЕЛЕНИЯ
ГАУССОВЫМ ЗАКОНОМ
В.И. Чеботарев
Вычислительный центр ДВО РАН
Россия, 680000, Хабаровск, Ким Ю Чена, 65
E-mail:
chebotarev@as.khb.ru
С.В. Нагаев
Институт математики им. С.Л. Соболева
Россия, 630090, Новосибирск, пр. Коптюга, 4
E-mail:
nagaev@math.nsc.ru
Ключевые слова:
неравенство Берри – Эссеена, метод сглаживания, ме-
тод характеристических функций, биномиальное распределение, неравно-
мерные оценки
Исследуется поведение сумм вида
P
k<x
C
k
n
p
k
q
n
−
k
. Для этого сначала выво-
дится так называемое равенство сглаживания. Оно приводит к представле-
нию погрешности в интегральной теореме Муавра – Лапласа в виде сум-
мы двух выражений. Одно появляется как результат применения формулы
обращения, а другое – как результат сглаживания. Определяется вклад в
погрешность каждого из выражений.
Пусть
Z
– двухточечная случайная величина с распределением
P
(
Z
= 1) =
p,
P
(
Z
= 0) =
q,
p
+
q
= 1
,
Z
1
, Z
2
, . . . , Z
n
– независимые копии случайной величины
Z
. Обозначим
Φ(
x
) =
1
√
2
π
x
Z
−∞
e
−
y
2
/
2
dy,
δ
n
(
p, x
) =
P
1
√
npq
n
X
j
=1
(
Z
j
−
p
)
< x
−
Φ(
x
)
,
(1)
∆
n
(
p
) = sup
x
∈
R
|
δ
n
(
p, x
)
|
.
В силу интегральной предельной теоремы Муавра – Лапласа
lim
n
→∞
∆
n
(
p
) = 0
для
любого
p
∈
(0
,
1)
. Сформулируем оценку величины
∆
n
(
p
)
, полученную в [1]. Так
же, как в [1], ради простоты формулировок мы будем рассматривать только случай
0
< p
6
0
.
5
. Нам понадобятся три функции:
K
1
(
p, n
)
,
K
2
(
p, n
)
и
K
3
(
p, n
)
, введенные
в [1]. Они имеют достаточно громоздкий вид, и здесь мы их не приводим. Обозначим
β
3
(
p
) =
E
Z
−
p
√
pq
3
≡
p
2
+
q
2
√
pq
,
E
(
p
) =
2
−
p
3
√
2
π
[
p
2
+ (1
−
p
)
2
]
.
(2)
Заметим, что
max
0
<p
6
0
.
5
E
(
p
) =
C
E
≡
√
10+3
6
√
2
π
= 0
.
409732
. . .
(см. [1]).
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.