Маркировка сетей Петри
Графы сетей Петри
Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф G = (V, A), где
V = { v 1, v 2,..., vs } – множество вершин;
А = { a 1, a 2,..., ar } – комплект направленных дуг ai = { vj, vk }, где vj, vk Î V.
Множество V может быть разбито на два непересекающихся подмножества P и T (P Ç T = 0), и если ai = (vj, vk), тогда либо vj Î P и vk Î T, либо vj Î T и vk Î P.
Сеть Петри есть ориентированный мультиграф, т.к. он допускает существование направленных кратных дуг от одной вершины к другой. Граф является двудольным, т.к. он допускает существование вершин двух типов: позиций (кружок O) и переходов (планка |).
Ориентированные дуги соединяют позиции и переходы. Дуга, направленная от позиции pi к переходу tj, определяет позицию, которая является входом перехода tj. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.
|
|
Оба представления сети Петри – в виде структуры и в виде графа – эквивалентны. Их можно преобразовать друг в друга.
Маркировка m есть присвоение фишек позициям сети Петри. Фишка – это одна из компонент сети Петри (подобно позициям и переходам). Фишки присваиваются позициям. Их количество при выполнении сети может изменяться. Фишки используются для отображения динамики системы.
Маркированная сеть Петри есть совокупность структуры сети Петри C = (P, T, I, O) и маркировки m и может быть записана в виде M = (P, T, I, O, m). На графе сети Петри фишки изображаются крупными точками в кружке, который представляет позицию сети Петри. Количество фишек (точек) для каждой позиции не ограничено и, следовательно, в целом для сети существует бесконечно много маркировок. Множество всех маркировок сети, имеющей n позиций, является множеством всех n векторов, т.е. Nn. Очевидно, что хотя это множество и бесконечно, но оно счетно. Когда маркировка превышает 4 или 5 фишек, то в кружках не рисуют фишки, а указывают их количество.
Структура сети Петри может оставаться неизменной, а маркировка сети может меняться.
Выполнением сети Петри управляют количество и распределение фишек в сети. Сеть Петри выполняется посредством запусков переходов. Переход запускается удалением фишек из его входных позиций и образованием новых фишек, помещаемых в его выходные позиции.
Переход запускается, если он разрешен. Переход tj Î T маркированной сети Петри M = (P, T, I, O, m) с маркировкой m разрешен, если для всех pi Î P m(pi) ³ #(pi, I (tj)), т.е. если каждая из его входных позиций имеет число фишек, по крайней мере, равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками.
|
|
Переход запускается удалением разрешающих фишек, из всех его выходных позиций (количество удаленных фишек для каждой позиции соответствует числу дуг, идущих из этой позиции в переход), с последующим помещением фишек в каждую из его выходных позиций (количество помещаемых фишек в позицию соответствует количеству дуг входящих в данную позицию из перехода).
Переход tj в маркированной сети Петри с маркировкой m может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода tj образуется новая маркировка m':
m'(pi) = m(pj) – #(pi, I (tj)) + #(pi, O (tj))
5.2. Сети Петри для моделирования систем: способы реализации