Cтраница 4
Графы, в которых связь между вершинами имеет направление, т.е. осуществляется множеством дуг, называют сетью. [46]
Чтобы использовать эту теорему для ориентированных сетей с источником и стоком, дополним множество дуг дугой ( л - f - l, О) с бесконечной пропускной способностью, замыкающей сеть. [47]
Предположим, что под действием внешней нагрузки берега разреза L смыкаются вдоль некоторого множества дуг. L, вдоль которых берега разреза не контактируют. Будем считать, что на части контура L - L имеется полное сцепление берегов разреза, а остальная часть свободна от нагрузки. [48]
Множество дуг, выходящих из вершины i, мы будем обозначать через NT, множество дуг, входящих в i, - через NJ. [49]
Граф имеет множество вершин, соответствующих пунктам сети ( узлам сети), и множество дуг ( ребер) - линий связи. Вершины и дуги записываются набором чисел и нумеруются в определенной последовательности. [50]
Очевидно, что Н о ( Я) не всегда будет потоком, если множество дуг 5 произвольно, так как поток должен удовлетворять уравнению непрерывности (11.1) при некотором значении V. [51]
В - множество имен вершин; Р - множество промежуточных дуг; Р1 - множество помеченных выходных и входных дуг, инцидентных вершинам-источникам и вершинам-стокам; С-множество имен дуг. Объекты ( сущности) отображаются вершинами СС, а отношения ( взаимосвязи) - дугами. Имена, приписываемые вершинам и дугам СС, отвечают именам соответствующих объектов и отношений, используемым в ЕЯ. [52]
На рис. 11.1 эти компоненты изображены в виде прямоугольников, а линии между прямоугольниками обозначают множество дуг, связывающих - эти компоненты. [53]
Алгоритм установления изоморфизма за О ( У-log У) действий зависит от эффективного алгоритма разбиения множества дуг планарногЬ графа на подмножества таким образом, что две дуги принадлежат одному и тому же множеству тогда и только тогда, когда эти дуги неразличимы. Разбиение отыскивается следующим образом. [54]
Сеть ( или линейный граф) состоит из множества узлов ( или вершин, точек) и множества дуг ( или ребер, звеньев), соединяющих различные пары узлов. Поэтому говорят, что сеть является ориентированной. [55]
& разбивает множество всех дуг сети 6 на три непересекающиеся множества: 6 ( w) - множество дуг базисного дерева, в которое входят, в частности, все дуги, на которых выполняется условие 0 хц ( wu) q ( ws); G ( w) - множество тех хорд, для которых х ( w) qu ( w5); C3 ( w) - множество хорд с нулевой производительностью. [56]