4551
правка
Сепараторы в графах: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
Дано: граф с взвешенными вершинами и ребрами <math>G = (V, E, c, \pi) \;</math>. | Дано: граф с взвешенными вершинами и ребрами <math>G = (V, E, c, \pi) \;</math>. | ||
Требуется: найти сечение <math>(S : V \; \backslash \; S)</math>, минимизирующее соотношение | Требуется: найти сечение <math>(S : V \; \backslash \; S)</math>, минимизирующее соотношение <math>(c( \delta (S))) / (\pi (S) \pi (V \; \backslash \; S))</math>. | ||
| Строка 30: | Строка 30: | ||
Задача 3 (самое неплотное сечение (однородное)) | '''Задача 3 (самое неплотное сечение (однородное))''' | ||
Дано: граф с взвешенными ребрами G = (V, E, c). | Дано: граф с взвешенными ребрами G = (V, E, c). | ||
Требуется: найти сечение <math>(S : V \; \backslash \; S)</math>, минимизирующее соотношение (c( | Требуется: найти сечение <math>(S : V \; \backslash \; S)</math>, минимизирующее соотношение <math>(c( \delta (S))) / (|s| | V \; \backslash \; S |)</math>. | ||
Самое неплотное сечение возникает в интегральной версии задачи линейного программирования, двойственной задаче управления несколькими товарными потоками (задача 4). Экземпляр задачи управления несколькими товарными потоками определяется на графе с взвешенными ребрами: для каждого из k товаров обозначаются источник | Самое неплотное сечение возникает в интегральной версии задачи линейного программирования, двойственной задаче параллельного управления несколькими товарными потоками (задача 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>. | ||
| Строка 43: | Строка 43: | ||
Задача 4 (параллельное управление несколькими товарными потоками) | '''Задача 4 (параллельное управление несколькими товарными потоками)''' | ||
Дано: граф с взвешенными ребрами G = (V, E, c), товары ( | Дано: граф с взвешенными ребрами <math>G = (V, E, c) \;</math>, товары <math>(s_1, t_1, D_1), ..., (s_k, t_k, D_k) \;</math>. | ||
Требуется: обеспечить управление несколькими товарными потоками, направляющее fDi единиц товара i из si в ti для каждого i одновременно, не нарушая заданной емкости каждого ребра. Цель: максимизация f. | Требуется: обеспечить управление несколькими товарными потоками, направляющее fDi единиц товара i из si в ti для каждого i одновременно, не нарушая заданной емкости каждого ребра. Цель: максимизация f. | ||