Входящее дерево

Cтраница 1

Входящее дерево получается из корневого дерева Т с корнем и ориентированием всех его ребер по направлению к вершине и. Выходящее дерево является ориентированно-двойственным к выходящему. [1]

Процедура преобразования входящего дерева в ы-цепъ лишь незначительно отличается от описанной процедуры для выходящего дерева. На каждом шаге в качестве опорной выбирается вершина i, все непосредственные предшественники которой не имеют предшественников в дереве, полученном после выполнения предыдущего шага. Цепь С0 получается присоединением вершины i к со-цепи С0 справа. [2]

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

Это невозможно для входящего дерева. [4]

Граф будем называть входящим деревом ( обозначение: & - -), если при изменении ориентации всех его дуг на противоположную получается выходящее дерево. [5]

Таким образом, если G - входящее дерево, d - О u ti 1 ( tl n), то для построения допустимого относительно директивных сроков расписания ( если оно существует) достаточно: а) вычислить модифицированные директивные сроки Di ( требуется выполнить не более 0 ( п) операций); б) получить список К требований, упорядоченных по неубыванию значений DI ( не более O ( nlogn) операций, см. гл. В результате выполнения не более O ( nlogn) операций будет построено допустимое расписание либо сделано заключение о том, что допустимого расписания не существует. [6]

Остовные входящие и выходящие деревья. [7]

На этом же рисунке показаны три остовных входящих дерева орграфа D, у которых и4 - сток. [8]

Теорема 3.1. Если граф G - выходящее ( входящее дерево, то существует последовательность преобразований I, II, переводящая G в ю-цепь. [9]

Изолированная вершина по определению является одновременно и выходящим, и входящим деревом. [10]

Перейдем к рассмотрению ситуаций, когда граф G является выходящим или входящим деревом. [11]

Пусть каждая компонента связности графа G редукции отношения строгого порядка - является входящим деревом. [12]

Рассмотрим задачу построения допустимого относительно заданных директивных сроков расписания в предположении, что граф G является входящим деревом. [13]

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

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

Страницы: 1 2