Дискретная математика

166 2) существует единственная вершина v^, называемая выходом или стоком, из которой не исходит никакая дуга (полустепень исхода вершины Vk равна нулю); 3) каждой дуге х поставлено в соответствие неотрицательное действительное число у/(х), называемое пропускной способностью дуги. Вершины в транспортной сети S, отличные от источника и стока, называются промежуточными. Потоком (р в сети называется действительнозначная функция <р. определенная на множестве дуг графа и удовлетворяющая следующим свойствам: 1) для любой дуги X, (р(х)> 0: 2) (р(х)< ц/(х) - поток по любой дуге х не превосходит ее пропускной способности; 3) для любой променсуточной вершины v выполняется равенство: J (р(х)- Ц л : J = О, где - множество дуг графа, xeCv XEUY соответственно заходящих в промежуточную вершину v и выходящих из нее. Это условие называется условием сохранения: в любой промежуточной вершине поток не создается и не исчезает. Условие 3) можно сформулировать и следующим образом: сумма потоков по дугам, заходящим в произвольную промежуточную вершину сети, равна сумме потоков по дугам, исходящим из этой вершины. Дуга называется насыгцеиной, если поток по ней равен её пропускной способности. Притоком на выходеv j сети называется величина = 2 'Pfx)• Пусть AcrV- такое подмножество вершин сети, что vo^A, VkSA. Разрезом сети относительно множества вершин А называют множество дуг, исходящих из вершин, не принадлежащих А, и заходящих в вершины^. Пропускной способностью разреза называют число у/{и'^)= '^у/{х), XSW^ равное сумме пропускных способностей дуг разреза . Разрез с минимальной пропускной способностью называется миншальным разрезом. Поток в сети называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в данной сети. Любой элемент, движущийся от VQ К VJ , обязательно пройдет по какой- либо дуге разрйа каков бы ни был этот разрез. Можно детсазать следующую террему.