Cтраница 1
Выходящее дерево является ориентированно-двойственным к выходящему. [1]
Выходящее дерево называется 2 - 3-деревом, если из каждой его вершины, не являющейся висячей, исходит две или три дуги. Выходящее дерево называется сбалансированным, если длины всех путей из его корпя в висячие вершины одинаковы. Высотой дерева называется высота его корня. [2]
G - выходящее дерево, предложен У. Курису [322] предложил алгоритм ( с оценкой временной сложности O ( nlogn)) решения задачи 2 X п Беллмана - Джонсона при наличии ограничений предшествования, определяемых графом G, каждая компонента связности которого - цепь. Здесь ограничения предшествования ( отношение - -) имеют следующий смысл. [3]
Таким образом, при преобразовании выходящего дерева d в со-цепь реализация всех процедур поиска объединяемых со-цепей, удаления из текущего графа вершин, соответствующих этим цепям, п сопоставления опорной вершине t цени С0 требует выполнения не более чем 0 ( nCl операций. [4]
Таким образом, реализация процедуры преобразования выходящего дерева в w - цепь требует выполнения не более CKwilog / ti) операций. [5]
Пусть каждая компонента связности графа G является выходящим деревом. Заменим ориентацию каждой дуги этого графа на противоположную. В результате получаем граф G, каждая компонента которого является входящим деревом. Ясно, что граф G является графом редукции отношения строгого порядка, обратного исходному. [6]
Каждая компонента графа G редукции построенного отношения - является выходящим деревом. [7]
Применяя описанные преобразования к G ( i), получим некоторое выходящее дерево G ( 2), и так до тех пор, пока не будет получен граф Gw, состоящий из единственной вершины. Цепь, сопоставленная этой вершине, является искомой w - цепью. [8]
Процедура преобразования G в ы-цепъ состоит в последовательном переходе от одного выходящего дерева к другому, имеющему меньшее число вершин. Преобразования проводятся до тех пор, пока не будет получен граф, состоящий из единственной вершины. При этом вершинам деревьев на каждом шаге сопоставляются некоторые со-цепп. [9]
Предположим, что V - это г. Из приведенных выше рассмотрений и определения выходящего дерева следует, что вершина г является в Г началом каждого из & ребер А. [10]
Процедура преобразования входящего дерева в ы-цепъ лишь незначительно отличается от описанной процедуры для выходящего дерева. На каждом шаге в качестве опорной выбирается вершина i, все непосредственные предшественники которой не имеют предшественников в дереве, полученном после выполнения предыдущего шага. Цепь С0 получается присоединением вершины i к со-цепи С0 справа. [11]
Нетрудно убедиться, что каждая компонента связности графа G редукции построенного отношения порядка является выходящим деревом. [12]
Аналогичным приемом можно воспользоваться и в случае, когда число приборов произвольно, граф G является выходящим деревом, моменты поступления требований в очередь на обслуживание различны, а все директивные сроки одинаковы. [13]
Граф будем называть входящим деревом ( обозначение: & - -), если при изменении ориентации всех его дуг на противоположную получается выходящее дерево. [14]
Входящее дерево получается из корневого дерева Т с корнем и ориентированием всех его ребер по направлению к вершине и. Выходящее дерево является ориентированно-двойственным к выходящему. [15]