Реферат: Графовая модель композитного документооборота

--PAGE_BREAK--Для отображения отношений используются два типа связей – «один к одному» и «один к многим». Теоретически возможно использование и связи «многие к многим», однако в практике ее использование нецелесообразно, так как приводит к усложнению восприятия модели и логики ее работы.  Если по какой-либо причине возникнет необходимость его использования, то этот тип связи может быть синтезирован с помощью двух предыдущих типов.
               
Таким образом, мы исходим из того, что документооборот организации задан в виде систем трех множеств, каждое из которых содержит конечное количество элементов. Предполагается также возможность изменения содержания множеств во время жизненного цикла процессов документооборота. Изменения элементов происходят дискретно таким образом, что каждому шагу изменений соответствует система <shape id="_x0000_i1043" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image012.wmz» o:><img width=«69» height=«23» src=«dopb37953.zip» v:shapes="_x0000_i1043"> со статическим содержанием множеств. Множество, состоящее из троек <shape id="_x0000_i1044" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image012.wmz» o:><img width=«69» height=«23» src=«dopb37953.zip» v:shapes="_x0000_i1044">, описывает события, происходящие в системе документооборота, с учетом времени. Каждый из элементов множества соответствует общему состоянию системы на какой-либо определенный момент, называемый кадром.
3.2.1. Использование графов в модели документооборота
В данной статье уже введена нотация, которая задает систему композитного документооборота с достаточной степенью адекватности. Для установления соответствия введенной нотации графовому представлению будем использовать так называемую парную грамматику. Парная грамматика представляет собой композицию двух грамматик, между правилами и нетерминальными символами которых устанавливаются предтерменированные однозначные соответствия. Таким образом, парная грамматика устанавливает однозначную связь между элементами языков, определенных двумя грамматиками. Будем рассматривать эту связь как систему перевода одного языка в другой, то есть систему соответствия их элементов.
В нашем случае для получения адекватной парной грамматики рассмотрим систему из двух языков, в которой первый язык – введенная нотация, то есть тройка множеств <shape id="_x0000_i1045" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image012.wmz» o:><img width=«69» height=«23» src=«dopb37953.zip» v:shapes="_x0000_i1045">, второй язык – набор графов с направленными взвешенными дугами и вершинами. Полученные два языка будем использовать для установления однозначного соответствия между понятиями теории графов и понятиями композитного документооборота, введенными и применяемыми автором этой статьи [8, 10].
3.2.2. Графовая модель
При построении графовой модели документооборота предлагается использовать следующий способ отображения документооборота графами. Для задания множества вершин графа будем исползовать множество возможных состояний <shape id="_x0000_i1046" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image014.wmz» o:><img width=«17» height=«16» src=«dopb37952.zip» v:shapes="_x0000_i1046">. Ребра графа зададим с помощью множества действий Д.  Установим это соответствие таким образом, чтобы выполнялись следующие правила:
– одной вершине графа соответствует один и только один элемент множества <shape id="_x0000_i1047" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image014.wmz» o:><img width=«17» height=«16» src=«dopb37952.zip» v:shapes="_x0000_i1047">;
– одному ребру графа соответствует один и только один элемент множества <shape id="_x0000_i1048" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image017.wmz» o:><img width=«19» height=«20» src=«dopb37951.zip» v:shapes="_x0000_i1048">;
– одному элементу множества <shape id="_x0000_i1049" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image014.wmz» o:><img width=«17» height=«16» src=«dopb37952.zip» v:shapes="_x0000_i1049">соответствует одна и только одна вершина графа;
– одному элементу множества <shape id="_x0000_i1050" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image017.wmz» o:><img width=«19» height=«20» src=«dopb37951.zip» v:shapes="_x0000_i1050"> соответствует одно и только одно ребро графа.
 Такое тождественное отображение множеств состояний <shape id="_x0000_i1051" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image014.wmz» o:><img width=«17» height=«16» src=«dopb37952.zip» v:shapes="_x0000_i1051"> в множество вершин <shape id="_x0000_i1052" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image018.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1052"> и множества состояний <shape id="_x0000_i1053" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image017.wmz» o:><img width=«19» height=«20» src=«dopb37951.zip» v:shapes="_x0000_i1053"> в множество ребер e можно математически определить следующим образом: для любого <shape id="_x0000_i1054" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image020.wmz» o:><img width=«9» height=«17» src=«dopb37955.zip» v:shapes="_x0000_i1054"> справедливо утверждение <shape id="_x0000_i1055" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image022.wmz» o:><img width=«69» height=«23» src=«dopb37956.zip» v:shapes="_x0000_i1055"> и <shape id="_x0000_i1056" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image024.wmz» o:><img width=«72» height=«23» src=«dopb37957.zip» v:shapes="_x0000_i1056">, где <shape id="_x0000_i1057" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image020.wmz» o:><img width=«9» height=«17» src=«dopb37955.zip» v:shapes="_x0000_i1057"> Є I, I=1,2,3..n. То есть определяются две парных грамматики – первая грамматика для установления перевода Ф в v, вторая грамматика – для установления перевода Д в e.
