Графы сетей Петри

Для иллюстрации понятий теории сетей Петри гораздо более удобно графическое представление сети Петри. Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф.

Структура сети Петри представляет собой совокупность позиций
и переходов. В соответствии с этим граф сети Петри обладает двумя
типами узлов. Кружок О является позицией, а планка │ - переходом.

Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие — от переходов к позициям. Дуга, направленная от позиции pi к переходу tj, определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.

Сеть Петри есть мультиграф, так как он допускает существование кратных дуг от одной вершины графа к другой. Следует добавить, что так как дуги являются направленными, то это ориентированный мультиграф. Мы знаем, что вершины графа можно разделить на два множества (позиции и переходы) таким образом, что каждая дуга будет направлена от элемента одного множества (позиций или переходов) к элементу другого множества (переходов или позиций); следовательно, такой граф является двудольным ориентированным мультиграфом. В дальнейшем для простоты будем называть его просто графом сети Петри.

Определение 3. Граф G сети Петри есть двудольный ориентированный мультиграф, G = (V, А), где V= { v1, v2,..., vn} - множество вершин, а А = {а1 а2,..., аm} - комплект направленных дуг, at = (vj, vk), где vj, vk принадлежат V. Множество V может быть разбито на два непересекающихся подмножества Р и Т, таких, что V = Р U Т, Р&Т = 0, и для любой направленной дуги at = (vj, vk), принадлежащей А, либо vj принадлежит V и vk принадлежит T, либо vj принадлежит T и vk принадлежит V.

Графы сети Петри, изображенные на рис. 4.4 — 4.6, эквивалентны структурам сети Петри на рис. 4.1 — 4.3.

Рис. 4.1 Граф сети Петри G1

Для демонстрации эквивалентности этих двух представлений сети Петри - структуры сети Петри и графа сети Петри - покажем, каким образом можно преобразовать один в другой. Предположим, нам дана структура сети Петри С = (Р, Т, I, О) с Р = {p1, p2, …, pn} и Т = {t1, t2,..., tm}. Тогда граф сети Петри можно определить следующим образом.

Определение 4. Определим V = Р U Т. Определим А как комплект направленных дуг, такой, что для всех pi, принадлежащих P и tj, принадлежащих Т:

#((tj,pi),A)=#(pi,О (tj)), #((pi,tj),A)=#(pi,I (tj)).

G = (V, А) есть граф сети Петри, эквивалентный структуре сети Петри С = (Р, Т, I, О).

Рис» 4. Граф сети Петри, эквивалентный структуре, показанной на рис. 1.

Рис. 2.5. Граф сети Петри, эквивалентный структуре, изображенной на Рис. 2.2.

Рис. 2.6. Граф сети Петри, эквивалентный структуре, показанной на рис. 2.3.

Обратное преобразование (от графа сети Петри к структуре) осуществляется подобным образом. Однако при переходе от графа сети Петри к структуре сети Петри возникает одна интересная задача: если множество вершин можно разделить на два подмножества S и R, то какое из этих подмножеств должно быть позициями, а какое - переходами? Оба возможных варианта позволяют определить сеть Петри, хотя в получающихся в результате структурах позиции и переходы меняются местами.

Двойственной к сети Петри С = (Р, Т, I, О) является сеть Петри С = (T, Р, I, О), которая получается в результате перестановки позиций и переходов. Структура графа сохраняется, просто меняются местами кружки и планки.

Рис. 2.7. Сеть, двойственная к сети Петри, показанной на рис. 2.4.

На рис. показана сеть, двойственная к сети Петри на рис. 2.4. Двойственность — обычно полезный прием в теории графов и кажется интересным понятием для сетей Петри. Однако никакой пользы извлечь из понятия двойственной сети Петри в исследовании этих сетей не представляется возможным. Это объясняется в основном трудностью определения сети, двойственной к маркированной сети Петри. Маркированные сети Петри мы обсудим позднее.