Материал из Викиконспекты
| Определение: |
| Для двух матроидов [math]M_1 = (S, \mathcal{I}_1) [/math] и [math]M_2 = (S, \mathcal{I}_2) [/math] многогранником пересечения (англ. intersection polytope) называется выпуклая оболочка (англ. convex hull) инцидентных векторов общего независимого множества:
[math]Conv\{\mathcal{X}(I), I \in \mathcal{I}_1 \cap \mathcal{I}_2 \} (1)[/math] |
| Теорема: |
Пусть [math]r_1[/math] и [math]r_2 : 2^S \mapsto Z_{+}[/math] ранговые функции матроидов [math]M_1 = (S, \mathcal{I}_1) [/math] и [math]M_2 = (S, \mathcal{I}_2) [/math] соответсвенно. Тогда многогранник пересечений [math](1)[/math] эквивалентен множеству [math]\mathit{x} \in R^{S}[/math] , определенным следующей системой общего двойного интегралоа (англ. totally dual integral (TDI)) [math](2)[/math] :
[math]x(u) := \sum\limits_{e \in U} x_e \leqslant r_i(U) \mid \forall U \subseteq S , i = 1, 2[/math]
[math] x \ge 0[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Достаточно показать, что эта система (2) является TDI , так как тогда все точки экстремума будут целыми, и тогда множество вершин будет являться набором инцидентных векторов общего независимого множества для двух матроидов .
Для доказательства TDI, рассмотрим следующее двойное линейное программирование для взвешенного вектора [math] \mathit{w} \in Z^{S} (3)[/math]:
[math]\max_{x \ge 0: x(u) \leqslant r_i(U), i = 1, 2 } [/math] [math]\mathbf\mathit{w^Tx} = [/math] минимизировать [math] \sum\limits_{U \subseteq S} r_1(U)u_1(U) + \sum\limits_{U \subseteq S} r_2(U)y_2(U)[/math]
С учетом того, что [math]\sum\limits_{e \in U} [y_1(U) + y_2(U)] \ge w_e \mid \forall e \in S[/math]
и так же [math]y_1, y_2 \ge 0[/math]
Заметим, что мы можем предположить [math]w \ge 0[/math] , так как любое отрицательное значение может быть удалено, поскольку оно никак не влияет на целостность двойственности. |
| [math]\triangleleft[/math] |
| Утверждение: |
Существуют оптимальные решения [math](y_1^*, y_2^*)[/math] для системы [math](3)[/math] , которое удовлетворяет свойствам [math](4) [/math]:
[math] y_1^*(U) = 0[/math] [math]\forall U \notin \mathcal{C}_1 [/math]
[math] y_2^*(U) = 0 [/math] [math]\forall U \notin \mathcal{C}_2 [/math]
для каких-то цепочек [math]\mathcal{C}_1 , \mathcal{C}_2 \subseteq 2^S [/math] |
| [math]\triangleright[/math] |
|
Пусть [math](y_1^*, y_2^*) [/math] будет оптимальным решением для [math](3)[/math]. Зафиксируем [math] y_2 = y_2^* [/math], и получаем:
минимизируем [math] \sum\limits_{U \subseteq S} (r_1(U)y_1(U) + r_2(U)y_2(U)) [/math]
при условии [math]\sum\limits_{e \in U} y_1(U) \ge w_e - \sum\limits_{e \in U} y_2^*(U)[/math] [math] \forall e \in S[/math]
с учетом того, что [math] y_1 \ge 0 [/math]
Это сводится к двойному линейному программированию задачи о максимальном независимом множестве с весом [math]w[/math]. Таким образом, оптимальное решение [math]y_1^*[/math] может быть выбрано для цепочки. Аналогично, делая замену [math]y_1 = y_1^*[/math] , оптимальное решение [math]y_2^*[/math] также может быть выбрано для цепочки. Более того, эти решения удовлетворяют
[math] \sum\limits_{U \in \mathcal{C}_1 : e \in U} y_1^*(U) = w_e^{(1)}[/math]
[math] \sum\limits_{U \in \mathcal{C}_2: e \in U} y_2^*(U) = w_e^{(2)}[/math]
и поэтому
[math] \sum\limits_{i = 1}^{2} \sum\limits_{U \subseteq S} y_1^*(U) = w_e [/math] для всех [math]e \in S[/math] |
| [math]\triangleleft[/math] |
