Синтез цифровых автоматов. Захаров Н.Г - 106 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

105
Определим, что переход t
j
является входом позиции p
i
, если p
i
есть выход t
j
. Переход t
j
есть выход позиции p
i
, если p
i
есть вход t
j
.
7.2.2. Графы сетей Петри
Наглядность сетевого моделирования систем существенно повышается, если
использовать теоретико-графовое представление сети Петри в виде двудольного ори-
ентированного мультиграфа.
В соответствии с данным подходом структура сети Петри представляет собой
совокупность позиций и переходов, а граф сети – два типа узлов, соединенных дуга-
ми (стрелками).
Кружок О является позицией, а планка | – переходом. Ориентированные дуги
соединяют позиции и переходы, при этом одни дуги направлены от позиций к пере-
ходам, а другие – от переходов к позициям. Дуга, направленная от позиции р
i
к пере-
ходу t
j
, определяет позицию, которая является входом перехода. Кратные входы в пе-
реход указываются кратными дугами из входных позиций в переход. Выходная пози-
ция указывается дугой от перехода к позиции. Кратные выходы также представлены
кратными дугами.
Сеть Петри есть мультиграф, так как он допускает существование кратных дуг
от одной вершины графа к другой. Следует добавить, что так как дуги являются на-
правленными, то это ориентированный мультиграф. Вершины графа можно разделить
на два множества (позиции и переходы) таким образом, что каждая дуга будет на-
правлена от элемента одного множества (позиций или переходов) к элементу другого
множества (переходов или позиций); следовательно, такой граф является двудольным
ориентированным мультиграфом. В дальнейшем для простоты будем называть его
просто графом сети Петри.
Определение. Граф G сети Петри есть двудольный ориентированный мульти-
граф G = (V, A), где
V = {v
1
, v
2
, ..., v
s
} – множество вершин;
А = {а
1
, а
2
, ..., а
r
} – комплект направленных дуг;
а
i
= (v
j
, v
k
), где v
j
, v
k
∈ V.
Множество V может быть разбито на два непересекающихся подмножест-
ва Р и Т, таких, что V = Р ∨ Т и P ∧ Т = ∅. Кроме того для любой направленной
дуги a
i
∈ А, если а
i
= (v
j
, v
k
), при условии, что тогда либо v
j
∈ Р и v
k
∈ Т, либо v
j
∈ Т и
v
k
∈ Р.
Для демонстрации эквивалентности двух представлений сети Петри: структуры
сети Петри и графа сети Петри (рис. 7.2 и 7.3) – покажем, каким образом можно пре-
образовать одно представление сети в друге.
Предположим, что дана структура сети Петри С = (Р, Т, I, О) с Р = {р
1
, p
2
, ..., p
n
}
и Т = {t
1
, t
2
, ..., t
m
}. Тогда граф сети Петри можно определить следующим образом.
Пусть V = Р ∨ Т. Определим А как комплект направленных дуг, такой что для
всех р
i
∈ Р и t
j
∈ Т
# ((p
i
, t
j
), A) = # (p
i
, I(t
j
));
# ((t
j
, p
i
), A) = # (p
i
, O(t
j
)),
тогда G (V, A) есть граф сети Петри, эквивалентный структуре сети Петри
С = (Р, Т, I, О).
Структура сети Петри С(Р, Т, I, О), где

Страницы