Вычислительная техника и прикладная математика

• Название: Вычислительная техника и прикладная математика
• Дата: 12.05.2023
• Размер: 0.78 Mb.
• Имя файла: razdel-3-33.pdf
• Тип: Документы; #1125413
• страница: 6 из 6

Определение_1. Дугу
 
l
jk
U
(петлю
kk
U ) гра-
фа
 
 
 


t
G
t
G
P
X
t
G
,

будем называть замкну-
той в сечении
T
t 

, если в этом временном
сечении существуют обе инцидентные этой
дуге вершины
k
j
x
x ,
(существует инцидентная
петле вершина
k
x ).
Определение_2. Дугу
 
l
jk
U
(петлю
kk
U ) гра-
фа
 
 
 


t
G
t
G
P
X
t
G
,

будем называть откры-
той в сечении
T
t 

, если в этом временном
сечении не существуют обе инцидентные
этой дуге вершины
k
j
x
x ,
(не существует инци-
дентная петле вершина
k
x ).
Определение_3.
Дугу
 
l
jk
U
графа
 
 
 


t
G
t
G
P
X
t
G
,

будем называть полуотк-

62
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
рытой слева в сечении
T
t 

, если в этом
временном сечении вершина
j
x (откуда исхо-
дит дуга) не существует, а вершина
k
x (куда
заходит дуга) существует.
Определение_4.
Дугу
 
l
jk
U
графа
 
 
 


t
G
t
G
P
X
t
G
,

будем называть полуотк-
рытой справа в сечении
T
t 

, если в этом
временном сечении вершина
j
x (откуда исхо-
дит дуга) существует, а вершина
k
x (куда за-
ходит дуга) не существует.
Определение_5. ОДВНГ будем называть
замкнутым в сечении
T
t 

, если в этом
сечении все существующие дуги (петли) графа
являются замкнутыми.
Рассмотрим далее отдельное временное сечение
T
t 

. В момент времени
t

определена многомерная случайная величина
 
m
B
t


:

, отображающая последователь- ность всех булеанов
B
в

m мерное прост- ранство векторов
 
 
 


t
t
t
m



...,
,
,
2 1
, где
 


t
j

- порядковый номер элемента
 
 
j
t
j
b


j
го булеана
j
B
Обозначим через


 
 
 


m
m
def
m
t
z
t
z
t
z
t
P
z
z
z
F







