2-дерево
Cтраница 2
Как обычно, число р неподобных вершин 2-дерева означав число орбит на множестве вершин 2-дерева; аналогичные опре ( деления даются для числа q неподобных ребер и для числа неподобных ячеек. [16]
 |
Преобразование 2-де - а для 2-дерева a al - в ревьев в деревья. обратном направлении. [17] |
В этом уравнении, как и ранее, запятая разделяет номера узлов, принадлежащих разным частям 2-дерева. [18]
Для узлов 1 и 2 треугольного графа, приведенного на рис. 4 - 6, можно составить два 2-дерева. Исключение строки, соответствующей узлам 1 и 2, символически означает объединение одного узла с базисным. Так, между узлами / - 3 и 2 - 3 можно дорисовать по одной ветви, как это показано на рисунке. Этим узлы / или 2 попеременно превращаются в изолированные. Произведение проводимостей, относящееся к изолированному узлу ( как это уже указывалось), равно единице. [19]
Алгебраическое дополнение А12 согласно формуле ( 10 - 45) равно сумме величин 2-деревьев Trfna 1гцл, у которых узлы / и 2 находятся в одной части 2-дерева, а базисный узел /, - в другой. [20]
 |
Исходный граф G и граф Gh, соответствующий пути ad. [21] |
В результате получаем правило: алгебраическое дополнение А / А определителя А; равно сумме величин таких 2-де-ревьев, у которых узлы i и k находятся в одной части 2-дерева, а базисная вершина q - в другой. [22]
В соответствии с формулой ( 10 - 45) алгебраическое дополнение А ( А равно сумме величин всех 2-деревьев типа 1 ь ч, у которых узлы i и k находятся в одной части 2-дерева, а базисный узел q - в другой. На рис. 10 - 37 условно изображено одно из таких 2-деревьев. [23]
Последнее выражение содержит сумму величин 2-де-ревьев. В этой сумме учтены не все 2-деревья, а только такие, которые содержат узлы У и 2 в одной части 2-дерева, а базисную вершину 4 - в другой. [24]
В частности, для вставки нового элемента в биномиальную очередь мы превращаем новый элемент в 1-узловое сортирующее дерево. Далее, если N есть четное число ( значение самого правого разряда равно 0), мы просто помещаем это сортирующее дерево в самую правую пустую позицию биномиальной очереди. Если N - нечетное число ( значение самого правого разряда составляет 1), мы объединяем сортирующее 1-дерево, соответствующее новому элементу, с сортирующим 1-деревом в самой крайней правой позиции биномиальной очереди, в результате чего получаем сортирующее 2-дерево переноса. Если позиция, соответствующая 2 в биномиальной очереди, пуста, то сортирующее дерево переноса помещается в эту позицию, в противном случае производится слияние сортирующего 2-дерева переноса с сортирующим 2 деревом из биномиальной очереди, образуя при этом 4-дерево переноса, и так продолжая процесс до тех пор, пока не будет достигнута пустая позиция в биномиальной очереди. Этот процесс демонстрируется на рис. 9.17, а в программе 9.14 приведена его реализация. [25]
В частности, для вставки нового элемента в биномиальную очередь мы превращаем новый элемент в 1-узловое сортирующее дерево. Далее, если N есть четное число ( значение самого правого разряда равно 0), мы просто помещаем это сортирующее дерево в самую правую пустую позицию биномиальной очереди. Если N - нечетное число ( значение самого правого разряда составляет 1), мы объединяем сортирующее 1-дерево, соответствующее новому элементу, с сортирующим 1-деревом в самой крайней правой позиции биномиальной очереди, в результате чего получаем сортирующее 2-дерево переноса. Если позиция, соответствующая 2 в биномиальной очереди, пуста, то сортирующее дерево переноса помещается в эту позицию, в противном случае производится слияние сортирующего 2-дерева переноса с сортирующим 2 деревом из биномиальной очереди, образуя при этом 4-дерево переноса, и так продолжая процесс до тех пор, пока не будет достигнута пустая позиция в биномиальной очереди. Этот процесс демонстрируется на рис. 9.17, а в программе 9.14 приведена его реализация. [26]
Страницы: 1 2