4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 41: | Строка 41: | ||
где in[v] – полустепень захода, а out[v] – полустепень исхода вершины v. Поскольку второй терм является константой, задачу можно переформулировать в виде следующей целочисленной линейной программы: | где in[v] – полустепень захода, а out[v] – полустепень исхода вершины v. Поскольку второй терм является константой, задачу можно переформулировать в виде следующей целочисленной линейной программы: | ||
Минимизировать ( | Минимизировать <math>\sum_{v \in V} (in[v] - out[v]) * r[v]</math> так, чтобы выполнялись неравенства | ||
<math>w[u, v] + r[v] - r[u] \ge 0 \; \forall (u, v) \in E</math> | |||
<math>W[u, v] + r[v] - r[u] \ge 1 \; \forall u, v \in V: D[u, v] > \phi</math> | |||
<math>r[v] \in \mathbb{Z} \; \forall v \in V</math> | |||
правка