4488
правок
Ресинхронизация схемы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
<math>\sum_{v \in V} (in[v] - out[v]) \ast r[v] + \sum_{(u, v) \in E} w[u, v] \;</math>, | <math>\sum_{v \in V} (in[v] - out[v]) \ast r[v] + \sum_{(u, v) \in E} w[u, v] \;</math>, | ||
где in[v] – полустепень захода, а out[v] – полустепень исхода вершины v. Поскольку второй терм является константой, задачу можно переформулировать в виде следующей целочисленной линейной программы: | где in[v] – [[Полустепень захода вершины|полустепень захода]], а out[v] – [[полустепень исхода вершины]] v. Поскольку второй терм является константой, задачу можно переформулировать в виде следующей целочисленной линейной программы: | ||
Минимизировать <math>\sum_{v \in V} (in[v] - out[v]) * r[v]</math> так, чтобы выполнялись неравенства | Минимизировать <math>\sum_{v \in V} (in[v] - out[v]) * r[v]</math> так, чтобы выполнялись неравенства | ||
| Строка 52: | Строка 52: | ||
'''Теорема 1. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к задаче нахождения потока с минимальной стоимостью в сети | '''Теорема 1. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к следующей задаче нахождения потока с минимальной стоимостью в сети:''' | ||
'''Минимизировать <math>\sum_{(u, v) \in E} w[u, v] * f[u, v] + \sum_{D[u, v] > \phi} (W[u, v] - 1) * f[u, v]</math> так, чтобы выполнялись соотношения''' | '''Минимизировать <math>\sum_{(u, v) \in E} w[u, v] * f[u, v] + \sum_{D[u, v] > \phi} (W[u, v] - 1) * f[u, v]</math> так, чтобы выполнялись соотношения''' | ||