Оказывается, дело здесь в том, что в следующих друг за другом итерациях помеченные вершины включались ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Ловас Л.N. Прикладные задачи теории графов


Оказывается, дело здесь в том, что в следующих друг за другом итерациях помеченные вершины включались нами в множество просмотренных с использованием разных правил. Назовем процедуру помечивания состоятельной, если всякий раз, когда имеется некоторое множество помеченных, но не просмотренных вершин, выбор вершин для отнесения их к множеству просмотренных осуществляется по одному и тому же правилу. Таккер ( 1977) доказал, что если состоятельная процедура помечивания применяется вместе с потоковым алгоритмом Форда - Фалкерсона, то алгоритм завершает работу и приводит к максимальному потоку. Фалкерсоном сформулирована ( но не опубликована) следующая гипотеза.

(cкачать страницу)

Смотреть книгу на libgen

Оказывается,  дело здесь в том,  что в следующих друг за другом итерациях помеченные вершины включались нами в множество просмотренных с использованием разных правил.  Назовем процедуру помечивания состоятельной,  если всякий раз,  когда имеется некоторое множество помеченных,  но не просмотренных вершин,  выбор вершин для отнесения их к множеству просмотренных осуществляется по одному и тому же правилу.  Таккер ( 1977) доказал,  что если состоятельная процедура помечивания применяется вместе с потоковым алгоритмом Форда  -  Фалкерсона,  то алгоритм завершает работу и приводит к максимальному потоку.  Фалкерсоном сформулирована ( но не опубликована) следующая гипотеза.