Список - ребро
Cтраница 2
Опишем схему включения новых ребер, которая неэффективна по затратам памяти, но легко поддается описанию. Она равносильна интерпретации списка отрезков многоугольника в виде описанного выше списка ребер. Если новое ребро появляется ( по координате X) между левым и правым ребрами, ограничивающими имеющийся отрезок, то отрезок расщепляется. Позднее этот список будет сделан более компактным. [16]
X - список вершин графа; ( ul, u2) - сортированный список ребер графа; We - веса ребер согласно их сортировке; ( uol, uo2) - ребра остовного дерева; Woe - веса ребер остовного дерева; Вес - сумма весов ребер остовного дерева. [17]
В предыдущем параграфе любой из рассмотренных кодов определялся как семейство подмножеств множества номеров звеньев. Отсюда и из определения гиперграфа следует, что всякий код можно рассматривать как список ребер гиперграфа, множество вершин которого в общем случае соответствует некоторому подмножеству множества номеров звеньев механизма, а ребра гиперграфа интерпретируются как тот или иной элемент коробки передачи: дифференциал, тормоз, муфта. [18]
Поскольку такое изменение упорядоченности не влияет на ее правильность, то и упорядочение (3.6) является правильным. Отметим, что в рассуждениях, подтверждающих правильность упорядочения (3.6), мы фактически описали немного другой способ получения правильного упорядочения нового множества J, которое требует двух просмотров списка ребер. [19]
 |
Иллюстрация к получению нижней оценки сложности решения задачи ТРИАНГУЛЯЦИЯ. [20] |
XN, показанное на рис. 5.7. N - 1 точек множества лежат на одной прямой, а одна точка находится вне этой прямой. Триангуляция этого множества может быть выполнена единственным способом, как это показано на рисунке. Список ребер, порождаемый алгоритмом триангуляции, можно использовать для получения упорядоченного списка чисел xi, затратив на это дополнительно О ( N) операций. [21]
Оценим теперь вычислительную сложность алгоритма. Циклы 22 и 25 требуют О ( я) шагов, причем для второго цикла не учитываются шаги, выполняемые при вызове ДВУСВ ( и 0) для каждой еще нерассмотренной вершины. Такой вызов для компоненты связности с п - вершинами и т - ребрами требует О ( щ - - rrii) шагов, не считая шагов в цикле 10, так как такая процедура ведет в компоненте поиск в глубину, требуя число шагов, ограниченное константой для каждого просматриваемого ребра. Каждое ребро удаляется из стека и попадает в список ребер блока в точности один раз, что дает в сумме О ( т) шагов, совершаемых циклом 10 во время его выполнения всего алгоритма. [22]
А вот ребро BD короче ребра AD, и поэтому должно его заменить. Вес ребра EG меньше веса ребра BG, поэтому оно замещает последнее. Из четырех ребер, ведущих в кайму, наименьший вес имеет АС, поэтому следующим к дереву добавляется оно. Добавление к остовному дереву вершины С и ребра АС ( рис. 6.5 ( д)) не приводит к изменению списка ребер. [23]
Страницы: 1 2