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

Задача:

Даны матроиды [math]M_1 = \langle S, \mathcal{I}_1 \rangle[/math] и [math]M_2 = \langle S, \mathcal{I}_2 \rangle[/math]. Необходимо найти максимальное по мощности независимое множество в объединении [math]M_1[/math] и [math]M_2[/math].

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

Объединение матроидов [math]M[/math] = [math]\langle S,J \rangle[/math] = [math]\bigcup\limits_{k=1}^{n}[/math] [math]M_i[/math], где [math]M_i[/math] = [math]\langle S,J_i \rangle[/math]

Алгоритм

Определим граф замен: для каждого [math]M_i[/math] построим двудольный ориентированный граф [math]D_{M_i}(I_i)[/math], где [math]I_i \in J_i[/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 J_i[/math].

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

[math]F_i = \{ x \in S \setminus I_i : I_i + x \in J_i \}[/math]. [math]F[/math] = [math]\bigcup\limits_{k=1}^{n}[/math] [math]F_i[/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] и поиске такого пути.

Псевдокод

 [math]J[/math] = [math]\emptyset[/math]
 isMaximal = false
 while not isMaximal
     построить граф замен [math]D_{M_1, M_2}(J)[/math]
     [math]X_1 \leftarrow \{ z \in S \setminus J \mid J + z \in \mathcal{I}_1 \}[/math]
     [math]X_2 \leftarrow \{ z \in S \setminus J \mid J + z \in \mathcal{I}_2 \}[/math]
     [math]P[/math] [math]\leftarrow[/math] кратчайший путь из [math]X_1[/math] в [math]X_2[/math]
     if [math]P \ne \emptyset[/math]
         [math]J[/math] = [math]J \bigtriangleup V(P)[/math]
     else
         isMaximal = true

Теорема:

Для любого [math]s \in S \setminus I[/math] имеем [math]I + s \in J \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, ... s_p[/math]}. [math]s_0 \in F[/math], так что не умаляя общности можно сказать, что [math]s_0 \in F_1[/math]. Для каждого [math]j = 1...k[/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 J_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 J_j[/math]. Аналогично [math]s_0 \in F_1[/math], значит [math]I'_1 \in J_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, \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) \le 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 J_i[/math]. Но [math]x \notin F[/math] (по предположению вначале доказательства), значит [math]I_i + x \notin J_i[/math]. Из этого следует, что [math]I_i + x[/math] содержит единственный цикл. Значит существует [math]y \in I_i - T[/math], такой что [math]I_i + x - y \in J_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) \le (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))[/math] [math]r_M(I + s) \le |(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 J[/math] — противоречие.

[math]\triangleleft[/math]

См. также

• Пересечение матроидов, определение, примеры
• Алгоритм построения базы в пересечении матроидов

Источники информации

Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13