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

Определение:

Объединение матроидов [math]M[/math] = [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].

Объединим все [math]D_{M_i}(I_i)[/math] в один граф [math]D[/math], котороый будет суперпозицией ребер из этих графов.

Определение:

[math]F_i[/math] = { [math]x \in S_i \setminus I_i[/math] : [math]I_i + x \in J_i [/math]}.

Теорема:

Для любого [math]s \in S \setminus I[/math] имеем [math]I + x \in J_i \Leftrightarrow [/math] существует ориентированный путь из [math]F[/math] в [math]s[/math] по ребрам [math]D[/math].

Алгоритм

Нам известно, что объединение матроидов - матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым. Здесь мы обозначили текущее множество как [math]I[/math]. Тогда нужно найти такой элемент [math]s \in S \setminus I[/math], что [math]I + s[/math] - снова независимо. Все наши кандидаты находятся в [math]S \setminus I[/math]. Если мы найдем путь из [math]F[/math] в [math]S \setminus I[/math], то элемент [math]s[/math], которым путь закончился, можно будет добавить в [math]I[/math]. То есть шаг жадного алгоритма заключается в создании нового [math]D[/math] и поиске такого пути.

Источник

Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13