4551
правка
Сепараторы в графах: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
Более формально: пусть даны неориентированный граф 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>). | Более формально: пусть даны неориентированный граф G = (V, E) \; с неотрицательной весовой функцией на ребрах <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>). | ||
Задача 1 (b-сбалансированный сепаратор) | '''Задача 1 (b-сбалансированный сепаратор)''' | ||
Дано: граф с взвешенными вершинами и ребрами G = (V, E, c, | Дано: граф с взвешенными вершинами и ребрами <math>G = (V, E, c, \pi) \;</math>, константа <math>b \le 1/2 \;</math>. | ||
Требуется: найти b-сбалансированный сепаратор (S: V | Требуется: найти b-сбалансированный сепаратор (<math>(S : V \; \backslash \; S)</math>. Цель: минимизировать вес ребер <math>c( \delta(S)) \;</math>. | ||
Тесно связана с этой задачей следующая: | Тесно связана с этой задачей следующая: | ||
Задача 2 (самое неплотное сечение (для материальных потоков)) | '''Задача 2 (самое неплотное сечение (для материальных потоков))''' | ||
Дано: граф с взвешенными вершинами и ребрами G = (V, E, c, | Дано: граф с взвешенными вершинами и ребрами <math>G = (V, E, c, \pi) \;</math>. | ||
Требуется: найти сечение (S: | |||
Требуется: найти сечение <math>(S : V \; \backslash \; S)</math>, минимизирующее соотношение i | |||
| Строка 33: | Строка 34: | ||
Дано: граф с взвешенными ребрами G = (V, E, c). | Дано: граф с взвешенными ребрами G = (V, E, c). | ||
Требуется: найти сечение (S: | Требуется: найти сечение <math>(S : V \; \backslash \; S)</math>, минимизирующее соотношение (c(S(S)))/(\S\\V\S\). | ||
| Строка 56: | Строка 57: | ||
Дано: граф с взвешенными ребрами G = (V, E, c), товары (s1;t1;D1); :::(sk;tk;Dk). | Дано: граф с взвешенными ребрами G = (V, E, c), товары (s1;t1;D1); :::(sk;tk;Dk). | ||
Требуется: найти минимальное сечение (S: V | Требуется: найти минимальное сечение <math>(S : V \; \backslash \; S)</math>, а именно – минимум отношения (c(S(S)))/(D(S, V n S)). | ||