7.4.2.       Маркированные графы

Другим, часто упоминаемым в литературе подклассом сетей Петри является класс маркированных графов. Маркированный граф есть сеть Петри, в которой каждая позиция является входом для точно одного перехода и выходом точно одного перехода. Иначе говоря, мы можем сказать, что каждая позиция имеет точно один вход и один выход.

Определение 7.2. Маркированный граф есть сеть Петри С — (Р, Т, I, О), такая, что для каждой pt £ Р:

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

Изучены такие свойства маркированных графов, как активность, безопасность и достижимость. Наиболее интересными структурными компонентами маркированного графа при изучении указанных свойств являются его циклы. Цикл в маркированном графе — это последовательность переходов tj±, tj2, tjy ..., tJb— такая, что для каждой пары переходов t jr и tjT+1 из этой последовательности существует позиция ріт — такая, что pir £ 0(t jr) и р1т £ f(tjr+i).

Таким образом, цикл есть замкнутый путь из какого-либо перехода обратно в этот же переход.

Например, в маркированном графе на рис. 7.13 последовательность t^4\ является циклом, как и последовательности txt3tk и

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

Теорема 7.1. Число фишек в цикле маркированного графа не из- < меняется в результате запусков переходов.

Используя эту теорему, легко показать следующее.

Теорема 7.2. Маркировка является активной тогда и только тогда, когда в каждом цикле маркированного графа присутствует по меньшей мере одна фишка.

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

Эти теоремы предоставляют простой и легкий путь исследования структуры маркированного графа и определения из его структуры

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

Теорема 7.4. Маркировка р' достижима из активной маркировки р в сильно связном маркированном графе тогда и только тогда, когда общее число фишек в каждом цикле маркированного графа совпадает для маркировок р и р'.

Большая мощность разрешения маркированных графов очевидна из следующих теорем и работ по маркированным графам [127, 54, 91, 136, 2091. Однако существует связь между мощностью разрешения и мощностью моделирования, и высокая мощность разрешения маркированных графов частично проистекает из низкой мощности моделирования. Поэтому исследователи пытались выделить другие подклассы сетей Петри, которые оставляли бы высокой мощность разрешения маркированных графов и увеличивали их мощность моделирования.