Пометка - вершина
Cтраница 2
Оценим количество операций в алгоритме Форда и Фалкерсо-на. Каждое увеличение потока приводит к появлению дуги с нулевым или насыщенным потоком по ней. Такая дуга далее не участвует в пометке вершин. Всего дуг U, а значит, для окончания алгоритма требуется не более 0 ( pf U) операций приращения потока. Сложность алгоритма является степенной. [16]
 |
Два графа, имеющие один и тот же знак. [17] |
Если граф Сне является четным, то хотя бы одна его вершина v имеет нечетную степень. Подмножество распределений из S, для которых пометка вершины v является положительной, и подмножество распределений из S, для которых она отрицательна, равномощны и вносят в сумму 2j ( - 1) разные по знаку и одинаковые по величине количества. [18]
Однако если матрица С является матрицей стоимостей, то дуги, приносящие доход, должны иметь отрицательные стоимости. Этот метод также является итерационным и основан на пометках вершин, причем в конце / с-й итерации пометки равны длинам тех кратчайших путей ( от 5 ко всем остальным вершинам), которые содержат не более & 1 дуг. В отличие от алгоритма Дейкстры никакая из пометок во время этого процесса не рассматривается как окончательная. [19]
Однако если матрица С является матрицей стоимостей, то дуги, приносящие доход, должны иметь отрицательные стоимости. Этот метод также является итерационным и основан на пометках вершин, причем в конце & - Й итерации пометки равны длинам тех кратчайших путей ( от s ко всем остальным вершинам), которые содержат не более k - f - 1 дуг. В отличие от алгоритма Дейкстры никакая из пометок во время этого процесса не рассматривается как окончательная. [20]
Во многих задачах необходимо обойти некоторое дерево ( например, дерево поиска), посещая каждую его вершину в точности один раз и выполняя при этом некоторую систематическую обработку информации, относящейся к этой вершине. Посещение каждой вершины дерева может быть связано или с выполнением простой операции, например с распечаткой пометки вершины дерева, или со сложной, например с вычислением некоторой функции. [21]
Страницы: 1 2