СТРУКТУРА СЕТИ ПЕТРИ
Сеть Петри состоит из четырех элементов: множество позиций Р, множество переходов Т, входная функция I и выходная функция O. Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t j в множество позиций I (t j), называемых входными позициями перехода. Выходная функция O отображает переход t j в множество позиций O (t j), называемых вы-ходными позициями перехода.
Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.
Определение 1.1. Сеть Петри С является четверкой С = (Р, Т, I, О). Р ={ p 1, p 2,¼, pn }–конечное множество позиций, n ≥ 0. Т =
= { t 1, t 2, ¼, tm } – конечное множество переходов, m ≥ 0. Множество
позиций и множество переходов не пересекаются, P ∩ T = 0. I: T ® P ¥является входной функцией–отображением из переходов в
комплекты позиций. O: T ® P ¥ есть выходная функция – отображение из переходов в комплекты позиций.
Мощность множества Р есть число n, а мощность множества T есть число m. Произвольный элемент Р обозначается символом pi, i = 1, …, n,а произвольный элемент Т –символом t j, j = 1, …, m.
Примеры сетей Петри даны на рис. 1.1–1.4.
Позиция pi является входной позицией перехода t j в том случае, если pi Î I (t j); pi является выходной позицией, если pi Î O (t j). Вхо-ды и выходы переходов представляют собой комплекты позиций. Комплект является обобщением множества, в которое включены мно-гократно повторяющиеся элементы – тиражированные элементы. Ис-пользование комплектов, а не множеств для входов и выходов перехо-да позволяет позиции быть кратным входом либо кратным выходом перехода. Кратность входной позиции pi для перехода t j есть число
появлений позиции во входном комплекте перехода, #(pi, I (t j)). Ана-логично кратность выходной позиции pi для перехода t j есть число появлений позиции в выходном комплекте перехода, #(pi, O (t j)). Если входная и выходная функции являются множествами (а не комплекта-ми), то кратность каждой позиции есть либо 0, либо 1.
Входные и выходные функции используются для отображений по-зиций в комплекты переходов, а также их можно использовать для отображения переходов в комплекты позиций. Определим, что пере-ход t j является входом позиции pi, если pi есть выход t j. Переход t j
есть выход позиции pi, если pi есть вход t j.
С = (Р, Т, I, О),
P = { p 1, p 2, p 3, p 4, p 5},
T ={ t 1, t 2, t 3, t 4},
I (t 1)={ p 1} O (t 1)={ p 2, p 3, p 5}
I (t 2)={ p 2, p 3, p 5} O (t 2)={ p 5}
I (t 3)={ p 3} O (t 3)={ p 4}
I (t 4)={ p 4} O (t 4)={ p 2, p 3}
Рис. 1. 1. Структура сети Петри
С = (Р, Т, I, О),
P = { p 1, p 2, p 3, p 4, p 5, p 6},
T ={ t 1, t 2, t 3, t 4, t 5},
| I (t 1)={ p 1} | O (t 1)={ p 2, p 3} |
| I (t 2)={ p 3} | O (t 2)={ p 3, p 5, p 5} |
| I (t 3)={ p 2, p 3} | O (t 3)={ p 2, p 4} |
I (t 4)={ p 4, p 5, p 5, p 5} O (t 4)={ p 4}
I (t 5)={ p 2} O (t 5)={ p 6}
Рис. 1. 2. Структура сети Петри
С = (Р, Т, I, О),
P = { p 1, p 2, p 3, p 4, p 5, p 6, p 7, p 8, p 9},
T ={ t 1, t 2, t 3, t 4, t 5, t 6},
I (t 1)={ p 1} O (t 1)={ p 2, p 3}
I (t 2)={ p 8} O (t 2)={ p 1, p 7}
I (t 3)={ p 2, p 5} O (t 3)={ p 6}
I (t 4)={ p 3} O (t 4)={ p 4}
I (t 6)={ p 4, p 9} O (t 6)={ p 5, p 8}
Рис. 1. 3. Структура сети Петри
С = (Р, Т, I, О),
P = { p 1, p 2, p 3, p 4},
T ={ t 1, t 2, t 3, t 4, t 5, t 6},
I (t 1)={ p 1} O (t 1)={ p 2}
I (t 2)={ p 1} O (t 2)={ p 2, p 3}
I (t 3)={ p 1} O (t 3)={ p 3, p 3}
I (t 4)={ p 2} O (t 4)={ p 3}
I (t 5)={ p 3, p 3} O (t 5)={ p 4}
I (t 6)={ p 4} O (t 6)={ p 1}
Рис. 1. 4. Структура сети Петри
Определение 1.2. Определим расширенную входную функцию I ивыходную функцию O.
I: P ® T ¥, O: P ® T ¥таким образом,что
# (t j, I (pi)) = # (pi, O (t j)), # (t j, O (pi)) = # (pi, I (t j)).
Для сети Петри на рис. 1.1 расширенными входной и выходной функциями являются:
С = (Р, Т, I, О), P ={ p 1, p 2, p 3, p 4}, T ={ t 1, t 2, t 3, t 4, t 5, t 6},
I (p 1)={}, O (p 1)={ t 1},
I (p 2)={ t 1, t 4}, O (p 2)={ t 2},
I (p 3)={ t 1, t 4}, O (p 3)={ t 2, t 3},
I (p 4)={ t 3}, O (p 4)={ t 4},
I (p 5)={ t 1, t 2}. O (p 5)={ t 2}.
ГРАФЫСЕТЕЙ ПЕТРИ
В значительной степени теоретическая работа по сетям Петри ос-нована на их формальном определении, изложенном выше. Тем не ме-нее для иллюстрации понятий теории сетей Петри гораздо более удоб-но их графическое представление. Теоретико-графовым представлени-ем сети Петри является двудольный ориентированный мультиграф.
Структура сети Петри представляет собой совокупность позиций и переходов. В соответствии с этим граф сети Петри обладает двумя ти-пами узлов. Кружок 
является позицией, а планка | – переходом.
Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, дру-гие – от переходов к позициям. Дуга, направленная от позиции pi к переходу t j, определяет позицию, которая является входом перехода.
Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода
к позиции. Кратные выходы также представлены кратными дугами. Сеть Петри есть мультиграф, так как он допускает существование
кратных дуг от одной вершины графа к другой. Следует добавить, что так как дуги являются направленными, то это ориентированный муль-тиграф. Мы знаем, что вершины графа можно разделить на два множе-ства (позиции и переходы) таким образом, что каждая дуга будет направлена от элемента одного множества (позиций или переходов) к элементу другого множества (переходов или позиций); следовательно, такой граф является двудольным ориентированным мультиграфом.
В дальнейшем для простоты будем называть его просто графом сети Петри.
Определение 1.3. Граф G сети Петри есть двудольный ориентиро-ванный мультиграф, G = (V, А), где V = { v 1, v 2,¼, vs } – множество вер-шин, а А = { a 1, a 2,¼, ar } – комплект направленных дуг, ai = (v j, vk), где v j, vk Î V. Множество V может быть разбито на два непересекаю-
щихся подмножества Р и Т, таких, что V = Р Т, Р Т = Ø, и для лю-бой направленной дуги ai Î А, если ai = (v j, vk), тогда либо v j, Î Р,
vk Î Т,либо v j,Î Т, vk Î Р.
Графы сети Петри, изображенные на рис. 1.5–1.8, эквивалентны соответственно структурам сети Петри на рис. 1.1–1.4.
| Рис. 1. 5. Граф сети Петри на рис. 1.1 | Рис. 1. 6. Граф сети Петри | |
| на рис. 1.2 | ||
| Рис. 1. 7. Граф сети Петри на рис. 1.3 | Рис. 1. 8. Граф сети Петри | |
| на рис. 1.4 | ||
Для демонстрации эквивалентности этих двух представлений сети Петри (структуры сети Петри и графа сети Петри) покажем, каким об-разом можно преобразовать один в другой. Предположим, нам дана структура сети Петри С = (Р, Т, I, О) с Р = { p 1, p 2, ¼, pn },
Т = { t 1, t 2,¼, tm }. Тогда граф сети Петри можно определить следую-щим образом.
Определение 1.4. Определим V = P T. Определим А как комплектнаправленных дуг, такой, что для всех pi Î Р и t j Î Т,
#((pi, t j), А) = #(pi, I (t j)), #(t j, pi), А) = #(pi, O (t j)).
G = (V, А) –граф сети Петри,эквивалентный структуре сети Петри
С = (Р, Т, I, О).
Обратное преобразование (от графа сети Петри к структуре) осу-ществляется подобным образом. Однако при переходе от графа сети Петри к структуре сети Петри возникает одна интересная задача: если множество вершин можно разделить на подмножества S и R, то какое из этих подмножеств должно быть позициями, а какое – переходами? Оба возможных варианта позволяют определить сеть Петри, хотя в получающихся в результате структурах позиции и переходы меняются местами.
Двойственной к сети Петри С = (Р, Т, I, О) является сеть Петри C =
= (Т, Р, I, О), которая получается в результате перестановки позиций и переходов. Структура графа сохраняется, просто меняются местами кружки и планки. На рис. 1.9, 1.10 показаны сети, двойственные к се-тям Петри, представленных на рис. 1.5 и 1.8.
Рис. 1. 9. СП,двойственная к СП Рис. 1. 10. СП,двойственная к СП
на рис. 1.5 на рис. 1.8
| Рис. 1. 11. СП,инверсная к СП | Рис. 1. 12. Пучок дуг | |
| на рис. 1.8 | ||
Инверсная сеть Петри для С = (Р, Т, I, О), определяется переста-новкой входной и выходной функций С ¢ = (Р, Т, О, I), т. е. граф для сети Петри, инверсной сети Петри на рис. 1.8, будет выглядеть, как на рис. 1.11.
Графы сети Петри являются мультиграфами, так как позиция мо-жет быть кратным входом или выходом перехода. В графе это показы-вается несколькими дугами между позицией и переходом. В то время как такой способ удовлетворителен для дуг с малой кратностью (не более трех), он неудобен для дуг очень большой кратности. Таким об-разом, в качестве альтернативного представления структур с большой краткостью используется пучок дуг. Пучок – это специальная дуга, которая рисуется жирной линией и помечается кратностью. Рис. 1.12 иллюстрирует переход с входной кратностью 7 и выходной кратно-стью 11.
МАРКИРОВКА СЕТЕЙ ПЕТРИ
Маркировка μесть присвоение фишек позициям сети Петри.Фиш-ка – это примитивное понятие сетей Петри (подобно позициям и пере-ходам). Фишки присваиваются (можно считать, что они принадлежат) позициям. Количество и положение фишек при выполнении сети Пет-ри могут изменяться. Фишки используются для определения выполне-ния сети Петри.
Определение 1.5. Маркировка μсети Петри С = (Р, Т, I, О)естьфункция, отображающая множество позиций Р в множество неотрица-тельных целых чисел N. μ: Р → N.
Маркировка μ может быть также определена как n -вектор m =
= (m1, m 2, ¼, m n), где n = |P| и каждое m i Î N, i = 1, …, n. Вектор μ определяет для каждой позиции pi сети Петри количество фишек в этой позиции. Количество фишек в позиции pi есть m i, i = 1, …, n. Связь между определениями маркировки как функции и как вектора очевидным образом устанавливается соотношением m (pi) = m i. Обо-
значение ее в виде функции является несколько более общим и поэто-му употребляется гораздо чаще.
Маркированная сеть Петри M = (C, μ)есть совокупность структу-ры сети Петри С = (Р, Т, I, О) и маркировки μ и может быть записана в виде M = (Р, Т, I, О, μ).
На графе сети Петри фишки изображаются маленькой точкой в кружке, который представляет позицию сети Петри. На рис 1.13 при-веден пример графического представления маркированной сети Петри.
Так как количество фишек, которое может быть определено для каждой позиции, неограниченно, то в целом для сети Петри существу-ет бесконечно много маркировок. Множество всех маркировок сети
Петри, обладающей n позициями, есть множество всех n -векторов, N n.
Это множество, хотя и бесконечно, но является счетным.
| Рис. 1. 13. Маркированная сеть Петри | Рис. 1. 14. Сеть Петри с большой | |
| маркировкой | ||
Количество фишек в сети Петри редко превышает 5 или 6. В этом случае их рисуют. Однако, когда маркировка имеет 10, 20 или сотни фишек, приписанных позиции, в кружках удобнее не рисовать фишки, а указывать их общее количество, как на рис. 1.14.
ПРАВИЛА ВЫПОЛНЕНИЯ СЕТЕЙ ПЕТРИ
Выполнением сети Петри управляет количество и распределениефишек в сети. Фишки находятся в кружках и управляют выполнением переходов сети. Сеть Петри выполняется посредством запусков пере-ходов. Переход запускается удалением фишек из его входных позиций
и образованием новых фишек, помещаемых в eго выходные позиции. Переход может запускаться только в том случае, когда он разре-
шен. Переход называется разрешенным,если каждая из его входныхпозиций имеет число фишек, по крайней мере, равное числу дуг из по-зиции в переход. Кратные фишки необходимы для кратных входных дуг. Фишки во входной позиции, которые разрешают переход, назы-
ваются его разрешающими фишками. Например, если позиции p 1 и р 2служат входами для перехода t 4,тогда t 4разрешен,если p 1и р 2имеют хотя бы по одной фишке. Для перехода t 7 с входным комплек-том { р 6, р 6, р 6} позиция р 6 должна обладать, по крайней мере, тремя фишками, для того чтобы t 7 был разрешен.
Определение 1.6. Переход tj Î Т в маркированной сети ПетриС = (Р, Т, I, О) с маркировкой μ разрешен, если для всех pi Î P
μ (pi) ≥ #(pi, I (t j)).
Переход запускается удалением всех разрешающих фишек из его входных позиций и последующим помещением в каждую из его вы-ходных позиций по одной фишке для каждой дуги. Кратные фишки создаются для кратных выходных дуг. Переход t 3 с I (t 3) = { р 2} и O (t 3)={ р 7, p 13}разрешен всякий раз,когда в p 2будет хотя бы однафишка. Переход t 3 запускается удалением одной фишки из позиции р 2и помещением одной фишки в позицию р 7и в p 13(его выходы).Дополнительные фишки в позиции р 2 не влияют на запуск t 3 (хотя они могут разрешать дополнительные запуски t 3). Переход t 2, в кото-ром I (t 2) = { р 21, p 23} и O (t 2) = { р 23, p 25, p 25}, запускается удалением одной фишки из р 21 и одной фишки из p 23, при этом одна фишка по-мещается в р 23 и две – в p 25 (так как p 25 имеет кратность, равную двум).
Запуск перехода в целом заменяет маркировку μ сети Петри на маркировку m¢. Заметим также, что поскольку можно запустить только
разрешенный переход, при запуске перехода количество фишек в каж-дой позиции всегда остается неотрицательным. Запуск перехода нико-гда не удалит фишку, отсутствующую во входной позиции. Если ка-кая-либо входная позиция перехода не обладает достаточным количе-ством фишек, то переход не разрешен и не может быть запущен.
Определение 1.7. Переход tj в маркированной сети Петри смаркировкой μ может быть запущен всякий раз, когда он разрешен.
В результате запуска разрешенного перехода t j образуется новая мар-кировка μ', определяемая следующим соотношением:
m ¢(pi) = m (pi) – #(pi, I (t j)) + #(pi, O (t j)).
В качестве примера рассмотрим маркированную сеть Петри, изоб-раженную на рис. 1.8. При такой маркировке разрешены переходы t 1, t 2, t 3.Переходы t 14, t 5, t 6не разрешены,так как ни одна из позиций р 2, р 3, р 4,являющихся входами этих переходов,не имеет фишек,т. е. ни один из переходов t 14, t 5, t 6 не может быть запущен. Если за-пущен переход t 2, то происходит удаление фишки из единственного входа р 1 и помещение двух фишек – по одной в выходы р 2 и р 3. Но-
вая маркировка, полученная в результате запуска, показана на рис. 1.15. Далее будем запускать последовательно разрешенные пере-ходы t 4, t 5, t 6, t 3, t 5, t 6, t 1, t 4. Результирующая маркированная сети Петри представлена на рис. 1.16.
| Рис. 1. 15. После запуска перехода t 2 | Рис. 1. 16. Окончательная | |
| маркировка | ||
Запуски могут производиться до тех пор, пока существует хотя бы один разрешенный переход. Когда не остается ни одного разрешенного перехода, выполнение прекращается.
Мы видим, что именно такая ситуация сложилась на последней маркировке. Для запуска перехода t 4 необходимо во входной позиции p 3иметь две разрешающие фишки,а у нас только одна.