| Задача: |
| Даны матроиды [math]M_1 = \langle S_1, \mathcal{I}_1 \rangle \dots M_n = \langle S_n, \mathcal{I}_n \rangle[/math]. Необходимо найти максимальное по мощности независимое множество в объединении [math]\bigcup\limits_{i=1}^{n}[/math] [math]M_i[/math]. |
Алгоритм
Пусть у нас есть множество [math]I\in\mathcal{I}[/math], где [math] \mathcal{I} = \{ \bigcup\limits_{i=1}^{n} I_i \mid I_i \in \mathcal{I}_i\} [/math], и разбиение [math]I[/math] на [math]\bigcup\limits_{i=1}^{n}I_i[/math], такое, что [math]I_i\in \mathcal{I}_i[/math]. То есть, [math]I[/math] состоит из каких-то подмножеств семейства множеств [math]\mathcal{I}_i[/math] для [math]i[/math] от [math]1[/math] до [math]n[/math]. Рассмотрим элемент [math]s\not \in I[/math]. Нужно определить, правда ли, что [math]I+s\in \mathcal{I}[/math]. Если научиться это делать, то тогда можно решить задачу жадным алгоритмом, добавляя в текущее множество по одному элементу [math]s[/math] на каждом шаге.
Определим объединение матроидов как [math]M[/math] = [math]\langle S,\mathcal{I} \rangle[/math] = [math]\bigcup\limits_{i=1}^{n}[/math] [math]M_i[/math], где [math]M_i[/math] = [math]\langle S_i,\mathcal{I}_i \rangle[/math].
Для [math]i[/math] от [math]1[/math] до [math]n[/math] возьмем [math]M_i[/math] и построим двудольный ориентированный граф [math]D_{M_i}(I_i)[/math], где [math]I_i \in \mathcal{I}_i[/math]. Вершины графа — элементы из [math]S[/math], в левой доле находятся вершины из [math]I_i[/math], а в правой — элементы из [math]S \setminus I_i[/math]. Проведем ориентированные ребра из [math]y \in I_i[/math] в [math]x \in S \setminus I_i[/math], при условии, что [math](I_i \setminus y) \cup x \in \mathcal{I}_i[/math].
Объединим все [math]D_{M_i}(I_i)[/math] в один граф [math]D[/math], который будет наложением ребер из этих графов, то есть, будет содержать все рёбра всех графов [math] D_{M_i}(I_i)[/math].
Для каждого [math]i[/math] определим множество [math]F_i[/math] как множество вершин [math]S_i\setminus I_i[/math] таких, что множество [math]I_i+x[/math] также независимое. Формально: [math]F_i = \{ x \in S_i \setminus I_i \mid I_i + x \in \mathcal{I}_i \}[/math].
Определим [math]F[/math] = [math]\bigcup\limits_{k=1}^{n}[/math] [math]F_i[/math]
| Теорема: |
Для какого-нибудь [math]s \in S \setminus I[/math] выполняется: [math]I + s \in \mathcal{I} \Leftrightarrow [/math] существует ориентированный путь из [math]F[/math] в [math]s[/math] по ребрам [math]D[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]\Leftarrow[/math]
- Пусть существует путь из [math]F[/math] в [math]s[/math] и [math]P[/math] — самый короткий такой путь. Запишем его вершины как [math]\{s_0, s_1, \dots s_p\}[/math]. Вершина [math]s_0 \in F[/math], так что не умаляя общности можно сказать, что [math]s_0 \in F_1[/math]. Для каждого [math]j = 1\dots n[/math] определим множество вершин [math]S_j =[/math] [math]\{s_i, s_{i+1}:(s_i, s_{i+1}) \in D_{M_j}(I_j)\}[/math], где [math]i[/math] пробегает от [math]0[/math] до [math]p - 1[/math].
- Положим [math]I'_1 = (I_1 \oplus S_1) \cup \{s_0\}[/math], для всех [math]j \gt 1[/math] опеределим [math]I'_j = (I_j \oplus S_j)[/math]. Ясно, что [math]\cup _j I'_j = I + s[/math] (. Для того, чтобы показать независимость [math]I + s[/math] в объединении матроидов нужно показать, что [math]I'_j \in \mathcal{I}_j[/math] для всех [math]j[/math]. Заметим, что так как мы выбирали путь [math]P[/math] таким, что он будет наименьшим, для каждого [math]j \gt 1[/math] существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать [math]I'_j = I_j \oplus S_j[/math]. Так как паросочетание единственно, [math]I'_j \in \mathcal{I}_j[/math]. Аналогично [math]s_0 \in F_1[/math], значит [math]I'_1 \in \mathcal{I}_1[/math] (см. лемму). Следовательно, [math]I + s[/math] независимо в объединении матроидов.
[math]\Rightarrow[/math]
- Пусть нет пути из [math]F[/math] в [math]s[/math] по ребрам [math]D[/math]. Тогда пусть существует множество [math]T[/math], состоящее из вершин [math]D[/math], из которого мы можем достичь [math]s[/math] : [math]T = \{x\mid \exists x \leadsto s\}[/math], по допущению [math]F\cap T = \varnothing[/math]. Утверждается, что для всех [math]i : |I_i \cap T| = r_i(T)[/math] (из чего следует, что [math]I_i \cap T[/math] — максимальное подмножество [math]T[/math], независимое в [math]M_i[/math]).
- Предположим, что это не так. Так как [math]|I_i \cap T| = r_i(I_i\cap T) \leqslant r_i(T)[/math], остается возможным только случай [math]|I_i \cap T| \lt r_i(T)[/math] (мы предположили, что утверждение в предыдущем абзаце неверно). Значит существует такой [math]x \in T \cap (S \setminus I_i)[/math], для которого [math](I_i \cap T) + x \in \mathcal{I}_i[/math]. Но [math]x \notin F[/math] (по предположению в начале доказательства), значит [math]I_i + x \notin
\mathcal{I}_i[/math]. Из этого следует, что [math]I_i + x[/math] содержит единственный цикл. Значит существует [math]y \in I_i - T[/math], такой, что [math]I_i + x - y \in \mathcal{I}_i[/math]. Получается, что [math](y, x)[/math] — ребро в [math]D_{M_i}(I_i)[/math] и оно содержит этот [math]y \in T[/math], что противоречит тому как был выбран [math]y \in I_i \setminus T[/math]. Следовательно для всех [math]i[/math] нам известно : [math]|I_i \cap T| = r_i(T)[/math].
- У нас есть [math]s \in T[/math] и [math](I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s[/math]. Из определения функции ранга объединения матроидов имеем :
- [math]r_M(I + s) \leqslant (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))[/math]
- [math]r_M(I + s) \leqslant |(I + s)\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I| \lt |I + s|[/math]
- и значит [math](I + s) \notin
\mathcal{I}[/math] — противоречие.
|
| [math]\triangleleft[/math] |
Итак, теперь мы можем описать сам алгоритм. Изначально инициализируем [math]I[/math] как семейство пустых множеств. На каждом шаге будем строить граф [math]D[/math] из текущего [math]I[/math] и [math]S\setminus I[/math] и добавлять в [math]I[/math] кандидата-вершину [math]s[/math], удовлетворяющую условию теоремы. При добавлении вершины нужно не забыть поменять местами вершины на пути [math]F \leadsto s[/math], так как ребра из [math]I_i[/math] должны вести в [math]S\setminus I_i[/math] (т.е. должен сохраняться инвариант). Когда вершины-кандидаты закончатся, по доказанной выше теореме получившееся множество [math]I[/math] станет максимальным.
Псевдокод
В реализации алгоритма каждый элемент представлен целым числом.
- [math]s[/math] — принимаемое множество носитилей матроидов
- [math]\mathtt{base}[/math] — принимаемое множество баз матроидов
- [math]\mathtt{res}[/math] — возвращаемая база в объединении матроидов. [math]res_1, res_2 \dots res_n[/math] содержат элементы, содержащиеся в полученной базе.
int[][] unionBase(int[n] [math]s[/math], int[n] [math]\mathtt{base}[/math]):
int[n][] [math]\mathtt{res}[/math] // На каждом шаге алгоритма заполняем очередным элементом
bool [math]\mathtt{reached}[/math] = false // Индикатор окончания работы цикла. Если true, то не нашли подходящую вершину
while [math]!\mathtt{reached}[/math]
[math]\mathtt{reached}[/math] = true
int [math]f[n][/math] // Соответствует [math]F[/math]
Graph [math]d[n][/math]
for [math]i[/math] = 1 to [math]n[/math]
[math]d[i][/math] = buildBipartiteGraph[math](\mathtt{res[i]} ,s[i] \setminus \mathtt{res}[i])[/math] // Строим двудольный граф d[i]
[math]f[i][/math] = [math] \{ x \in s[i] \setminus \mathtt{res[i]} : \mathtt{res}[i] + x \in base[i] \}[/math]
for [math]\mathtt{elem} \in s\setminus \mathtt{base}[/math]
List<int> [math]p[/math] = findShortestPath([math]f[/math], [math]\mathtt{elem}[/math])
if [math]p\neq \varnothing [/math]
[math]\mathtt{reached}[/math] = false // Нашли очередную вершину, цикл можно продолжить
int [math]\mathtt{pos}[/math] = getF([math]p[1][/math]) // Находим [math]f_i[/math], которому принадлежит стартовая вершина в пути
int [math]v[n][/math] // i-й элемент [math]v[/math] хранит множество вершин, соответствующее i-му входному матроиду
for [math] j[/math] = 1 to [math]p.len - 1[/math]
int [math]\mathtt{vertex}[/math] = getDbyEdge[math](p[j],p[j+1])[/math] // Находим номер графа, соответствующего ребру [math](p[j],p[j+1])[/math]
[math]v[\mathtt{vertex}].add(j)[/math] // Добавляем в соответствующее вершинам множество концы ребра
[math]v[\mathtt{vertex}].add(j + 1)[/math]
for [math]j[/math] = 1 to [math]n[/math]
[math] \mathtt{res}[j][/math] = [math] \mathtt{res}[j] \oplus v[j][/math] // Удаляем и добавляем ребра на пути к конечной вершине
[math]\mathtt{res}[\mathtt{pos}][/math] = [math]res[\mathtt{pos}] \cup p[1] [/math]
break
return [math]\mathtt{res}[/math]
См. также
Асимптотика
На каждом шаге алгоритма происходит построение графа D. Для того, чтобы его построить, нам нужно для [math]i=1\dots n[/math] для каждого [math]v[/math] из [math]S[/math] и [math]u[/math] из [math]S\setminus I_i[/math], где [math]S[/math] — объединение матроидов, проверить условие [math](I_i \setminus u) \cup v \in \mathcal{I}_i[/math]. Построение графа занимает [math]O(\sum\limits_{i=1}^{n}\vert (S_i\setminus I_i)\vert \vert I_i\vert [/math]) времени на каждой итерации. Нахождение кратчайшего пути для всех вершин занимает [math]O(\vert E\vert )[/math] единиц времени, где [math]E[/math] — множество ребер графа [math]D[/math], если использовать поиск в ширину, что в худшем случае будет равно [math]O(\vert S \vert ^2)[/math]. Обновление [math]res[/math] занимает [math]O(n|I_{max}|)[/math] времени, что равно [math]O(\vert S \vert)[/math]. В худшем случае требуется [math]|S|[/math] итераций, и общая асимптотика будет [math]O(|S|^3)[/math].
Источники информации
