Ориентированная сеть

Cтраница 1

Ориентированная сеть называется ациклической, если она не содержит циклов. [1]

По этим данным строится ориентированная сеть, дуги которой соответствуют работам проекта, а узлы - событиям, обозначающим начало и / или конец этапов. Каждая дуга нагружена числом, равным продолжительности выполнения соответствующей операции. [2]

Пусть S - произвольная частично ориентированная сеть, каждому ребру и которой приписано неотрицательное число с ( и) - пропускная способность. Потоком в сети S называется пара ( /, со), где со - некоторая ориентация всех неориентированных ребер сети, а / ( и) - заданная на множестве всех ребер функция с неотрицательными значениями, не превосходящими пропускных способностей, и такая, что в каждой внутренней вершине а выполняется закон Кирхгофа, согласно которому сумма значений потока по ребрам, входящим в вершину, равна сумме значений потока по ребрам, исходящим из вершины. [3]

Чтобы использовать эту теорему для ориентированных сетей с источником и стоком, дополним множество дуг дугой ( л - f - l, О) с бесконечной пропускной способностью, замыкающей сеть. [4]

В нижней части рис. 24 изображена ориентированная сеть, построенная по данным таблицы 2 и наглядно показывающая, как именно связаны между собой работы по проекту и в какой очередности их следует выполнять. [5]

Представим схему материальных и энергетических потоков производства в виде ориентированной сети, узлами которой являются агрегаты, промежуточные емкости, склады, а дугами - технологические и энергетические связи между ними. [6]

Сетевые базы данных строятся на основе сетевой модели данных, в которой данные имеют структуру ориентированного графа. База данных представляется ориентированной сетью. [7]

Простота, наглядность, обозримость графа ( сети) позволяют использовать сетевую модель в задачах оперативного планирования и управления крупными разработками. Сетевая модель разработки - ориентированная сеть без циклов, дуги к-рой соответствуют отд. Дугам ( операциям) приписываются числа - длительности или стоимости операций. Такая сетевая модель наглядно отражает технологич. [8]

Для проведения расчетов с помощью ЭВМ разработана специальная макет-схема газовой промышленности, на которой изображены основные узлы и дуги газотранспортной сети. На схеме для каждой дуги задана определенная ориентация ( направление потока), следовательно, сеть является ориентированной. Для описания ориентированной сети пронумеруем узлы и обозначим дугу ( газопровод), исходящую из узла i и входящую в узел /, в виде ij, а структуру сети зададим матрицей узлы-дуги. Каждый узел отображается строкой такой матрицы, а каждая дуга ( газопровод) - столбцом. [9]

Взаимосвязь продуктов производимого ассортимента, определяемая. хемами их химического синтеза. [10]

При календарном планировании следует различать товарные и промежуточные продукты, так как для товарных продуктов определены директивные сроки выпуска, а для промежуточных они не установлены. Каждому продукту соответствует технологический маршрут. Последовательность производства продуктов задается в виде обобщенного технологического графа, имеющего вид ориентированной сети, вершины которой соответствуют продуктам, а дуги - последовательности их выпуска. [11]

Если на сети имеются каналы, различные по назначению, то такая сеть называется неоднородной. Каналы сети могут быть односторонними и двухсторонними. По каналам первого типа соединение устанавливается только в одну сторону, а по каналам второго типа - в обе стороны. Сеть, состоящая из односторонних каналов, называется ориентированной сетью, а сеть, состоящая из двухсторонних каналов, - неориентированной сетью. Если на сети имеются односторонние и двухсторонние каналы, то она называется смешанной. [12]

