Алгоритм построения базы в объединении матроидов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Для каждого <tex>M_i</tex> построим двудольный ориентированный граф <tex>D_{M_i}(I_i)</tex>, такой что в левой доле находятся вершины из <tex>I_i</tex>, а в правой - вершины из <tex>S_i \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S_i \setminus I_i</tex>, при условии, что <tex>I_i y + x \in J_i</tex>.
+
Для каждого <tex>M_i</tex> построим двудольный ориентированный граф <tex>D_{M_i}(I_i)</tex>, такой что в левой доле находятся вершины из <tex>I_i</tex>, а в правой - вершины из <tex>S_i \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S_i \setminus I_i</tex>, при условии, что <tex>I_i - y + x \in J_i</tex>.
 
}}
 
}}

Версия 06:07, 27 июня 2011

Определение:
Объединение матроидов M = [math]\langle S,J \rangle[/math] = [math]\cup _{k=1}^{n}[/math] [math]M_i[/math]


Определение:
Для каждого [math]M_i[/math] построим двудольный ориентированный граф [math]D_{M_i}(I_i)[/math], такой что в левой доле находятся вершины из [math]I_i[/math], а в правой - вершины из [math]S_i \setminus I_i[/math]. Построим ориентированные ребра из [math]y \in I_i[/math] в [math]x \in S_i \setminus I_i[/math], при условии, что [math]I_i - y + x \in J_i[/math].