4551
правка
Сепараторы в графах: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
Задача 4 может быть решена за полиномиальное время при помощи методов линейного программирования. Она также допускает произвольную аппроксимацию при помощи нескольких более эффективных комбинаторных алгоритмов (см. раздел «Реализация»). Максимальное значение f, для которого возможно управление несколькими товарными потоками, называется [[максимальный поток|максимальным потоком]] для данного экземпляра задачи. ''Минимальным сечением'' является минимальное соотношение <math>(c( \delta (S)))/(D(S, V \; \backslash \; S)) \;</math>, где <math>D(S, V \; \backslash \; S) = \sum_{i: | \{ | Задача 4 может быть решена за полиномиальное время при помощи методов линейного программирования. Она также допускает произвольную аппроксимацию при помощи нескольких более эффективных комбинаторных алгоритмов (см. раздел «Реализация»). Максимальное значение f, для которого возможно управление несколькими товарными потоками, называется [[максимальный поток|максимальным потоком]] для данного экземпляра задачи. ''Минимальным сечением'' является минимальное соотношение <math>(c( \delta (S)))/(D(S, V \; \backslash \; S)) \;</math>, где <math>D(S, V \; \backslash \; S) = \sum_{i: | \{ s_i, t_i \} \; \cap \; S | = 1} D_i</math>. Эта двойственная интерпретация приводит нас к самой общей версии задачи – нахождению неоднородного самого неплотного сечения (задача 5). | ||
| Строка 61: | Строка 61: | ||
Дано: граф с взвешенными ребрами <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>(S : V \; \backslash \; S)</math>, | Требуется: найти минимальное сечение <math>(S : V \; \backslash \; S)</math>, иначе говоря, сечение с минимальным соотношением <math>(c( \delta (S)))/(D(S, V \; \backslash \; S)) \;</math>. | ||