...,
,
,
...,
,
,
2 2
1 1
2 1
m
j
j
N
z
1
)
(


функцию распределения случай- ной величины
 
t

в момент времени
T
t 
. Тот факт, что элементы всякого булеана упоря- дочены (и ранжированы с учётом количества
элементов в отдельном элементе булеана), позволяет для каждого момента времени
t

получить информацию о количестве вершин и дуг графа
 
 
 


t
G
t
G
P
X
t
G


,


по значениям


m
t
z
z
z
F
...,
,
,
2 1

, вычисление которых не представляет затруднений. Действительно, из статистической независимости элементов булеанов следует, что


n
t
z
z
z
F

...,
,
,
2 1
 
 
 
m
t
t
t
z
F
z
F
z
F




2 1
. Рассмотрим лю- бую из этих величин
 
j
t
z
F
. Принципиально различаются два случая, когда булеан
j
B
есть булеан множества вершин графа


G
G
P
X
G
,

, и когда
j
B
- булеан какого-то множества дуг.
Рассмотрим эти случаи по отдельности.
Если рассматривать булеан вершин
 
 
 




,
...,
,
,
...,
,
,
2 1
1 2
1
s
i
i
i
j
i
j
j
j
x
x
x
b
x
b
b
B





, то процедура поиска значения
 
 


j
j
j
t
z
t
P
z
F





следующая. Выберем все элементы
j
B
с номерами, меньшими, чем
j
z
:
 
 
 
j
z
j
j
j
b
b
b
1 2
1
...,
,
,

. По формуле вероят- ности объединения несовместных событий найдём
 
 














1 1

1 1
j
j
z
i
j
i
t
z
i
j
i
b
p
b
P

. Вероят- ности
 
 
j
i
t
b
p

найдём по формуле вероятности произведения независимых событий. Предпо- ложим, что элемент булеана
 
j
z
j
b
1

с наибольшим порядковым номером среди рассматриваемых содержит


1
ˆ

j
z
n
элементов. Тогда значение
 
 


j
j
j
t
z
t
P
z
F





определяет вероятность события, состоящего в том, что “в сечении
t

граф
 
 
 


t
G
t
G
P
X
t
G


,


будет иметь коли- чество вершин, не большее чем


1
ˆ

j
z
n
“.
Если анализируется булеан множества дуг
 
 
 
 
 
 
 




,
...,
,
,
...,
,
,
2 1
1 2
1
s
i
kr
i
kr
i
kr
j
i
kr
j
j
j
U
U
U
b
U
b
b
B





, то для нахождения
 
 


j
j
j
t
z
t
P
z
F





по- ступаем аналогично. По формуле вероятности объединения несовместных событий найдём
 
 
 












1 1

1 1
j
j
z
i
j
i
t
z
i
j
i
b
p
b
P

. Вероятности
 
 
j
i
t
b
p

найдём по формуле вероятности произведения независимых событий. Предположим, что эле- мент булеана
 
j
z
j
b
1

с наибольшим порядковым номером среди рассматриваемых содержит


1


j
kr
z
n
элементов.
Тогда значение
 
 


j
j
j
t
z
t
P
z
F





определяет вероятность события, состоящего в том, что “в сечении
t

граф
 
 
 


t
G
t
G
P
X
t
G


,


будет иметь коли- чество дуг, проведённых из вершины
k
x
в вершину
r
x
, не большее чем


1

j
kr
z
n
“.
Очевидно, что значение функции


 
 
 
m
t
t
t
n
t
z
F
z
F
z
F
z
z
z
F

2

1

2 1

...,
,
,




определяет вероятность следующих событий: “В
сечении
T
t 

ОДВНГ
 
 
 


t
G
t
G
P
X
t
G


,


будет иметь вершин не более чем


1
ˆ

j
z
n
”, “В
сечении
T
t 

ОДВНГ
 
 
 


t
G
t
G
P
X
t
G


,



ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
63
будет иметь дуг, проведённых из вершины
k
x в
вершину
r
x , не более чем


1

j
kr
z
n
”, “В сечении
T
t 

ОДВНГ
 
 
 


t
G
t
G
P
X
t
G


,


будет иметь
дуг, инцидентных вершинам
r
k
x
x ,
, не более чем




1 1



j
rk
j
kr
z
n
z
n
”,
“В сечении
T
t 

ОДВНГ
 
 
 


t
G
t
G
P
X
t
G


,


будет иметь дуг и петель не более чем


 



n
k
n
r
j
kr
z
n
1 1
1
”.
В реальных задачах моделирования случайных процессов на базе ОДВНГ прин- ципиально важным является знание того, каким образом в данном временном сечении закон распределения вершин графа влияет на распределение множеств дуг (петель). Пусть
 
t
1

- случайная функция, определяющая для каждого сечения
T
t 
номер элемента булеана множества вершин ОДВНГ (то есть указы- вающая те вершины
 
 
 


t
G
t
G
P
X
t
G
,

, кото- рые существуют в момент t ). Соответственно пусть
 
t
j

- случайная величина, опреде- ляющая, какие именно дуги из множества
 
 
 


jk
l
jk
jk
jk
jk
U
U
U
U
...,
,
,
2 1

существуют в сечении t . Рассмотрим вероят- ность события
 


 




2 1
1 1
j
j
j
k
t
k
n
t






,


2 1
2 1
1
;
,
,
j
j
j
j
k
k
N
k
k
n


. По теореме умножения имеем
 


 








2 1
1 1
j
j
j
k
t
k
n
t
P



 


 
 


1 1
2 1
1 1
n
t
k
t
k
P
n
t
P
j
j
j









То есть
 
 






1 1
2 1
n
t
k
t
k
P
j
j
j


 


 




 


1 1
2 1
1 1
n
t
P
k
t
k
n
t
P
j
j
j









Задача нахождения
 


1 1
n
t
P


была решена ранее. Найдём
 


 




2 1
1 1
j
j
j
k
t
k
n
t
P






В простейшем случае, когда события, состоящие в существовании конкретных мно- жеств вершин и дуг графа (в конкретном
временном сечении), являются независимыми
 


 








2 1
1 1
j
j
j
k
t
k
n
t
P



 




 




2 1
1 1
j
j
j
k
t
k
P
n
t
P







и задача решена. Пусть теперь события
 


 


2 1
1 1
,
j
j
j
k
t
k
n
t





- зависимы, тогда
 


 








2 1
1 1
j
j
j
k
t
k
n
t
P



 


 



























2 1
1 1
j
j
k
k
s
j
s
t
n
t
P


 








2 1
,
j
j
j
k
k
s
s
t
событий
ость
несовместн
учитывая

 


 





















2 1
1 1
j
j
k
k
s
j
s
t
n
t
P


 


 









2 1
1 1
j
j
k
k
s
j
s
t
n
t
P



Кажется очевидным, что вероятности событий
 


 




2 1
1 1
,
j
j
j
k
k
s
s
t
n
t






зависят от совокупности конкретных вершин и дуг, входящих во множество вершин (элемент булеана вершин с порядковым номером
1
n
) и множество дуг (элемент булеана дуг с поряд- ковым номером
s
), и поэтому определяются
(задаются) применительно к конкретной моде- лируемой ситуации.
Заключение. В данной статье предлагается и анализируется алгоритм построения модели случайного процесса на базе введённого ранее автором [1] нового объекта – обобщённого динамического вероятностного нагруженного графа. Даются определения основных сопут- ствующих понятий, анализируются особенности и характерные свойства процесса.
Библиографический список
1. Орлов Г.С. Динамические вероятностные нагруженные графы. Определения, свойства, области применения. –Вестник РГРТУ. № 1 (выпуск 31).
Рязань, 2010. – С. 48 – 57.
2. Гихман И.И., Скороход А.В. Введение в теорию случайных процессов. – М.: Из–во «Наука»,
1965. – 655 с.