Сепараторы в графах: различия между версиями

Требуется: найти b-сбалансированный сепаратор (<math>(S : V \; \backslash \; S)</math>.

 

Цель: минимизировать вес ребер <math>c( \delta(S)) \;</math>.

Требуется: обеспечить управление несколькими товарными потоками, направляющее <math>f D_i \;</math> единиц товара i из <math>s_i \;</math> в <math>t_i \;</math> для каждого i одновременно, не нарушая заданной емкости каждого ребра.  

Цель: максимизация f.

Задача 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).

'''Задача 5 (самое неплотное сечение (неоднородное))'''

Дано: граф с взвешенными ребрами <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>(c( \delta (S)))/(D(S, V \; \backslash \; S)) \;</math>.