4551
правка
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
Строка 7: | Строка 7: | ||
Более формально: пусть даны неориентированный граф G = (V, E) с неотрицательной весовой функцией на ребрах c: E | Более формально: пусть даны неориентированный граф 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: | ||
(Большая часть посвященных этой теме работ затрагивает либо однородную, либо общую неоднородную версии, нередко называя их просто «задачами о неплотном сечении»). | (Большая часть посвященных этой теме работ затрагивает либо однородную, либо общую неоднородную версии, нередко называя их просто «задачами о неплотном сечении»). | ||
== Основные результаты == | == Основные результаты == |
правка