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

Для иллюстрации основных понятий теории сетей Петри наиболее удобным является графическое представление сетей Петри.

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

Дуга, направленная от позиции к переходу определяет позицию, которая является входом перехода . Аналогично, дуга, которая направлена от к определяет позицию, которая является выходом перехода .

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

Граф сети Петри можно представить как:

G = (V,A), где

V (vertex) – множество вершин. Может быть разбито на два не пересекающихся множества p и t таких, что пересечение p и t = 0 и любая дуга, если начинается из p, то должна идти к t. И наоборот. Граф сети Петри является бинарным, т.к. допускает существование вершин двух типов – позиций и переходов.

A (arc) –множество дуг.