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

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

Граф – совокупность непустого множества вершин и множества дуг (рёбер), представляющих собой набор пар вершин, задающий связи между вершинами.

Вершины и дуги называются элементами графа.

Если в наборе пар вершин при задании дуг графа учитывается порядок их следования (например: (a, b) и (b, a)), то граф называется ориентированным, если нет – то неориентированным. В ориентированном графе каждая дуга имеет начало и конец. Граф, содержащий как направленные, так и не направленные дуги, называется смешанным.

Граф называется двудольным, если его вершины можно разбить на два непересекающихся подмножества A и B так, что всякая дуга соединяет вершину из подмножества A с вершиной из подмножества B (т.е. нет дуг, соединяющих вершины одного и того же подмножества).

Если разные дуги в графе имеют одинаковые начала и концы, то такие дуги называются кратными.

Граф, в котором разрешено использование кратных дуг, называется мультиграфом (или псевдографом).

Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф.

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

Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие – от переходов к позициям.

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

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

Граф сети Петри, изображённый на рис.5.2, эквивалентен структуре сети Петри из вышеприведённого примера.

Рис. 5.2

Для графов с большой кратностью используется пучок дуг, помеченный числом кратности, а не изображением кратных дуг (рис.5.3).

Рис. 5.3

Дата добавления: 2014-12-16