4446
правок
Сепараторы в графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
Тесно связана с этой задачей следующая: | Тесно связана с этой задачей следующая: | ||
'''Задача 2 (самое | '''Задача 2 (самое разреженное сечение (для материальных потоков))''' | ||
Дано: граф с взвешенными вершинами и ребрами <math>G = (V, E, c, \pi) \;</math>. | Дано: граф с взвешенными вершинами и ребрами <math>G = (V, E, c, \pi) \;</math>. | ||
| Строка 29: | Строка 29: | ||
Задача 2 представляет собой наиболее общий случай задачи нахождения самого | Задача 2 представляет собой наиболее общий случай задачи нахождения самого разреженного сечения, решенной Лейтоном и Рао. Если установить веса всех вершин равными 1, получим однородную версию этой задачи: | ||
'''Задача 3 (самое | '''Задача 3 (самое разреженное сечение (однородное))''' | ||
Дано: граф с взвешенными ребрами G = (V, E, c). | Дано: граф с взвешенными ребрами G = (V, E, c). | ||
| Строка 39: | Строка 39: | ||
Самое | Самое разреженное сечение возникает в интегральной версии задачи линейного программирования, двойственной задаче параллельного управления несколькими товарными потоками (задача 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>. | ||
| Строка 54: | Строка 54: | ||
Задача 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>. Эта двойственная интерпретация приводит нас к самой общей версии задачи – нахождению неоднородного самого | Задача 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 (самое | '''Задача 5 (самое разреженное сечение (неоднородное))''' | ||
Дано: граф с взвешенными ребрами <math>G = (V, E, c) \;</math>, товары <math>(s_1, t_1, D_1), ..., (s_k, t_k, D_k) \;</math>. | Дано: граф с взвешенными ребрами <math>G = (V, E, c) \;</math>, товары <math>(s_1, t_1, D_1), ..., (s_k, t_k, D_k) \;</math>. | ||
| Строка 64: | Строка 64: | ||
(Большая часть посвященных этой теме работ затрагивает либо однородную, либо общую неоднородную версии, нередко называя их просто «задачами о самом | (Большая часть посвященных этой теме работ затрагивает либо однородную, либо общую неоднородную версии, нередко называя их просто «задачами о самом разреженном сечении»). | ||
== Основные результаты == | == Основные результаты == | ||