Графы и сети. Харитонова Е.В. - 47 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

46
2.2 Сети Петри
В этом пункте продолжается рассмотрение двудольных графов с ориен-
тированными ребрами. Однако, ориентация ребер допускается в обоих направ-
лениях. Пусть
G(V, E) – двудольный ориентированный граф, в котором V = P ∪
T. Множество Р называется множеством позиций, а множество Т – множеством
переходов. Е – множество ориентированных ребер между Р и Т. В рассмотрение
включено также множество функций
М таких, что каждая функция
µ
∈ М ста-
вит в соответствие неотрицательное целое число каждому элементу множества
Р. Функция
µ
называется разметкой графа G. Ориентированный граф, обла-
дающий такими свойствами, называется
сетью Петри.
Сети Петри используются главным образом для моделирования парал-
лельных процессов: для моделирования компонентов компьютера, параллель-
ных вычислений, в робототехнике и даже ля описания музыкальных структур.
Вообще, сети Петри используются для нахождения дефектов в проекте систе-
мы, хотя имеют и многие другие применения. Они обладают многими свойст-
вами блок-схем и
конечных автоматов, речь о которых пойдет дальше. Более
подробно.
Каждая позиция в сети Петри обозначена кружком, а каждый переход –
вертикальной линией. Если
р – позиция, то ƒ(р) называется разметкой позиции
р. Разметка множества G показана на графе с помощью больших черных точек,
называемых метками, помещенных в кружки, которые обозначают позиции.
Если кружок позиции
р пуст, это означает, что в р меток нет, поэтому ƒ(р) = 0.
Рассмотрим граф, изображенный на рис. 2.20. В этой сети Петри
р
1
и р
2
–
позиции, а
t
1
– переход. Позиция р
1
содержит одну метку, а р
2
– меток не со-
держит.
Рис. 2.20
Срабатывание перехода t – это удаление по одной метке из каждой пози-
ции
р
i
, так что имеется ориентированное ребро из р
i
в t, и добавление метки в
каждую позицию
р
i
, так что имеется ориентированное ребро из t в р
i
.
Например, срабатывание t
1
в приведенном выше примере приводит к сети Петри,
изображенной на рис. 2.21.
Рис. 2.21
●
р
1
р
2
t
1
●
р
1
р
2
t
1

Страницы