Таким образом, связи между вершинами тождественно соответствуют связям состояний моделируемого документооборота. В графе документооборота вершины графа соединяют ребра в том и только в том случае, если соответствующие вершинам состояния связаны действием, соответствующим ребру, то есть e= {e, если ребро существует; 0, если ребро отсутствует}.
Направленность ребер устанавливается таким образом, чтобы отображать логику последовательности смены состояний документооборота. Вершина <shape id="_x0000_i1058" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image020.wmz» o:><img width=«9» height=«17» src=«dopb37955.zip» v:shapes="_x0000_i1058"> является входящей вершиной для вершины <shape id="_x0000_i1059" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image026.wmz» o:><img width=«13» height=«20» src=«dopb37958.zip» v:shapes="_x0000_i1059"> через ребро <shape id="_x0000_i1060" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image028.wmz» o:><img width=«13» height=«19» src=«dopb37959.zip» v:shapes="_x0000_i1060"> в том и только в том случае, если состояние i сменяется на состояние <shape id="_x0000_i1061" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image026.wmz» o:><img width=«13» height=«20» src=«dopb37958.zip» v:shapes="_x0000_i1061"> после совершения действия <shape id="_x0000_i1062" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image028.wmz» o:><img width=«13» height=«19» src=«dopb37959.zip» v:shapes="_x0000_i1062">. Таким образом, состояниям <shape id="_x0000_i1063" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image030.wmz» o:><img width=«19» height=«23» src=«dopb37960.zip» v:shapes="_x0000_i1063">, <shape id="_x0000_i1064" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image032.wmz» o:><img width=«52» height=«24» src=«dopb37961.zip» v:shapes="_x0000_i1064"> сопоставляются вершины графа <shape id="_x0000_i1065" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image034.wmz» o:><img width=«67» height=«24» src=«dopb37962.zip» v:shapes="_x0000_i1065">, и каждая пара вершин <shape id="_x0000_i1066" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image036.wmz» o:><img width=«16» height=«24» src=«dopb37963.zip» v:shapes="_x0000_i1066"> и <shape id="_x0000_i1067" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image038.wmz» o:><img width=«17» height=«25» src=«dopb37964.zip» v:shapes="_x0000_i1067"> соединена дугой <shape id="_x0000_i1068" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image040.wmz» o:><img width=«17» height=«25» src=«dopb37965.zip» v:shapes="_x0000_i1068">, идущей от <shape id="_x0000_i1069" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image036.wmz» o:><img width=«16» height=«24» src=«dopb37963.zip» v:shapes="_x0000_i1069"> к <shape id="_x0000_i1070" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image038.wmz» o:><img width=«17» height=«25» src=«dopb37964.zip» v:shapes="_x0000_i1070"> в том и только в том случае, когда состояние <shape id="_x0000_i1071" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image036.wmz» o:><img width=«16» height=«24» src=«dopb37963.zip» v:shapes="_x0000_i1071"> является входным состоянием для <shape id="_x0000_i1072" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image038.wmz» o:><img width=«17» height=«25» src=«dopb37964.zip» v:shapes="_x0000_i1072">.
3.2.2.1. Термины для описания локальной структуры
Чтобы получить возможность четкого описания различных структурных свойств документооборота, полезно ввести в графовую модель ряд понятий, определенных и широко применяемых в теории графов.
Граф есть совокупность непустого множества <shape id="_x0000_i1073" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image042.wmz» o:><img width=«16» height=«17» src=«dopb37966.zip» v:shapes="_x0000_i1073">, изолированного от него множества <shape id="_x0000_i1074" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image044.wmz» o:><img width=«16» height=«16» src=«dopb37967.zip» v:shapes="_x0000_i1074"> (возможно, пустого) и отображения <shape id="_x0000_i1075" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image014.wmz» o:><img width=«17» height=«16» src=«dopb37952.zip» v:shapes="_x0000_i1075"> множества <shape id="_x0000_i1076" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image044.wmz» o:><img width=«16» height=«16» src=«dopb37967.zip» v:shapes="_x0000_i1076"> <shape id="_x0000_i1077" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image046.wmz» o:><img width=«44» height=«19» src=«dopb37968.zip» v:shapes="_x0000_i1077">. Элементы множества <shape id="_x0000_i1078" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image042.wmz» o:><img width=«16» height=«17» src=«dopb37966.zip» v:shapes="_x0000_i1078"> называются вершинами графа, элементы множества <shape id="_x0000_i1079" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image044.wmz» o:><img width=«16» height=«16» src=«dopb37967.zip» v:shapes="_x0000_i1079"> – ребрами графа, а <shape id="_x0000_i1080" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image014.wmz» o:><img width=«17» height=«16» src=«dopb37952.zip» v:shapes="_x0000_i1080"> – отображением инцидентности графа [11].
Если <shape id="_x0000_i1081" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image048.wmz» o:><img width=«75» height=«23» src=«dopb37969.zip» v:shapes="_x0000_i1081">, то <shape id="_x0000_i1082" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1082"> и <shape id="_x0000_i1083" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image051.wmz» o:><img width=«16» height=«15» src=«dopb37970.zip» v:shapes="_x0000_i1083"> называются граничными точками вне зависимости от того может ли быть граф представлен в евклидовом пространстве или нет. Если <shape id="_x0000_i1084" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image053.wmz» o:><img width=«40» height=«15» src=«dopb37971.zip» v:shapes="_x0000_i1084">, тогда <shape id="_x0000_i1085" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1085"> — единственная граничная точка ребра <shape id="_x0000_i1086" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image055.wmz» o:><img width=«12» height=«15» src=«dopb37972.zip» v:shapes="_x0000_i1086">, а само ребро <shape id="_x0000_i1087" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image055.wmz» o:><img width=«12» height=«15» src=«dopb37972.zip» v:shapes="_x0000_i1087"> называется петлей. Если <shape id="_x0000_i1088" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image057.wmz» o:><img width=«68» height=«23» src=«dopb37973.zip» v:shapes="_x0000_i1088"> и <shape id="_x0000_i1089" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image057.wmz» o:><img width=«68» height=«23» src=«dopb37973.zip» v:shapes="_x0000_i1089">, тогда <shape id="_x0000_i1090" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image059.wmz» o:><img width=«17» height=«19» src=«dopb37974.zip» v:shapes="_x0000_i1090"> и <shape id="_x0000_i1091" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image061.wmz» o:><img width=«20» height=«19» src=«dopb37975.zip» v:shapes="_x0000_i1091"> называются параллельными ребрами. В частности, две петли, инцидентные одной и той же вершине, являются параллельными. Вершины <shape id="_x0000_i1092" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1092"> и <shape id="_x0000_i1093" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image051.wmz» o:><img width=«16» height=«15» src=«dopb37970.zip» v:shapes="_x0000_i1093"> называются смежными, если существует одно ребро <shape id="_x0000_i1094" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image055.wmz» o:><img width=«12» height=«15» src=«dopb37972.zip» v:shapes="_x0000_i1094"> такое, что  <shape id="_x0000_i1095" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image063.wmz» o:><img width=«61» height=«23» src=«dopb37976.zip» v:shapes="_x0000_i1095">. В частности, вершина <shape id="_x0000_i1096" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1096"> смежна сама с собой, если существует петля, инцидентная <shape id="_x0000_i1097" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1097">, в противном случае <shape id="_x0000_i1098" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1098"> не может быть смежной сама с собой. Аналогично, ребра <shape id="_x0000_i1099" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image059.wmz» o:><img width=«17» height=«19» src=«dopb37974.zip» v:shapes="_x0000_i1099"> и <shape id="_x0000_i1100" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image061.wmz» o:><img width=«20» height=«19» src=«dopb37975.zip» v:shapes="_x0000_i1100"> называются смежными, если они имеют, по крайней мере, одну общую граничную точку.
Смежность является отношением между двумя подобными элементами (между вершинами или между ребрами), тогда как инцидентность является отношением между разнородными элементами. Число ребер, инцидентных вершине <shape id="_x0000_i1101" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1101"> (петля учитывается дважды), называется степенью вершины <shape id="_x0000_i1102" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1102"> и обозначается <shape id="_x0000_i1103" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image065.wmz» o:><img width=«31» height=«23» src=«dopb37977.zip» v:shapes="_x0000_i1103">. Говорят, что вершина <shape id="_x0000_i1104" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1104"> изолирована, если  b(v)=0. Если дуга e направлена от вершины <shape id="_x0000_i1105" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1105"> к вершине <shape id="_x0000_i1106" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image051.wmz» o:><img width=«16» height=«15» src=«dopb37970.zip» v:shapes="_x0000_i1106">, то она считается отрицательно инцидентной вершине <shape id="_x0000_i1107" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1107"> и положительно инцидентной вершине <shape id="_x0000_i1108" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image051.wmz» o:><img width=«16» height=«15» src=«dopb37970.zip» v:shapes="_x0000_i1108">. Число дуг, положительно инцидентных вершине <shape id="_x0000_i1109" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1109">, называется положительной степенью <shape id="_x0000_i1110" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image050.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1110"> и обозначается через <shape id="_x0000_i1111" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image067.wmz» o:><img width=«45» height=«23» src=«dopb37978.zip» v:shapes="_x0000_i1111">. Отрицательная степень определяется аналогично, через <shape id="_x0000_i1112" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image069.wmz» o:><img width=«44» height=«23» src=«dopb37979.zip» v:shapes="_x0000_i1112">.
Конечная последовательность ребер графа <shape id="_x0000_i1113" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image071.wmz» o:><img width=«21» height=«20» src=«dopb37980.zip» v:shapes="_x0000_i1113"><shape id="_x0000_i1114" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image073.wmz» o:><img width=«57» height=«20» src=«dopb37981.zip» v:shapes="_x0000_i1114"> (не обязательно различных называется маршрутом длины <shape id="_x0000_i1115" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image075.wmz» o:><img width=«13» height=«15» src=«dopb37982.zip» v:shapes="_x0000_i1115">, если существует последовательность <shape id="_x0000_i1116" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image077.wmz» o:><img width=«24» height=«20» src=«dopb37983.zip» v:shapes="_x0000_i1116"> <shape id="_x0000_i1117" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image079.wmz» o:><img width=«55» height=«20» src=«dopb37984.zip» v:shapes="_x0000_i1117"> из <shape id="_x0000_i1118" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image081.wmz» o:><img width=«33» height=«19» src=«dopb37985.zip» v:shapes="_x0000_i1118"> (не обязательно различных вершин) таких, что <shape id="_x0000_i1119" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image083.wmz» o:><img width=«105» height=«23» src=«dopb37986.zip» v:shapes="_x0000_i1119"> для <shape id="_x0000_i1120" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image085.wmz» o:><img width=«73» height=«20» src=«dopb37987.zip» v:shapes="_x0000_i1120">.  Говорят, что маршрут замкнут, если <shape id="_x0000_i1121" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image087.wmz» o:><img width=«52» height=«19» src=«dopb37988.zip» v:shapes="_x0000_i1121">, и не замкнут, если <shape id="_x0000_i1122" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image089.wmz» o:><img width=«52» height=«19» src=«dopb37989.zip» v:shapes="_x0000_i1122">. Если все неориентированные ребра, составляющие неориентированный маршрут, различны, то такой маршрут называется цепью, если она не замкнута, и циклом, если он замкнут. Ориентированный маршрут, в котором нет повторяющихся дуг, называется путем или контуром (ориентированным циклом) в зависимости от того, является он замкнутым или нет.
3.2.2.2. Определения модели документооборота на графе
В настоящей статье для представления графа документооборота принимается написание вида <shape id="_x0000_i1123" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image091.wmz» o:><img width=«88» height=«23» src=«dopb37990.zip» v:shapes="_x0000_i1123">, где <shape id="_x0000_i1124" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image093.wmz» o:><img width=«16» height=«17» src=«dopb37966.zip» v:shapes="_x0000_i1124">– множество вершин графа, <shape id="_x0000_i1125" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image094.wmz» o:><img width=«16» height=«16» src=«dopb37967.zip» v:shapes="_x0000_i1125"> – множество ребер графа, <shape id="_x0000_i1126" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image095.wmz» o:><img width=«17» height=«16» src=«dopb37991.zip» v:shapes="_x0000_i1126"> – множество отношений инцидентности. Таким образом, граф <shape id="_x0000_i1127" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image097.wmz» o:><img width=«17» height=«19» src=«dopb37992.zip» v:shapes="_x0000_i1127"> состоит из непустого множества элементов, называемых вершинами; множества связанных пар из множества вершин, называемых ребрами; множества признаков направленности ребер. Множество, состоящее из вершин графа <shape id="_x0000_i1128" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image097.wmz» o:><img width=«17» height=«19» src=«dopb37992.zip» v:shapes="_x0000_i1128">, называется множеством вершин графа и обозначается <shape id="_x0000_i1129" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image099.wmz» o:><img width=«37» height=«23» src=«dopb37993.zip» v:shapes="_x0000_i1129">. Аналогично, множество, состоящее из ребер, называется множеством ребер и обозначается <shape id="_x0000_i1130" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image101.wmz» o:><img width=«37» height=«23» src=«dopb37994.zip» v:shapes="_x0000_i1130">. Если v и w являются вершинами графа <shape id="_x0000_i1131" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image097.wmz» o:><img width=«17» height=«19» src=«dopb37992.zip» v:shapes="_x0000_i1131">, тогда ребро <shape id="_x0000_i1132" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image103.wmz» o:><img width=«23» height=«15» src=«dopb37995.zip» v:shapes="_x0000_i1132"> называется связью, которая соединяет <shape id="_x0000_i1133" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image018.wmz» o:><img width=«12» height=«15» src=«dopb37954.zip» v:shapes="_x0000_i1133"> и <shape id="_x0000_i1134" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image105.wmz» o:><img width=«16» height=«15» src=«dopb37970.zip» v:shapes="_x0000_i1134">.
Две вершины <shape id="_x0000_i1135" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1135"> и <shape id="_x0000_i1136" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image108.wmz» o:><img width=«15» height=«17» src=«dopb37997.zip» v:shapes="_x0000_i1136"> являются граничными вершинами дуги u, если <shape id="_x0000_i1137" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1137"> – начало дуги, а <shape id="_x0000_i1138" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image108.wmz» o:><img width=«15» height=«17» src=«dopb37997.zip» v:shapes="_x0000_i1138"> – конец дуги. Две вершины <shape id="_x0000_i1139" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1139"> и <shape id="_x0000_i1140" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image108.wmz» o:><img width=«15» height=«17» src=«dopb37997.zip» v:shapes="_x0000_i1140"> смежны, если они различны и существуют, и есть дуга, идущая от одной из них к другой. Считается, что дуга <shape id="_x0000_i1141" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image110.wmz» o:><img width=«13» height=«15» src=«dopb37998.zip» v:shapes="_x0000_i1141"> исходит из вершины <shape id="_x0000_i1142" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1142">, если <shape id="_x0000_i1143" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1143"> является началом, но не является концом <shape id="_x0000_i1144" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image110.wmz» o:><img width=«13» height=«15» src=«dopb37998.zip» v:shapes="_x0000_i1144">, и что дуга заходит в <shape id="_x0000_i1145" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1145">, если <shape id="_x0000_i1146" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1146"> является концом, но не является началом <shape id="_x0000_i1147" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image110.wmz» o:><img width=«13» height=«15» src=«dopb37998.zip» v:shapes="_x0000_i1147">. В обоих случаях дуга <shape id="_x0000_i1148" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image110.wmz» o:><img width=«13» height=«15» src=«dopb37998.zip» v:shapes="_x0000_i1148"> называется инцидентной вершине <shape id="_x0000_i1149" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1149">, а вершина <shape id="_x0000_i1150" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1150"> – инцидентной дуге u. Общее число дуг, инцидентных вершине <shape id="_x0000_i1151" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1151">, является степенью вершины <shape id="_x0000_i1152" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image106.wmz» o:><img width=«13» height=«15» src=«dopb37996.zip» v:shapes="_x0000_i1152"> и обозначается <shape id="_x0000_i1153" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image112.wmz» o:><img width=«31» height=«23» src=«dopb37999.zip» v:shapes="_x0000_i1153">.
3.2.3.Типы графа в модели
Для наглядного представления модели документооборота предлагается использовать два основных вида графов: ориентированные и неориентированные. В большинстве современных реализаций электронного документооборота используются только ориентированные графы, что накладывает ряд ограничений на применимость решения. В частности, на раннем этапе надо иметь детерминированное описание о направленности протекающих процессов, что на практике часто является очень сложным. Рассмотрим целесообразность и адекватность применения различных видов графов в модели документооборота. Для этого воспользуемся разделением процесса создания композитного документооборота на этапы, предложенные автором настоящей статьи в работе [10].
Неориентированные графы удобно использовать на этапах анализа и проектирования для наглядного отображения полученных при  обследовании данных. Характерной для этих этапов особенностью являются слабая связность и неустойчивость корреляций первичных данных. Модели начинают строиться на основании данных, полученных при первичном анализе. При опросе дополнительных пользователей, выявлении дополнительных данных становятся явными корреляции, которые упраздняют предыдущие. В описанной ситуации неориентированный граф очень удобен для использования, так как позволяет лишь констатировать факт наличия связи между отношениями, не требуя установления направленности. Первые данные, полученные при анализе, вообще представляют собой множество состояний документа, что отображается вырожденным неориентированным графом. По мере поступления дополнительных данных становятся явными существующие отношения и начальные состояния рассматриваемых бизнес-процессов. Это отображается слабосвязным неориентированным графом.
Ориентированные графы целесообразно использовать на этапах проектирования, реализации, внедрения и разработки. При  разработке систем композитного документооборота на вышеописанных этапах на неупорядоченные отношения между состояниями накладываются правила, описывающие их последовательность. При формализации и детерминировании этих правил важно обеспечить сохранность полученной информации о причинно-следственных связях. Эта информация наглядно и полно отображается с помощью ориентированных графов.
При составлении графовых моделей бизнес-процессов удобно использовать циклы для отображения реальных процессов, происходящих на предприятии. На практике, часто в производственном процессе, используется цикличная организация, то есть документ попадает в цикл, образованный между несколькими исполнителями и состояниями, который заканчивается по факту выполнения достаточных условий. Такая форма прозрачна и широко распространена в реальной жизни. Тем не менее значительно усложняет задачу моделирования с точки зрения конечности моделируемых процессов. Не представляется возможным гарантировать факт возникновения условий достаточности, то есть критериев окончания перфекционного цикла. В таком случае всегда остается вероятность того, что цикл не будет завершен в пределах жизненного цикла документооборота. Таким образом, можно утверждать, что применение графов Бержи для описания моделей документооборота накладывает неоправданные ограничения на синтезируемые системы и значительно сокращает функциональные возможности будущих систем.
Исходя из вышеизложенного, можно утверждать, что для отображения процессов документооборота целесообразно использовать ориентированные графы, содержащие циклы.
3.2.4. Время в модели
Используемая в данной модели дискретизация состояний документов и событий, вызывающих изменение состояний, подозревает, что эти события происходят в некотором дискретном временном пространстве. Это значит, что производственная деятельность предприятия разделяется на соответствующие участки времени, каждый из которого содержит не более одного события по изменению состояний. Общая совокупность этих временных участков представляет жизненный цикл документооборота.
Проводя аналогию с кинематографом, можно сравнить процесс документооборота, протекающий во времени, с кинофильмом. В этом примере каждый временной участок дискретного времени документооборота представляется  кадром фильма – снимком ситуации, в котором зафиксировано текущее состояние документооборота организации. Последовательная смена кадров образует анимацию, что представляет общий процесс движения документов организации во времени – последовательное изменение состояний множества после некоторых дискретных тактов.
Очевидно, что на практике в документообороте даже небольшого предприятия участвует некоторое множество документов. До сих пор основное внимание мы уделяли модели документооборота, состоящей из одного документа, состояния которого образуют множество состояний. Расширим нашу модель так, чтобы она отражала не один документ, а множество документов, что позволит представлять не только существующие документообороты, но и те, которые могут возникнуть в будущем. Для этого надо представить каждый из документов в виде множества состояний, возможных в пределах документооборота. Если произвести конкатенацию полученных множеств, то получится новое множество, т.е. совокупность элементов которых представляют все возможные состояния всех документов, которые участвуют в моделируемом процессе документооборота.
Описываемая динамическая модель документооборота представляет собой множество матриц, каждая из которых определяет состояние документов в единицу времени. Под единицей времени будем понимать момент времени между событиями, приводящими к изменению хотя бы одного состояния одного документа.
Представление модели в виде совокупности состояний, которые могут быть представлены в виде  графа,  позволяют выразить ее реактивность в терминах темпоральной логики. В работе [12] описано использование темпоральной логики на Е-сетях, являющихся мощным расширением сетей Петри. Таким образом, появляется возможность представления систем документооборота с помощью Е-сетей и реализации динамической модели, основанной на темпоральной логике. Такая реализация представляет самостоятельный интерес и будет исследована автором в дальнейшей работе.
3.2.5. Матричная форма представления
Для задания матричной формы представления документооборота будем использовать три множества из введенной ранее тройки <shape id="_x0000_i1154" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image012.wmz» o:><img width=«69» height=«23» src=«dopb37953.zip» v:shapes="_x0000_i1154">. Считается, что на момент представления произошла актуализация множеств, то есть все состояния представлены множеством форм, все действия, приводящие к изменению состояний множеством действий, а участники, производящие действия, описаны в виде ролей в множестве участников. Предполагается, что задаваемая матричная модель будет представлять динамическую модель документооборота, оперирующую конечным количеством документов, при этом описывая в точности до дискретизации все события и состояния системы.
Для решения вышеописанной задачи предлагается использовать множество плоских прямоугольных матриц документооборота, каждая из которых представляет состояние системы в некоторую дискретную единицу времени. Столбцы матрицы документооборота ставятся в соответствие состояниям документов, возможных в пределах жизненного цикла документооборота. То есть первый столбец соответствует первому элементу множества <shape id="_x0000_i1155" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image114.wmz» o:><img width=«17» height=«16» src=«dopb37952.zip» v:shapes="_x0000_i1155">, второй столбец – второму элементу и так далее, до последнего элемента множества <shape id="_x0000_i1156" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image114.wmz» o:><img width=«17» height=«16» src=«dopb37952.zip» v:shapes="_x0000_i1156">. Строки матрицы документооборота ставятся в соответствие действиям, произведение которых приводит к смене состояния хотя бы одного документа. Первая строка соответствует первому элементу множества <shape id="_x0000_i1157" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image115.wmz» o:><img width=«19» height=«20» src=«dopb37951.zip» v:shapes="_x0000_i1157">, вторая строка – второму и так далее, для всего множества <shape id="_x0000_i1158" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image115.wmz» o:><img width=«19» height=«20» src=«dopb37951.zip» v:shapes="_x0000_i1158">. Таким образом, мы получаем прямоугольную матрицу со столбцами, количество которых равно размерности множества <shape id="_x0000_i1159" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image114.wmz» o:><img width=«17» height=«16» src=«dopb37952.zip» v:shapes="_x0000_i1159"> и строкам по размерности матрицы <shape id="_x0000_i1160" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image115.wmz» o:><img width=«19» height=«20» src=«dopb37951.zip» v:shapes="_x0000_i1160">. Заполняется данная матрица элементами множества ролевых участников моделируемого документооборота <shape id="_x0000_i1161" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image116.wmz» o:><img width=«16» height=«17» src=«dopb37950.zip» v:shapes="_x0000_i1161">. Элемент заполняется в клетку матрицы в том и только в том случае, если соответствующий участник производит действие, соответствующее элементу строки, что приводит к изменению состояния, соответствующего элементу столбца. В том случае, если на данном шаге документооборота действие строки не изменяет состояние столбца, то элемент матрицы заполняется пустыми или нулевыми значениями. Критерием успешности создания матрицы является ее невырожденность по столбцам и строкам. То есть в матрице существуют хотя бы один столбец, содержащий непустой элемент, и хотя бы одна строка, в которой присутствует непустой элемент. При этом предполагается, что для заполнения будут задействованы не все элементы множества ролевых участников <shape id="_x0000_i1162" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«7191.files/image116.wmz» o:><img width=«16» height=«17» src=«dopb37950.zip» v:shapes="_x0000_i1162">.
    продолжение
--PAGE_BREAK--