Cтраница 1
Книга Басакера и Саати Конечные графы и сети рассчитана на лиц, занимающихся использованием теории графов при решении различных задач в области техники, экономики, социологии. Она содержит основные понятия теории графов, достаточно полный перечень научных результатов и описание методов решения различных задач. [1]
В алгоритме Басакера на / - м шаге определяется наиболее дешевый путь из источника в ток, по которому можно увеличить поток. [2]
Модифицированный алгоритм Басакера - Гоуэна. [3]
Модифицированный алгоритм Басакера - Гоуэна в задаче о потоках с множителями может не обеспечивать сходимости. Рассмотрим прием, гарантирующий достаточную для практики точность и быстродействие. Будем считать, что поток хц насыщает дугу и графа приращений, если 7 - х ц е, где е - число, определяющее точность вычислений. [4]
Ряд авторов ( Басакер и Саати [1965], Ледерберг [1964], Скойнс [1968], Вейнберг [1965]) предлагают такие способы упорядочения; эти способы мало отличаются друг от друга. Алгоритм Эдмондса ( см. Басакер и Саати [1965]) является хорошим примером такого упорядочения. В данном корневом дереве вершины на каждом уровне упорядочиваются, начиная с вершин, которые располажены дальше всех от корня. Вершины на ( i - 1) - м уровне упорядочиваем лексикографически по их спискам в соответствии с порядком, который получили вершины на i - м уровне. После того как вершины упорядочены на каждом уровне, построить каноническое дерево легко. Но ни Эдмондс, ни другие авторы не заметили, что сам процесс упорядочения не так прост, и чтобы получить оценку числа действий 0 ( F), этот процесс нужно тщательно определить и аккуратно реализовать. [5]
Первый алгоритм, предложенный Басакером и Гоуэном [22], имеет следующий вид. [6]
Алгоритм нахождения оптимального потока на сети, предложенный Басакером и Гоуэном, состоит из ряда шагов. [7]
Если ввести взаимно-однозначное соответствие у - Ig к -, и - - Ig cu, то эти условия станут эквивалентными условиям оптимальности в задаче о потоке минимальной стоимости, поэтому для решения задачи ( 9) можно использовать модифицированный алгоритм Басакера - Гоуэна, в котором вместо путей минимальной стоимости в графе приращений на каждой итерации отыскивается путь с минимальными потерями потока. [8]
Двойственные алгоритмы оперируют оптимальными решениями двойственной задачи для коррекции начального недопустимого потока. Идея двойственного алгоритма Басакера - Гоуэна состоит в последовательном наращивании потока из источника в сток до требуемой величины, начиная от нулевого потока. Каждый новый поток образуется из предыдущего за счет наращивания потока вдоль кратчайшего пути из источника в сток в графе приращений. [9]
Поток по введенной дуге указывает величину прироста пропускной способности исходной коммуникации. Используем модифицированный алгоритм Басакера - Гоуэна. Изменения касаются построения графа приращений и кратчайшего пути в нем. Отправляясь от нулевого потока в расширенной сети, будем последовательно наращивать до максимальной величины поток в сети, используя для этого кратчайшие цепи, ведущие из источника 0 в сток N. Как и раньше, цепи однозначно соответствуют путям из 0 в N в графе приращений. [10]
Ряд авторов ( Басакер и Саати [1965], Ледерберг [1964], Скойнс [1968], Вейнберг [1965]) предлагают такие способы упорядочения; эти способы мало отличаются друг от друга. Алгоритм Эдмондса ( см. Басакер и Саати [1965]) является хорошим примером такого упорядочения. В данном корневом дереве вершины на каждом уровне упорядочиваются, начиная с вершин, которые располажены дальше всех от корня. Вершины на ( i - 1) - м уровне упорядочиваем лексикографически по их спискам в соответствии с порядком, который получили вершины на i - м уровне. После того как вершины упорядочены на каждом уровне, построить каноническое дерево легко. Но ни Эдмондс, ни другие авторы не заметили, что сам процесс упорядочения не так прост, и чтобы получить оценку числа действий 0 ( F), этот процесс нужно тщательно определить и аккуратно реализовать. [11]