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

Задача о (сбалансированном) сепараторе заключается в нахождении сечения минимального (реберного) веса в графе, такого, что два сегмента графа имеют примерно одинаковый (вершинный) вес.

Более формально: пусть даны неориентированный граф <math>G = (V, E) \;</math> с неотрицательной весовой функцией на ребрах <math>c: E \to \mathbb{R}_+ \;</math> и неотрицательной весовой функцией на вершинах <math>\pi : V \to \mathbb{R}_+ \;</math>, а также константа <math>b \le 1/2 \;</math>. Сечение <math>(S : V \; \backslash \; S)</math> называется b-сбалансированным, или (b, 1 - b)-сепаратором, если <math>b \; \pi (V) \le \pi (S) \le (1 - b) \pi(V) \;</math> (где <math>\pi(S) \;</math> обозначает <math>\sum_{v \in S} \pi (v) \;</math>).

'''Задача 2 (самое разреженное сечение (для материальных потоков))'''

Задача 2 представляет собой наиболее общий случай задачи нахождения самого разреженного сечения, решенной Лейтоном и Рао. Если установить веса всех вершин равными 1, получим однородную версию этой задачи:

'''Задача 3 (самое разреженное сечение (однородное))'''

Требуется: найти сечение <math>(S : V \; \backslash \; S)</math>, минимизирующее соотношение <math>(c( \delta (S))) / (|S| | V \; \backslash \; S |)</math>.

Самое разреженное сечение возникает в интегральной версии задачи линейного программирования, двойственной задаче параллельного управления несколькими товарными потоками (задача 4). Экземпляр задачи управления несколькими товарными потоками определяется на графе с взвешенными ребрами: для каждого из k ''товаров'' обозначаются источник <math>s_i \in V \;</math>, сток <math>t_i \in V \;</math> и спрос <math>D_i \;</math>. Допустимое решение этой задачи определяет для каждого товара функцию потока на E, таким образом направляя поток определенного объема из <math>s_i \;</math> в <math>t_i \;</math>.

Веса ребер представляют их емкость (пропускную способность), каждому ребру e сопоставлено ограничение пропускной способности: максимальная сумма всех товарных потоков через ребро e не превышает его емкости c(e).

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

'''Задача 5 (самое разреженное сечение (неоднородное))'''

Требуется: найти минимальное сечение <math>(S : V \; \backslash \; S)</math>, иначе говоря, сечение с минимальным соотношением <math>(c( \delta (S)))/(D(S, V \; \backslash \; S)) \;</math>.

(Большая часть посвященных этой теме работ затрагивает либо однородную, либо общую неоднородную версии, нередко называя их просто «задачами о самом разреженном сечении»).