Правила выполнения сетей Петри

Маркировка сетей Петри

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

Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф G = (V, A), где

V = { v ₁, v ₂,..., v_s } – множество вершин;

А = { a ₁, a ₂,..., a_r } – комплект направленных дуг a_i = { v_j, v_k }, где v_j, v_k Î V.

Множество V может быть разбито на два непересекающихся подмножества P и T (P Ç T = 0), и если a_i = (v_j, v_k), тогда либо v_j Î P и v_k Î T, либо v_j Î T и v_k Î P.

Сеть Петри есть ориентированный мультиграф, т.к. он допускает существование направленных кратных дуг от одной вершины к другой. Граф является двудольным, т.к. он допускает существование вершин двух типов: позиций (кружок O) и переходов (планка |).

Ориентированные дуги соединяют позиции и переходы. Дуга, направленная от позиции p_i к переходу t_j, определяет позицию, которая является входом перехода t_j. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.

Оба представления сети Петри – в виде структуры и в виде графа – эквивалентны. Их можно преобразовать друг в друга.

Маркировка m есть присвоение фишек позициям сети Петри. Фишка – это одна из компонент сети Петри (подобно позициям и переходам). Фишки присваиваются позициям. Их количество при выполнении сети может изменяться. Фишки используются для отображения динамики системы.

Маркированная сеть Петри есть совокупность структуры сети Петри C = (P, T, I, O) и маркировки m и может быть записана в виде M = (P, T, I, O, m). На графе сети Петри фишки изображаются крупными точками в кружке, который представляет позицию сети Петри. Количество фишек (точек) для каждой позиции не ограничено и, следовательно, в целом для сети существует бесконечно много маркировок. Множество всех маркировок сети, имеющей n позиций, является множеством всех n векторов, т.е. Nⁿ. Очевидно, что хотя это множество и бесконечно, но оно счетно. Когда маркировка превышает 4 или 5 фишек, то в кружках не рисуют фишки, а указывают их количество.

Структура сети Петри может оставаться неизменной, а маркировка сети может меняться.

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

Переход запускается, если он разрешен. Переход t_j Î T маркированной сети Петри M = (P, T, I, O, m) с маркировкой m разрешен, если для всех p_i Î P m(p_i) ³ #(p_i, I (t_j)), т.е. если каждая из его входных позиций имеет число фишек, по крайней мере, равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками.

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

Переход t_j в маркированной сети Петри с маркировкой m может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода t_j образуется новая маркировка m':

m'(p_i) = m(p_j) – #(p_i, I (t_j)) + #(p_i, O (t_j))

5.2. Сети Петри для моделирования систем: способы реализации