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

Перейти к навигации Перейти к поиску
Нет описания правки
Строка 7: Строка 7:




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




Строка 60: Строка 60:


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


== Основные результаты ==
== Основные результаты ==
4551

правка

Навигация