Граф сети Петри. Пример графа сети Петри и описание сети Петри.
В значительной степени теоретическая работа по сетям Петри основана на формальном определении сетей Петри, изложенном выше. Тем не менее, для иллюстрации понятий теории сетей Петри гораздо более удобно графическое представление сети Петри. Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф.
Структура сети Петри представляет собой совокупность позиций и переходов. В соответствии с этим граф сети Петри обладает двумя типами узлов. Кружок О является позицией, а планка | — переходом.
Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие — от переходов к позициям. Дуга, направленная от позиции pi к переходу tj, определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.
Сеть Петри есть мультиграф, так как он допускает существование кратных дуг от од-ной вершины графа к другой. Следует добавить, что так как дуги являются направленными, то это ориентированный мультиграф. Мы знаем, что вершины графа можно разделить на два множества (позиции и переходы) таким образом, что каждая дуга будет направлена от элемента одного множества (позиций или переходов) к элементу другого множества (переходов или позиций); следовательно, такой граф является двудольным ориентированным мультиграфом. В дальнейшем для простоты будем называть его просто графом сети Петри.
Определение 2.3. Граф G сети Петри есть двудольный ориентированный мультиграф, 
, где 
— множество вершин, а 
— комплект направленных дуг, 
, где 
, Множество V может быть разбито на два непересекающихся подмножества 
и 
, таких, что 
, 
, и для любой направленной дуги 
, если , тогда либо 
и 
, либо 
а 
.
|
|
Для примера-1 эквивалентный граф имеет вид:
 
 
 
 
| 
|
Маркировка сети Петри. Формальное определение.
Маркировка 
есть присвоение фишек позициям сети Петри. Фишка — это примитивное понятие сетей Петри (подобно позициям и переходам). Фишки присваиваются (можно считать, что они принадлежат) позициям. Количество и положение фишек при выполнении сети Петри могут изменяться. Фишки используются для определения выполнения сети Петри.
Определение Маркировка сети Петри есть функция, отображающая множество позиций в множество неотрицательных целых чисел 
.
Маркировка , может быть также определена как 
-вектор 
, где 
и каждое 
. Вектор определяет для каждой позиции 
сети Петри количество фишек в этой позиции. Количество фишек в позиции есть 
. Связь между определениями маркировки как функции и как вектора очевидным образом устанавливается соотношением 
. Обозначение ее в виде функции является несколько более общим и поэтому употребляется гораздо чаще.
Маркированная сеть Петри 
есть совокупность структуры сети Петри и маркировки и может быть записана в виде 
.
На графе сети Петри фишки изображаются маленькой точкой в кружке, который представляет позицию сети Петри. На рис. 2.11 и 2.12 приведены примеры графического представления маркированной сети Петри.
|
|
ПРИМЕР 1 из предыдущей лекции
|
| 
|
Так как количество фишек, которое может быть определено для каждой позиции, неограниченно, то в целом для сети Петри существует бесконечно много маркировок. Множество всех маркировок сети Петри, обладающей позициями, есть множество всех -векторов, 
. Это множество, хотя и бесконечно, является счетным.