Пометка - вершина
Cтраница 1
Пометки вершин обновляются так же, как и раньше, и показаны на рис. 7.13 а вместе с необходимыми для построения дерева дополнительными ребрами. [1]
Линейные пометки вершин определяются от листьев к корню следующим алгоритмом. [2]
После пометки вершин возможны два случая: вершина z оказалась либо помеченной, либо непомеченной. [3]
Прямая польская запись простого выражения получается последовательным выписыванием пометок вершин во время их посещения при прямом обходе дерева этого выражения. Обратная польская запись простого выражения получается последовательным выписыванием пометок вершин во время их посещения при обратном обходе дерева этого выражения. [4]
В силу условий 4 и 5 определения канонического дерева нелинейные пометки вершин, лежащих над произвольной вершиной с линейной пометкой, чередуются, начиная с пометки V. Нелинейная пометка корня восстанавливается по следующему правилу. [5]
В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от я к этой вершине. Эти пометки ( их величины) постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от 5 к рассматриваемой вершине. Опишем этот метод подробно. [6]
В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от s к этой вершине. Эти пометки ( их величины) постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от s к рассматриваемой вершине. Опишем этот метод подробно. [7]
 |
Перераспределение потока на основе пометки вершин.| Максимальный поток. [8] |
Выполненное перераспределение потока сохраняет все его свойства и увеличивает на единицу поток в вершину z - Таким образом, пометка вершины z позволяет увеличить поток как минимум на единицу, а значит, алгоритм конечен, т.е. наступит момент, когда вершина z останется непомеченной. [9]
Отметим, что если xt Г ( 5), то кратчайший путь от s к xt не может состоять из ft 1 дуг и поэтому изменять пометку вершины xt не нужно. [10]
Отметим, что если х1 Г ( 5), то кратчайший путь от 5 к х1 не может состоять из А - - 1 дуг и поэтому изменять пометку вершины х ( не нужно. [11]
Множество точек n - симплекса S называется допустимо помеченным, если оно содержит все вершины S и все эти вершины помечены от 0 до п в любом порядке, так что каждая пометка присвоена в точности одной вершине, а всякая другая точка этого множества помечена одной из пометок вершин ее носителя. [12]
 |
Неполный связный орграф без петель и кратных ребер.| Мультиграф с петлями.| Многопоточная передача. [13] |
Два помеченных графа GJ и G2 называются изоморфными, если существует взаимно однозначное отображение множества X ( Gj) на множество X ( G2), сохраняющее не только смежность, но и распределение пометок. Сразу же оговоримся, что пометки вершин в СС и ГЧВ отличаются от принятых в теории графов; подробнее об этом будет сказано ниже. [14]
Прямая польская запись простого выражения получается последовательным выписыванием пометок вершин во время их посещения при прямом обходе дерева этого выражения. Обратная польская запись простого выражения получается последовательным выписыванием пометок вершин во время их посещения при обратном обходе дерева этого выражения. [15]
Страницы: 1 2