Cтраница 2
Оказывается, дело здесь в том, что в следующих друг за другом итерациях помеченные вершины включались нами в множество просмотренных с использованием разных правил. Назовем процедуру помечивания состоятельной, если всякий раз, когда имеется некоторое множество помеченных, но не просмотренных вершин, выбор вершин для отнесения их к множеству просмотренных осуществляется по одному и тому же правилу. Таккер ( 1977) доказал, что если состоятельная процедура помечивания применяется вместе с потоковым алгоритмом Форда - Фалкерсона, то алгоритм завершает работу и приводит к максимальному потоку. Фалкерсоном сформулирована ( но не опубликована) следующая гипотеза. [16]
Как и прежде, некоторые из этих граней лежат внутри первоначального симплекса, а некоторые лежат на границе. Те, что лежат внутри, должны быть инцидентны в точности двум симплексам подразделения по одному с каждой стороны грани. По предположению индукции сильное утверждение справедливо для симплексов размерности k, и, следовательно, число - граней подразделения, учитываемых один раз, нечетно. При общем подсчете, как и прежде, это нечетное число складывается с удвоенным числом - граней, подсчитываемых дважды, так что снова получается нечетное число. Тогда, как и прежде, 2а Ь - нечетное число и отсюда вытекает, что b нечетно. Так как b - число симплексов подразделения с вершинами, несущими все пометки от 0 до k 1, то этим доказывается сильное утверждение для каждого допустимого помечивания любого подразделения произвольного ( k 1) - симплекса. [17]