Cтраница 3
Рассмотренные выше алгоритмы выделения комплексов и определение оптимально-разрывающего множества дуг объединены в единый алгоритм полного структурного анализа. [31]
Ориентированный граф с множеством вершин V и множеством дуг X, определенным формулой ( 5), является, по теореме 3, деревом. [32]
Обозначим соответственно через UJT, и UE, множества дуг, заходящих в Е, и исходящих из него. [33]
Пусть qjp ( p Z) входит в множество дуг, образующих разрыв всех элементарных контуров для многоконтурной подсистемы К. Очевидно, что при замене в этом множестве дуги qpj дугой qlt с пара-метричностью т ( случай т1 / га2) или ДУг й Ян ( случай тг те2) полученное множество по-прежнему будет разрывать все элементарные контуры; при этом общая параметричность всех разрываемых дуг может только уменьшиться. [34]
Аналогично, через К ( х) обозначается множество дуг, исходящих из х таким образом, ЛХ. [35]
В - множество имен вершин; Р - множество промежуточных дуг; Р1 - множество помеченных выходных и входных дуг, инцидентных вершинам-источникам и вершинам-стокам; С-множество имен дуг. Объекты ( сущности) отображаются вершинами СС, а отношения ( взаимосвязи) - дугами. Имена, приписываемые вершинам и дугам СС, отвечают именам соответствующих объектов и отношений, используемым в ЕЯ. [36]
Определим формально направленный граф как некое множество вершин и множество дуг, причем каждая дуга ведет от некоторой вершины V к неко. [37]
Чтобы формализовать классификацию, обозначим через и - V множество дуг, для которых о является начальной вершиной, а через V - и - мно-жесто дут, для которых и является конечной вершиной. [38]
ГДе ( /, у) е U - множество дуг, с у - стоимость единичного дугового потока, / г, ( / -) - множество узлов, которые соединены с узлом / дугами из U, начинающимися в / ( или оканчивающимися в /), сх стоимость потока. [39]
Можно также говорить, что этот функционал задан на множестве дуг некоторых кривых. [40]
Предположим далее, что S - опора G и V - множество дуг паросочетания. [41]
В теории графов эта задача срответствует задаче отыскания наименьшего по мощности множества дуг, удаление которых разрывает все контуры и тем самым превращает орграф в бесконтурный. Нахождение точного решения представляет собой ЖР-полную проблему, и для ее решения неизвестен эффективный алгоритм. Рассмотрим приближенное решение, при котором отыскивается множество дуг, принадлежащих как можно большему числу контуров. [42]
Пусть в данной сети N ( V, А) С есть множество дуг, образующих простую цепь или простой цикл в соответствующем неориентированном графе. [43]
Часто приходится рассматривать графы, в которых в сравнении с исходным уменьшены множества дуг и вершин. [44]
Граф, или сеть, определяется двумя множествами: множеством вершин и множеством дуг. Пусть М - множество вершин, а N - множество дуг графа. Дуга определяется упорядоченной парой вершин и интерпретируется как возможные направления перемещений между вершинами. Если граф содержит дугу ( / /), то возможно перемещение из вершины / в вершину у. Предположим, что вершины 1, 2, 3 и 4 ( рис. 8.1) представляют некоторые города, а дуги - некоторые дороги, связывающие данные города. [45]