Cтраница 2
Сравниваем стоимости всех временных пометок и выделяем либо [4,3], либо [4,7] как постоянную пометку. [16]
P, это один из п первых помеченных постоянной пометкой групповых элементов, а он по предположению имеет корректную постоянную пометку. [17]
Кроме того, при осуществлении шагов 2 и 3 необходимо определить, какие вершины являются временными, а для этого нужно еще п ( п - 1) / 2 операций сравнения. Они действительно достигаются, если окажется, что вершина I будет последней вершиной, получившей постоянную пометку. [18]
Кроме того, при осуществлении шагов 2 и 3 необходимо определить, какие вершины являются временными, а для этого нужно еще п ( п - 1) / 2 операций сравнения. Они действительно достигаются, если окажется, что вершина t будет последней вершиной, получившей постоянную пометку. [19]
Вначале все дуги сети не принадлежат дереву: узлы ЛГ4, Nz, N3 - соседние с узлом Ns. Так как min ( 4, 3, 1) 1, то пометка ( 1, s) становится постоянной пометкой узла N3, a дуга AS3 становится дугой дерева. [20]
Подсчитаем, какое число операций сложения и сравнения требуется для выполнения алгоритма. На шаге 3 нужно выполнить не более п операций сложения и п операций сравнения, чтобы получить временные пометки. На шаге 1 нужно выполнить еще не более п сравнений, чтобы получить постоянную пометку. [21]