Глава 22, Потоки в сетях. вых, потоки в сети всегда дают допустимое сочетание: поскольку в каждую вершину входит (из истока) ребро с пропускной способностью

вых, потоки в сети всегда дают допустимое сочетание: поскольку в каждую вершину входит (из истока) ребро с пропускной способностью, равной единице, либо выходит из нее (в сток), то через каждую вершину может пройти только единица потока, от­куда, в свою очередь, следует, что каждая вершина может быть использована для со­четания только один раз. Во-вторых, ни одно сочетание не может использовать боль­шее число ребер, поскольку такое сочетание может непосредственно привести к большей величине потока, чем та, которая получена по алгоритму вычисления макси­мального потока. ■

Например, на графе из рис. 22.38 алгоритм вычисления максимального потока методом аугментальных путей может использовать пути s-0-6-t, s-l-7-t, s-2-7-t, s-4-9-t, s-5-10-t и s-3-6-0-7- 1-11-t для вычисления сочетания 0-7, 1-11, 2-8, 3-6, 4-9 и 5-10. Следовательно, су­ществует способ трудоустройства всех студентов в задаче, показанной на рис. 22.3.

Программа 22.7 является клиентской программой, которая считывает задачу о двудоль­ном сочетании со стандартного ввода и использует сведение, задействованное при дока­зательстве существования ее решения. Каким будет время выполнения этой программы на крупных сетях? Разумеется, время выполнения зависит от выбора алгоритма вычисле­ния максимального потока и используемой его реализации. Кроме того, мы должны при­нять во внимания тот факт, что для сетей, которые мы строим, характерна специальная структура (двудольные транспортные сети с единичной пропускной способностью ребер), благодаря чему время выполнения различных алгоритмов вычисления максимальных по­токов не только не приближается к границам, определенным для худшего случая, но и существенно снижают эти границы. Например, первая граница, которую мы подвергли анализу, определяет быстрый отклик для случая выполнения обобщенного алгоритма вы­числения аугментальных путей.