Предикатный информационный граф можно рассматривать как обобщение контактных схем и АДВ-модели, причем от контактных схем заимствована структура в виде сети с нагрузкой ребер функциями и использование функций проводимости, а от АДВ-модели - способ введения сложности сети. Кроме того, вводится алгоритм обхода сети, похожий на алгоритм разметки графа [51, 61], который можно рассматривать как соответствующий сети алгоритм поиска. Причем в каждой вершине сети, до которой на некотором запросе х дошел алгоритм поиска, каждое из ребер, исходящее из этой вершины, задает возможное направление поиска, и если на этом запросе х значение предиката, соответствующего ребру, равно 1, то в направлении данного ребра поиск продол жнется, а если равно 0, то по этому направлению поиск прекращается. Таким образом, из одной вершины сети может возникнуть сразу несколько направлений, по которым поиск продолжается. Но в задачах поиска часто встречается ситуация, когда из нескольких направлений поиска выбирается точно одно, например, так как это происходит в вершине ветвления алгебраического дерева вычислений, когда в зависимости от результата сравнения выбирается одно из двух направлений движения. В таких случаях гораздо удобнее приписать вершине функцию-переключатель и в зависимости от ее значения на запросе выбрать то направление, на которое указывает значение переключателя. Теперь если дана ненагруженная многополюсная ориентированная сеть, то нагрузку сети функциями будем осуществлять следующим образом. Сначала выберем в сети некоторое количество вершин, которые назовем точками переключения, и каждой точке переключения припишем некоторый переключатель из G и затем занумеруем подряд, начиная с 1, ребра, исходящие из нее. Такие ребра, исходящие из точек переключения, назовем переключательными. Остальные ребра назовем предикатными и нагрузим их предикатами из множества F. Нагрузим все полюсы сети, кроме корня, записями, причем можем считать, что одна и та же запись может быть приписана нескольким полюсам. Алгоритм обхода сети на запросе в этом случае полностью аналогичен описанному ранее за тем исключением, что если активная выбранная вершина является точкой переключения, то вычисляем значение переключателя, соответствующего вершине, на запросе ж, и если среди ребер, исходящих из этой вершины, есть ребро с номером, равным вычисленному значению, то включаем конец этого ребра в множество активных вершин, если только этот конец не был отмеченной вершиной. [13]

Предикатный информационный граф можно рассматривать как обобщение контактных схем и АДВ-модели, причем от контактных схем заимствована структура в виде сети с нагрузкой ребер функциями и использование функций проводимости, а от АДВ-модели - способ введения сложности сети. Кроме того, вводится алгоритм обхода сети, похожий на алгоритм разметки графа [51, 61], который можно рассматривать как соответствующий сети алгоритм поиска. Причем в каждой вершине сети, до которой на некотором запросе х дошел алгоритм поиска, каждое из ребер, исходящее из этой вершины, задает возможное направление поиска, и если на этом запросе х значение предиката, соответствующего ребру, равно 1, то в направлении данного ребра поиск продолжается, а если равно 0, то по этому направлению поиск прекращается. Таким образом, из одной вершины сети может возникнуть сразу несколько направлений, по которым поиск продолжается. Но в задачах поиска часто встречается ситуация, когда из нескольких направлений поиска выбирается точно одно, например, так как это происходит в вершине ветвления алгебраического дерева вычислений, когда в зависимости от результата сравнения выбирается одно из двух направлений движения. В таких случаях гораздо удобнее приписать вершине функцию-переключатель и в зависимости от ее значения на запросе выбрать то направление, на которое указывает значение переключателя. Теперь если дана ненагруженная многополюсная ориентированная сеть, то нагрузку сети функциями будем осуществлять следующим образом. Сначала выберем в сети некоторое количество вершин, которые назовем точками переключения, и каждой точке переключения припишем некоторый переключатель из G и затем занумеруем подряд, начиная с 1, ребра, исходящие из нее. Такие ребра, исходящие из точек переключения, назовем переключательными. Остальные ребра назовем предикатными и нагрузим их предикатами из множества F. Нагрузим все полюсы сети, кроме корня, записями, причем можем считать, что одна и та лее запись может быть приписана нескольким полюсам. Алгоритм обхода сети на запросе в этом случае полностью аналогичен описанному ранее за тем исключением, что если активная выбранная вершина является точкой переключения, то вычисляем значение переключателя, соответствующего вершине, на запросе ж, и если среди ребер, исходящих из этой вершины, есть ребро с номером, равным вычисленному значению, то включаем конец этого ребра в множество активных вершин, если только этот конец не был отмеченной вершиной. [14]

Страницы: 1