RT - 
SR - Electronic
T1 - ЗАМЕЧАНИЯ ОБ ИЗОМОРФИЗМАХ ГРАФОВ СЕТЕЙ ПЕТРИ
SP - 2023-03-27
A1 - Белов, Ю. А.
YR - 2023
UL - https://rep.herzen.spb.ru/publication/374
AB - Определения. Сеть Петри D(P, T) есть двудольный ориентированный граф со взвешенными дугами [ 1 ]. Вершины доли Р называются позициями, вершины доли Т -переходами, РГ\Т = ©.Размерность сети есть \Р\ = d. Множество дуг это F с (РхТ)и (Т х Р). w : F -> N = {0,1,2,...} - весовая функция, определяющая кратность дуг. Если кратность дуги равна нулю, то считаем, что соответствующая дуга отсутствует. Остальные дуги, т.е. дуги с положительными кратностями, образуют для каждого перехода t входные дуги: (р, t) е (Р х Т) и соответственно, выходные дуги (t, р) e (Т х Р) с соответствующими весами. Вектор in{t) = (w(p,t)\p е Р) кратностей входящих дуг называется вектором ресурсов, потребляемых данным переходом t, вектор out(t) = (w(t,p)\p е Р) вектором производимых ресурсов. Вектор ö{tt) = outiti) - initi) назовём вектором сдвига данного перехода. Состоянием сети D называется целочисленный неотрицательный вектор s = (pi,P2, ■■■Pd), задающий количество абстрактных неименованных фишек, располагаемых в каждой позиции, то есть одно из значений отображения Р -> Nd. О функционировании сети [1]. Переход ?г называется активным (допустимым) в данном состоянии s, если выполняется неравенство s > initi) при покомпонентном 241 сравнении. Другими словами, количество имеющихся фишек в текущем состоянии сети не менее количества потребляемых ресуров данного перехода (для каждой позиции). Каждый переход, активный в данном состоянии, может привести к изменению состояния, как говорят, может «сработать». Изменение состояния сети происходит по правилу: s = s - initi) + outiti) = s + 6(ti), что часто обозначается следующим образом: s A s . Таким образом, активные переходы могут перераспределять ресурсы (фишки) по позициям. Если в данном состоянии допустимы (активны) несколько переходов, то сеть может перейти в любое из допустимых состояний. Рассматривая всевозможные конечные цепочки допустимых переходов, начинающиеся из состояния sq, получаем множество Re (so) всевозможных состояний, достижимых из данного начального состояния. Хотя данное множество может быть и бесконечным, оно имеет естественную структуру ориентированного графа с выделенным начальным состоянием. При этом все вершины достижимы из начальной с учётом ориентации, и все вершины можно считать помеченными неотрицательными векторами, указывающими текущее «распределение ресурсов по позициям». Можно считать, что такой конечный граф является подграфом некоторого полного ориентированного графа порядка d без петель и параллельных дуг с выделенной вершиной. При этом полустепень захода и полустепень исхода каждой вершины равна d - 1. Возникает естественный вопрос: какие графы изоморфны, как ориентированные графы, графам Re (so) достижимости подходящих сетей Петри. Такие графы будем называть моделируемыми. Можно проверить, что конечный полный ориентированный граф, отмеченный ранее, является моделируемым. При этом он моделируется даже неизоморфными сетями, например, сетями различных размерностей. Вообще, для конечных графов многое ясно, а для бесконечных графов, а графы Re (so) могут быть и бесконечными, на основные вопросы пока нет хороших ответов. Результаты. Предложение 1. Всякий конечный ориентированный граф G порядка d без петель и параллельных дуг моделируется некоторой сетью Петри порядка d, то есть изоморфен как ориентированный граф графу достижимости Re (so) некоторой подходящей сети Петри. При этом сеть может быть выбрана даже автоматной [1] с одной циркулирующей фишкой. Предложение 2. Для любого к > 1 существует ориентированное бесконечное счётное выходящее корневое дерево [2], в котором вершин к-то уровня имеется ровно одна или две и такое, что данное дерево не моделируемо. О доказательствах. Пусть имеется вершинная разметка исходного графа, то есть просто произвольная нумерация. Для доказательства первого утверждения сопоставим каждой вершине 0-1-вектор размерности d с одной единицей на месте номера вершины и остальными нулями. Далее определяются переходы, потребля- 242 емыми ресурсами которых становятся одна фишка и производимыми ресурсами -также одна фишка. Например, первой вершине соответствует вектор (1,0, ...0), третьей вершине - вектор (0,0,1, ...0). Тогда переход ?1з из первой вершины в третью определится так: £(?1з) = (-1,0,1, ...0). Таким образом получится автоматная сеть, моделирующая данный граф. В связи с первым предложением можно рассматривать вопросы моделируемо-сти различных классов графов различными типами сетей Петри. Кроме того, интересно указать минимум размерности сети, моделирующей данный граф. Здесь можно увидеть некоторый аналог алгоритма минимизации диаграммы, реализующей данный регулярный язык. Для доказательства второго примера рассмотрим сначала бесконечную возрастающую цепь из начальной вершины sq. Далее, к соответствующим вершинам цепи присоединяем по одной дуге и одной концевой вершине, назовём это «отросток». Присоединяем отросток к первой вершине, затем к третьей вершине цепи, далее к шестой, потом к десятой и т. д., увеличивая на каждом шаге построения расстояние между отростками. Полученное дерево не моделируемо. Предположим противное. Пусть дерево моделирется сетью размерности d. Тогда каждой вершине цепи будет соответствовать нетрицательный целочисленный вектор длины d, описывающий текущее состояние сети. Из любой бесконечной последовательности неотрицательных целочисленных векторов можно выделить бесконечную строго возрастающую подпоследовательность [1]. Отметим ещё свойство монотонности активности: если некоторый переход сети активен в данном состоянии, то он останется активным и в любом состоянии большем, чем данное. Рассмотрим теперь хотя бы первую вершину возрастающей подпоследовательности. На некотором расстоянии от неё, например, через q шагов, имеется отросток. Через какое-то фиксированное расстояние т от этой вершины имеется следующий элемент возрастающей подпоследовательности. Он строго больше, чем первый элемент, поэтому все переходы, активные в первом случае, остаются активными и сейчас. Все последующие элементы наследуют это свойство активности, поэтому через q шагов от второго элемента снова будет находится отросток. Таким образом, как угодно далеко вдоль цепи будут находится отрезки фиксированной длины т, содержащие два отростка, что противоречит строению дерева. По поводу второго предложения можно ещё отметить, что построить не моделируемый бесконечный граф можно, используя ограничение на скорость роста количества вершин данного уровня в любом моделируемом графе. Она должа быть степенной. Но в предложении отмечено, что в построенном дереве количество вершин данного уровня всегда 1 или 2, то есть ограничение на рост не является достаточным условием моделируемости. Указание каких-то достаточных свойств моделируемости, видимо, является 243 нерешённым вопросом.