2.3

Для демонстрации эквивалентности этих двух представлений сети Петри — структуры сети Петри и графа сети Петри — покажем, каким образом можно преобразовать один в другой. Предположим, нам дана структура сети Петри С — (Р, Т, /, О) с Р = = {ри Ръ рп}и.т = {tu t2,..., tm}• Тогда граф сети Петри можно определить следующим образом.

Определение 2.4. Определим V = Р U Т. Определим А как комплект

направленных дуг, такой,

что для всех Рі£ Р и tj £ Т

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

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

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

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

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

Упражнения

1.   Постройте графы сетей Петри, двойственные к сетям Петри, показанным на рис. 2.5 и 2.6.

2.   Постройте граф сети Петри для следующей структуры сети Петри:

Р = {ри Р*> РЗ, рі}> т = {h, h, із, *4,

3.   Изобразите граф сети Петри следующей структуры:

Р = {ply Р2}, Т = {<і, fe, fe},

4.   Покажите, что двойственная к двойственной сети Петри С есть сама сеть С.

5.   Определите класс сетей Петри, которые совпадают с двойственными к себе. Можете ли вы дать простую характеризацию этого класса сетей Петри? в. Если сеть, двойственная к сети Петри С = (Р, Т, I, О), определена как С — (Т, Р, I, О), входные и выходные функции должны быть расширены для отображения и Я, и Т. Почему? Если С — (Р, Т,1, О) имеет нерасширенные входные и выходные функции, дайте определение С — (Т, Р, О') с нерасширенными входными и выходными функциями.

7.   Найдите структуру сетн Петри, соответствующую графу сети Петри на рис. 2.8. Определите структуру сети Петри для графа на рис. 2.9.

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

Рис. 2.10 иллюстрирует переход с входной кратностью 7 и выходной кратностью 11. Нарисуйте граф сети Петри для следующей структуры:

(Рі. Рг, Рз, рі), Т = {fi, І2, ta, ti}.

тор ц определяет для каждой позиции р-г сети Петри количество фишек в этой позиции. Количество фишек в позиции рг есть ц,г, і — 1, ..., п. Связь между определениями маркировки как функции и как вектора очевидным образом устанавливается соотношением ц(рг) = Ці- Обозначение ее в виде функции является несколько более общим и поэтому употребляется гораздо чаще.

Маркированная сеть Петри М = (С, |л) есть совокупность структуры сети Петри С = (Р, Т, 1,0) и маркировки jj, и может быть записана в виде М — (Р, Т, I, О, ц).

На графе сети Петри фишки изображаются маленькой точкой в кружке, который представляет позицию сети Петри. На рис. 2.11 и 2.12 приведены примеры графического представления маркированной сети Петри.

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

вует бесконечно много маркировок. Множество всех маркировок сети Петри, обладающей п позициями, есть множество всех «-векторов, Nn. Это множество, хотя и бесконечно, является счетным.

Упражнения

1.   Для маркированной сети Петри (рис. 2.12) представьте маркировку как функцию и как вектор.

2.   Для структуры сети Петри (рис. 2.2) изобразите граф сети Петри и укажи- те на графе маркировку р. = (1,0, 1, 1, 0, 0).

3.   Количество фншек в сети Петри редко превышает 5 или 6. В этом случае их рисуют. Однако, когда маркировка имеет 10, 20 или сотни фишек, приписанных позиции, в кружках удобнее не рисовать фишки, а указывать их общее количество, как на рис. 2.13. Используя этот способ, изобразите маркировку р = (137, 22, 2, 0, 14) для сети Петри на рис. 2.12.