Задача присваивания: различия между версиями

Задача присваивания (посмотреть исходный код)

137 байт добавлено , 20 ноября 2016

4551

правка

@@ Строка 6: / Строка 6: @@
 == Основные результаты ==
-Определим допустимую разметку вершин £ как отображение множества вершин G на множество вещественных чисел, где
+Определим ''допустимую разметку вершин'' <math>\ell \;</math> как отображение множества вершин G на множество вещественных чисел, где <math>\ell(x) + \ell(y) \ge w(x, y) \;</math>.
-£(x) + £(y) > w(x;y):
+Назовем <math>\ell(x) \;</math> меткой вершины x. Допустимую разметку вершин легко вычислить следующим образом:
+<math>\forall y \in Y \; \; \; \ell(y) = 0</math>
+и
+<math>\forall x \in X \; \; \; \ell(x) max_{y \in Y} \; w(x, y).</math>
-Назовем l(x) меткой вершины x. Допустимую разметку вершин легко вычислить следующим образом:
-y 2 Y    l(y) = 0
-and
-x 2 X    £(x) = maxw(x; y):
-y2Y
 Определим подграф равенства, G^, как остовный подграф G, содержащий все вершины G и только те ребра (x, y), веса которых удовлетворяют условию w(x, y) =