Ориентированный ациклический граф

Cтраница 1

Ориентированный ациклический граф ( DA-граф 1)) - это ориентированный граф, не имеющий циклов ни в одной вершине. [1]

Ориентированный ациклический граф ( DA-граф х)) - это ориентированный граф, не имеющий циклов ни в одной вершине. [2]

Двоичное дерево и его представление. [3]

Ориентированный граф без циклов называется ориентированным ациклическим графом. [4]

Схему можно также представлять в виде ориентированного ациклического графа, у которого вершины входной степени 0 ( входы) помечены исходными переменными; остальные вершины ( функциональные элементы) помечены функциями из базиса ( при этом входная степень вершины должна совпадать с количеством аргументов ее пометки); ребра помечены числами, указывающими номера аргументов; вершины выходной степени 0 ( выходы) помечены переменными, описывающими результат работы схемы. УЙ, из которых ведут ребра в данную вершину v, вершина v получает значение у fv ( yi, , ykv), где fv - базисная функция, которой помечена вершина. При переходе к графу схемы мы опускаем несущественные присваивания, которые ни разу не используются на пути к выходным вершинам, так что они никак не влияют на результат вычисления. [5]

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

Лемма 5.12. Пусть G ( У, Е) - ориентированный ациклический граф с корнем г, a S ( V, Т) - остовное дерево для него с корнем г, построенное поиском в глубину. [7]

Говоря неформально, можно сказать, что мы строим доминатор-ное дерево для данного ориентированного ациклического графа G ( V, E) следующим образом. Номера узлов графа G меняем на их номера, порожденные поиском в глубину. Затем применяем к G преобразования из лемм 5.12 - 5.14. Они выполняются двумя взаимосвязанными подпрограммами, одна из которых обрабатывает прямые ребра, а другая - поперечные. [8]

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

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

Мы построим алгоритм сложности О ( е log e), вычисляющий доминаторное дерево для корневого ориентированного ациклического графа с е ребрами. Основная наша цель - показать, как комбинировать технику этой главы и предыдущей. Алгоритм основан на трех леммах. [11]

Слова в алфавите А будем называть текстами в алфавите А, сетью из текстов ( Г - сетыо) - связный ориентированный ациклический граф следующего вида. [12]

Ориентированный граф, состоящий из нескольких деревьев, называется лесом. Леса и деревья - столь часто встречающиеся частные случаи ориентированных ациклических графов, что для описания их свойств стоит ввести специальную терминологию. [13]

Наконец отметим, что эта программа предполагает ацикличность отношения has share. Тем самым предполагается, что отображение отношения собственности фактически является ориентированным ациклическим графом. На самом деле программа также является корректной при менее жестких ограничениях, а именно при условии ацикличности отношения controlled. Это условие непосредственно следует из предыдущего. [14]

Методы, развитые в предыдущих разделах этой главы, приме нимы к совершенно произвольным графам. Но на практике задачу кратчайшего пути часто требуется решать для класса ориентированных ациклических графов. [15]

Страницы: 1 2