Логические (булевы) функции основные логические функции

ts
Рис. 8
Заметим, что дуга, выходящая из источника, и дуга, входящая в сток, должны быть обязательно прямыми. Прибавим  _s к c_ij для прямых дуг этой цепи (по построению видно, что полученное число будет меньше или равно q_ij) и вычтем это  _s из c_ij для обратных дуг (может получиться отрицательное число, но оно обязательно будет по абсолютной величине меньше q_ij, так как по построению  _s   c_ij+q_ij , а это означает, что обратная дуга меняет направление, становится прямой дугой и его “нагрузка” будет равна модулю числа  Тогда новые числа для дуг, входящих в нашу цепь, а также “старые” c_ij для всех дуг, не входящих в нашу цепь, образуют новый поток из вершины t в вершину s (легко проверить простым рассуждением, что для новых чисел выполняются условия (1)–(4)). Кроме того, величина нового потока по сравнению со старым увеличилась на _s > 0 . Для нового потока снова проведем ту же процедуру и т. д.
Так как каждый раз величина потока увеличивается, по крайней мере, на 1 (пропускные способности ребер являются целыми числами), а величина максимального потока ограничена (величиной минимального сечения), то эта процедура не может продолжаться бесконечно и, значит, на каком-то шаге получим поток, для которого вершина s не входит в Y, т. е. поток является максимальным и величина его равна величине минимального сечения. Теорема доказана.
Рассуждение теоремы Форда – Фалкерсона фактически является алгоритмом нахождения максимального потока между двумя вершинами (или доказательством того, что этот поток является максимальным). Подробный пример на эту тему приведен в разд. 15 “Решение типовых задач”.
Примечание. Если в данном графе с пропускными способностями ребер (т. е. сети) имеется несколько источников и несколько стоков, то описанный выше алгоритм можно применить следующим образом. Вводим новый источник и новый сток, причем новый источник соединяем ребрами со всеми источниками, а новый сток – со всеми стоками, при этом пропускные способности новых ребер считаем сколь угодно большими числами, так что эти дуги в любом возможном потоке были бы ненасыщенными (напомним, что ребра, идущие из источника и ребра, идущие в сток всегда являются прямыми дугами). После этого для нового графа решаем задачу о максимальном потоке (из одного нового источника в один новый сток). Решив ее, стираем все введенные ребра и вершины.
Рассмотрим еще некоторые вопросы (достаточно общего характера) из теории графов. Заметим, что в следующих разделах мы приводим только самые простые доказательства, а основные доказательства приведены в книге Р. Уилсона [6].