Полный поток в транспортной сетиПотоки в сетях Полный поток в транспортной сети Теория транспортных сетей возникла при решении задач, связанных с организацией перевозки грузов. Тем не менее понятие потока на транспортной сети, алгоритм нахождения потока наибольшей величины и критерий существования потока, насыщающего выходные дуги сети, оказались полезными для многих других прикладных и теоретических вопросов комбинаторного характера. Введем основные понятия данной теории. Транспортной сетью называется орграф D = (V,X) с множеством вершин V = {v1,…,vn}, для которого выполняются условия: 1) существует одна и только одна вершина v1, называемая источником, такая, что Г-1 (v1) = Æ (т.е. ни одна дуга не заходит в v1), 2) существует одна и только одна вершина vn, называемая стоком, такая, что Г(vn) = Æ (т.е. из vn не исходит ни одной дуги), 3) каждой дуге xÎX поставлено в соответствие целое число c (x) ³ 0, называемое пропускной способностью дуги. Функция j(x), определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если 1) для любой дуги xÎX величина j(x), называемая потоком по дуге x, удовлетворяет условию 0 £ j(x) £ c(x), 2) для любой промежуточной вершины v сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v. Величиной потока j в транспортной сети D называется величина, равная сумме потоков по всем дугам, заходящим в сток, или, что то же самое сумме потоков по всем дугам, исходящим из источника. Дуга xÎX называется насыщенной, если поток по ней равен ее пропускной способности. Поток j называется полным, если любой путь в сети из источника в сток содержит, по крайней мере, одну насыщенную дугу.
|
