множеством действий Д. При этом, должны выполняться следующие правила: • одной вершине графа соответствует один и только один элемент множества Ф; • одному ребру графа соответствует один и только один элемент множества Д; • одному элементу множества Ф соответствует одна и только одна вершина графа; • одному элементу множества Д соответствует одно и только одно ребро графа. Такое тождественное отображение множеств состояний Ф в множество вершин V и множества действий Д в множество ребер е математически определяется следующим образом: для любого / справедливо утверждение V(^) = Ф(^) и е(ф=Д(0, где / = 1,2,..., л. То есть, определяются две парных грамматики первая грамматика для установления перевода Ф в V, вторая грамматика для установления перевода Д в е . Таким образом, связи между вершинами тождественно соответствуют связям состояний моделируемого документооборота. В графе документооборота вершины графа соединяют ребра в том и только в том случае, если соответствующие вершинам состояния связаны действием, соответствующим ребру. Направленность ребер устанавливается таким образом, чтобы отображать логику последовательности смены состояний документооборота. Вершина / является входящей вершиной для вершины у через ребро к в том и только в том случае, если состояние / сменяется на состояние } после совершения действия к. Таким образом, состояниям у,,у2,...,уГ1 сопоставляются вершины графа ^,у2,...,уи, и каждая пара вершин V, и у, соединена дугой еч, идущей от V, к уу в том и только в том случае, когда состояние V, является входным состоянием для . 53 |
45 грамматиками. Будем рассматривать эту связь как систему перевода одного языка в другой, то есть систему соответствия их элементов. Для получения адекватной парной грамматики рассмотрим систему из двух языков, в которой первый язык введенная нотация, то есть тройка множеств {У,Д,Ф}, второй язык набор графов с направленными взвешенными дугами и вершинами [26]. 2.2.2. Графовая модель При построении графовой модели документооборота используется следующий способ отображения документооборота графами: множества вершин графа задаются множество возможных состояний Ф, а ребра графа множеством действий Д. При этом, должны выполняться следующие правила: • одной вершине графа соответствует один и только один элемент множества Ф; • одному ребру графа соответствует один и только один элемент множества Д\ • одному элементу множества Ф соответствует одна и только одна вершина графа; • одному элементу множества Д соответствует одно и только одно ребро графа. Такое тождественное отображение множеств состояний Ф в множество вершин у и множества действий Д в множество ребер е математически определяется следующим образом: для любого / справедливо утверждение у(/) = Ф(/) и *?(/) = Д(/), где 1 = 1,2,...,п. То есть определяются две парных грамматики — первая грамматика для установления перевода Ф в у, вторая грамматика — для установления перевода Д в е . Таким образом, связи между вершинами тождественно соответствуют связям состояний моделируемого документооборота. В графе документооборота вершины графа соединяют ребра в том и только в том 46 случае, если соответствующие вершинам состояния связаны действием, соответствующим ребру. Направленность ребер устанавливается таким образом, чтобы отображать логику последовательности смены состояний документооборота. Вершина I является входящей вершиной для вершины у через ребро к в том и только в том случае, если состояние / сменяется на состояние у после совершения действия к. Таким образом, состояниям уру2,...,у„ сопоставляются вершины графа у1?у2,...,у„, и каждая пара вершин у, и у, соединена дугой еи, идущей от у, к у, в том и только в том случае, когда состояние у, является входным состоянием для . Термины для описания локальной структу ры Чтобы получить возможность четкого описания различных структурных свойств документооборота, полезно ввести в графовую модель ряд понятий, определенных и широко применяемых в теории графов. Граф есть совокупность непустого множества Т7, изолированного от него множества Е (возможно, пустого) и отображения Ф множества Е У&У. Элементы множества У называются вершинами графа, элементы множества Е ребрами графа, а Ф отображением инцидентности графа [27]. Если ~(у&ч'), то у и ту называются граничными точками вне зависимости от того может ли быть граф представлен в евклидовом пространстве или нет. Если у = ту, тогда у единственная граничная точка ребра , а само ребро е называется петлей. Если е1~(у,ту) и е2~(у,ту), тогда е\ и е2 называются параллельными ребрами. В частности, две петли, инцидентные одной и той же вершине, являются параллельными. Вершины V и ту называются смежными, если существует одно ребро е такое, что е~(у,ту). В частности, вершина у смежна сама с собой, если существует петля, инцидентная V, в противном случае у не может быть смежной сама с собой. Аналогично, ребра е\ и с2 называются смежными, если они имеют, по |