|
54 Термины для описания локальной структуры Чтобы получить возможность четкого описания различных структурных свойств документооборота, полезно ввести в графовую модель ряд понятий, определенных и широко применяемых в теории графов. Граф есть совокупность непустого множества V , изолированного от него множества Е (возможно, пустого) и отображения Ф множества Е V & V . Элементы множества V называются вершинами графа, элементы множества Е ~ ребрами графа, а Ф отображением инцидентности графа [86]. Если еЩу&м), то V и IV называются граничными точками вне зависимости от того может ли быть граф представлен в евклидовом пространстве или нет. Если у = ч/, тогда V единственная граничная точка ребра е, а само ребро е называется петлей. Если еЮ (у,IV) и е2П (у,и>), тогда е\ и е2 называются параллельными ребрами. В частности, две петли, инцидентные одной и той же вершине, являются параллельными. Вершины у и IV называются смежными, если существует одно ребро е такое, что е □ (у, >у). В частности, вершина у смежна сама с собой, если существует петля, инцидентная у , в противном случае у не может быть смежной сама с собой. Аналогично, ребра е\ и е2 называются смежными, если они имеют, по крайней мере, одну общую граничную точку. Смежность является отношением между двумя подобными элементами (между вершинами или между ребрами), тогда как инцидентность является отношением между разнородными элементами. Число ребер, инцидентных вершине у (петля учитывается дважды), называется степенью вершины у и обозначается 6(у). Говорят, что вершина у изолирована, если 6(у) = 0. Если дуга е направлена от вершины у к вершине IV, то она считается отрицательно инцидентной вершине у и положительно инцидентной вершине ™. Число дуг, положительно инцидентных вершине у, называется положительной степенью у и обозначается через 6+(у). Отрицательная степень определяется аналогично, через 6-(у). |
46 случае, если соответствующие вершинам состояния связаны действием, соответствующим ребру. Направленность ребер устанавливается таким образом, чтобы отображать логику последовательности смены состояний документооборота. Вершина I является входящей вершиной для вершины у через ребро к в том и только в том случае, если состояние / сменяется на состояние у после совершения действия к. Таким образом, состояниям уру2,...,у„ сопоставляются вершины графа у1?у2,...,у„, и каждая пара вершин у, и у, соединена дугой еи, идущей от у, к у, в том и только в том случае, когда состояние у, является входным состоянием для . Термины для описания локальной структу ры Чтобы получить возможность четкого описания различных структурных свойств документооборота, полезно ввести в графовую модель ряд понятий, определенных и широко применяемых в теории графов. Граф есть совокупность непустого множества Т7, изолированного от него множества Е (возможно, пустого) и отображения Ф множества Е У&У. Элементы множества У называются вершинами графа, элементы множества Е ребрами графа, а Ф отображением инцидентности графа [27]. Если называются граничными точками вне зависимости от того может ли быть граф представлен в евклидовом пространстве или нет. Если у = ту, тогда у единственная граничная точка ребра Если е1~(у,ту) и е2~(у,ту), тогда е\ и е2 называются параллельными ребрами. В частности, две петли, инцидентные одной и той же вершине, являются параллельными. Вершины V и ту называются смежными, если существует одно ребро е такое, что е~(у,ту). В частности, вершина у смежна сама с собой, если существует петля, инцидентная V, в противном случае у не может быть смежной сама с собой. Аналогично, ребра е\ и с2 называются смежными, если они имеют, по 47 крайней мере, одну общую граничную точку. Смежность является отношением между двумя подобными элементами (между вершинами или между ребрами), тогда как инцидентность является отношением между разнородными элементами. Число ребер, инцидентных вершине V (петля учитывается дважды), называется степенью вершины у и обозначается Ь(г). Говорят, что вершина у изолирована, если 6(у) = 0. Если дуга е направлена от вершины V к вершине ;у, то она считается отрицательно инцидентной вершине у и положительно инцидентной вершине Число дуг, положительно инцидентных вершине у, называется положительной степенью у и обозначается через Ь+(у). Отрицательная степень определяется аналогично, через Ь (у). Определения модели документооборота на графе Для представления графа документооборота принимается написание вида С = (У,Е,Г), где Vмножество вершин графа, Е ~ множество ребер графа, Г множество отношений инцидентности. Таким образом, граф С состоит из непустого множества элементов, называемых вершинами; множества связанных пар из множества вершин, называемых ребрами; множества признаков направленности ребер. Множество, состоящее из вершин графа О, называется множеством вершин графа и обозначается 7(0). Аналогично, множество, состоящее из ребер, называется множеством ребер и обозначается Е(0). Если V и ш являются вершинами графа О, тогда ребро те называется связью, которая соединяет у и и». Две вершины х и у являются граничными вершинами дуги и, если х начало дуги, а у конец дуги. Две вершины х и у смежны, если они различны и существуют, и есть дуга, идущая от одной из них к другой. Считается, что дуга и исходит из вершины х, если х является началом, но не является концом и, и что дуга заходит в х, если х является концом, но не является началом и. В обоих случаях дуга г/ называется инцидентной вершине х, а вершина х инцидентной дуге и. Общее число дуг, |