4551
правка
Сепараторы в графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 49: | Строка 49: | ||
Дано: граф с взвешенными ребрами <math>G = (V, E, c) \;</math>, товары <math>(s_1, t_1, D_1), ..., (s_k, t_k, D_k) \;</math>. | Дано: граф с взвешенными ребрами <math>G = (V, E, c) \;</math>, товары <math>(s_1, t_1, D_1), ..., (s_k, t_k, D_k) \;</math>. | ||
Требуется: обеспечить управление несколькими товарными потоками, направляющее <math>f D_i \;</math> единиц товара i из <math>s_i \;</math> в <math>t_i \;</math> для каждого i одновременно, не нарушая заданной емкости каждого ребра. | Требуется: обеспечить управление несколькими товарными потоками, направляющее <math>f D_i \;</math> единиц товара i из <math>s_i \;</math> в <math>t_i \;</math> для каждого i одновременно, не нарушая заданной емкости каждого ребра. | ||
Цель: максимизация f. | Цель: максимизация f. | ||