4.2.1.3. Покрываемость

Последняя задача, которую можно решить с помощью дерева достижимости, — задача покрываемости. В задаче покрываемости мы хотим для данной маркировки р' определить, достижима ли маркировка р" > р'. Данная задача решается проверкой дерева достижимости. Строим для начальной маркировки р дерево достижимости. Затем ищем любую вершину х с р[х] р.'. Если такой вершины не существует, маркировка р' не покрывается никакой достижимой маркировкой; если она найдена, р[х] дает достижимую маркировку, покрывающую р'.

Путь от корня к покрывающей маркировке определяет последовательность переходов, которые приводят из начальной маркировки к покрывающей маркировке, а маркировка, связанная с этой «ершиной, определяет покрывающую маркировку. Символ со вновь Должен рассматриваться как обозначение бесконечного множества Значений. Если компонента покрывающей маркировки — о, то в ітути от корня к покрывающей маркировке имеется «цикл». Для

увеличения соответствующей компоненты с тем, чтобы она была не меньше, чем в данной маркировке, необходимо достаточное число раз_повторить этот цикл.

Заметим, что, если несколько компонент покрывающей маркировки равны со, между изменениями маркировки, получающимися в результате прохождения циклов, возможна взаимосвязь. Рассмотрим сеть Петри на рис. 4.18 и ее дерево достижимости, показанное на рис. 4.19. Согласно проведенному анализу, маркировка (0, 14, 1, 7) покрывается в множестве достижимости. Путь, порождающий покрывающую маркировку, состоит из некоторого числа переходов /ь за которыми следует переход t2, после которого уже следует некоторое число переходов ts. Задача заключается в определении того, сколько раз нужно запустить переходы tt и ts. Так как мы хотим иметь в позиции р2 14 фишек, а помещает в /?2 одну фишку, попытаемся

выполнить 14 tt. Однако нам необходимо выполнить 7ts, а каждый запуск t3 удаляет из р2 фишку, поэтому в действительности необходимо выполнить не менее 21 tu затем t2 и после этого не менее 7t3 (выполнить t3 такое число раз, чтобы в позиции р.г осталось не менее 14 фишек). Карп и Миллер [148] предложили алгоритм, определяющий минимальное число запусков переходов, необходимых для покрытия дайной маркировки.