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

Иа условия сохранения штока в вершинах оледузт у слот е сохранения потока в оети: 2 . F C I R ) =X . V C T ) , ГеI t f s Ц- (12.4) "tr „ Величиной потока ^ называется чиоло , равное % = Z I L . (12.5) Поток т наэы. js'ioff макоимальным, оолн имеет напбольщую величину. При решении практичаоких задач предотавляот интерес проб­ лема отыскания максимального лотока в тпанспортнсй оети. Надп- ча о максимальном потоке оказыиаетоя тьоно 01,.занной о задачей о минимальном ^мэрезе. Ранее било определено понятие p a a j -а графа. Сузим это определение к болаэ удойному виду пра работе о транспортными сетями, Пуоть /4 с: V' - подмножеотр^-' веришн сети, удовл0 _гво1)яд- щее условиям; % ф А к ^ А • Тогда множество ^ i наэываетоя разрезом транспортной сети Т , . Очевидно, удаление и з ®рансп6ртной ос,™ Т воех дуг paapesu разрывает воа^ - (/-о • Если, напрмлер, А-1(Ло \ , то разрез^' =^.^=(1Г,«о)' J ' £("\ Ub )' i содержит только дуги, заходящие в сток, которые называют также выходными дугами оети. Если , '.о разрез « д = {Г=С«г.,1Г); гге ГОД)} .Лу г и »того разреза назаваютоя входными дугами саги, Пропускной споообноотыо разреза называется число = = Х - ^ С У ) . • (1Й.е) Разрез лавнвае' минимальным, еоли имеет наименьшую I п р -'уокную опсеобнооть с С ) . Приведем основные утверждения, отнссящивоя к задаче о мак- оима^'ном потоке. Л е т а 12.1. любого noroita Ч и лвзбого разреза в транспортной сети Т оправ едатво равенство ^ 2 1 ^ С Г ) - (18.7) " 3 . . g . . Для ли выполняется иеравэйство Демла юбого потока V и любого iMSpeaa в Т Vm., С (