Теория графов и комбинаторика

Оч0Ш5Д!га, воли для некоторого -.отокаV " п некоторого "Мд» доо'гцгаотоя равенство в (12,8), т . е . то ле­ гок маконмалышй, а разрез-^д». - минимальный. В силу соночноотн графа минимальный разрез мокет быть най- доп парзбором Еоех разрезов, но этот путь, конечно, неприеше?" дпя достаточно больших графов. Кроме ""угй, оотостаенен вопрос: шцилняотся лгл рапепотво в (12.8) да макот!даль':--го потока? Ответ на этот волрос ооотавляат оолерспашзе известной теореш Форда - «алкероона. Теошма 12.1. (Форд и Фалкерсои, 1953г.). Е любо-.трано- псрткой оети Т в№5чана любого максимального потока равна про­ пускной спооойнооти любого минимального разреза. Извеотно конотруктйвное доказательотво теореш I 2 . I , на оонованиц которого построен следуичий aлгo^JJтм. Алгоритм Форда - Фалкеробна макоимизациа потока в трано- портной сети: 1 . Перечумеровать вое верлглш оети произвольным образом, кроме и а о . . ! 2 . Задать Ht'Kc.jpHS начальный потек в оети. В чаот- ноотя, в качестве начального потока мовно выбрать 15улвЕ0й поток; V L F E R ^СГ)=0. 3 . Вершияам оети присвоить целочиож. miB метки, а дугам знвкя ила по следующим права^чм: а) вершине присвоить метку О ; Б) пусть '^1 - помеченная в е р т к а , a l i T - HQ помеченная Г";;шша. Тогда вершине е Г с п ) , для которой < с I ) присвоить метку " с " , а д г г е f ~ Сг^с присвоить знак Варшне и ^ е Г 'с^с) такой, что ^(.Ю-,1Т1)> 0 , присвоить МЭГ " "С " , а д у г е Г - ) - знак Осталь­ ные иепомвчеишй вершина ц дуги метки и знака т получают; в ) 80Ю1 в результате процалуры помечшгаиця (и.3,б) йершна Wo метки н е получает, то поток ^ - макоимальщй. В противном олучао перейти к п . 4 . 4 . Рвосмотреть пооледоветвльнооть вершин Л = метка каздой и з которых равна HOI .: следующей за ней вершины, и множество мугуМ , оовдинящих соседние верзины т:з А . Построить ловнй поток т С х ) по $ор.«.зулв i j \ j I если I f f c / ' ^ имеет знак \( X )^ j ЧС.Г) - £ ( м ) , волн ^ С ^ имеет знак 74