Cтраница 2
Выходящее дерево называется 2 - 3-деревом, если из каждой его вершины, не являющейся висячей, исходит две или три дуги. Выходящее дерево называется сбалансированным, если длины всех путей из его корпя в висячие вершины одинаковы. Высотой дерева называется высота его корня. [16]
Действительно, пронумеруем элементы X следующим образом. Корню выходящего дерева сопоставим номер один. Пусть v-му рангу графа G принадлежит rv вершин. [17]
Для этого изменим ориентацию всех дуг дерева на противоположную и пронумеруем вершины, как в случае выходящего дерева. Таблица, представляющая входящее дерево, отличается от таблицы, представляющей выходящее дерево, второй и четвертой строкой. Здесь вторая строка - номер прямого потомка, а четвертая строка - минимальный п максимальный номера непосредственных предшественников. Выбор опорной вершины осуществляется по последней непустой кл етке таблицы, представляющей текущий граф: содержимое соответствующей клетки второй строки есть номер опорной вершины. Реализация процедуры преобразования входящего дерева в ш-цепь также требует выполнения не более O ( HI log n операций. [18]
Обслуживание требования i е N может быть осуществлено любым из приборов в течение tf единиц времени. Прерывания процесса обслуживания требования не допускаются. Каждая компонента связности G представляет собой выходящее дерево. [19]
Для этого изменим ориентацию всех дуг дерева на противоположную и пронумеруем вершины, как в случае выходящего дерева. Таблица, представляющая входящее дерево, отличается от таблицы, представляющей выходящее дерево, второй и четвертой строкой. Здесь вторая строка - номер прямого потомка, а четвертая строка - минимальный п максимальный номера непосредственных предшественников. Выбор опорной вершины осуществляется по последней непустой кл етке таблицы, представляющей текущий граф: содержимое соответствующей клетки второй строки есть номер опорной вершины. Реализация процедуры преобразования входящего дерева в ш-цепь также требует выполнения не более O ( HI log n операций. [20]
А в дереве Т ( см. разд. Я и К и вершина г содержится в К, то ребро А ориентируется из конца, принадлежащего графу К, в конец, содержащийся в графе Я. Так определенный орграф Г называется деревом, растущим из г ( или выходящим деревом ], а вершина г - его корнем. [21]