26. Понятие транспортной сети (источник, сток, функция пропускных способностей, функция потока, величина потока)
К списку вопросов
Определение максимального потока сети.
1. fi - функция, которая ставит в соответствие каждому ребру а неотрицательное действительное число fi (а), называемое его пропускной способностью.
2. полустепенью исхода вершины Х назовем сумму пропускных способностей всех дуг вида аxz.
Аналогично определяем полустепень захода P (X) любой вершины Х:
3. сток - вершина, для которой P (W)=0; источник - P (V)=0.
4. будем называть сетью пару D,fi, где D - орграф, имеющий один источник и один сток (ровно); fi - функция пропускных способностей.
Обозн.: Nfi = (D, fi)
Определим поток через сеть как функцию fi, ставящую в соответствие каждой дуге а неотрицательное действительное число ?(a), называемое потоком через дугу а такое, что:
1. для любой дуги fi (a)Jfu(a);
2. для любого X (не источник и не сток)
Определим сеть потоков Nfi = (D, fi) как пару D и fi, где D - орграф из Nfi, а fi - поток через сеть.
Назовем дугу а, для которой fi (a)= fu(a) насыщенной, остальные - не насыщенные.
Из орлеммы о рукопожатиях следует, что сумма потоков через дуги, инцидентные источнику, равна сумме потоков через дуги, инцидентные стоку. Общая сумма называется величиной потока через данную сеть. Потоки имеющие max-ную величину, называются максимальными потоками.
К списку вопросов
