| Задача: |
| Даны матроиды [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]J \in (\mathcal{I}_1 \cap \mathcal{I}_2)[/math].
Определим граф замен [math]D_{M_1, M_2}(J) = \langle S, A(J) \rangle[/math], где
[math]A(J) = \{(y, z) | y \in J, z \in S\setminus J, J - y + z \in \mathcal{I}_1 \} [/math]
[math]\cup \{ (z', y') | z' \in S \setminus J, y' \in J, J - y' + z' \in \mathcal{I}_2 \}[/math].
Пусть [math]X_1 = \{ z \in S \setminus J | J + z \in \mathcal{I}_1 \}[/math], [math]X_2 = \{ z \in S \setminus J | J + z \in \mathcal{I}_2 \}[/math], [math]P[/math] — кратчайший путь из [math]X_1[/math] в [math]X_2[/math] в графе [math]D_{M_1, M_2}(J)[/math]. [math]P[/math] может и не существовать.
| Лемма: |
Если в графе [math]D_{M_1, M_2}(J)[/math] нет пути из [math]X_1[/math] в [math]X_2[/math], то [math]J[/math] — искомое максимальное по мощности независимое множество в пересечении [math]M_1[/math] и [math]M_2[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Отметим, что если [math]X_1[/math] или [math]X_2[/math] пустые, то [math]J[/math] — база в одном из исходных матроидов [math]M_1[/math] или [math]M_2[/math] и, следовательно, искомое максимальное по мощности независимое множество в пересечении [math]M_1[/math] и [math]M_2[/math]. Таким образом, предположим, что [math]X_1[/math] и [math]X_2[/math] непусты. Пусть [math]U[/math] — множество вершин, из которых достижимы вершины из [math]X_2[/math]. Отсутствие пути из [math]X_1[/math] в [math]X_2[/math] означает, что [math]X_1 \cap U = \emptyset[/math], [math]X_2 \subseteq U[/math] и [math]\delta^- (U) = \emptyset[/math] (т.е. в [math]U[/math] не входит ни одной дуги). Тогда:
| Утверждение: |
[math]r_1 (U) \leqslant |J \cap U|[/math] |
| [math]\triangleright[/math] | |
От противного. Пусть [math]r_1 (U) \gt |J \cap U|[/math], тогда [math]\exists z \in U \setminus (J \cap U) : (J \cap U) + z \in \mathcal{I}_1[/math] при том, что [math]J + z \notin \mathcal{I}_1[/math]. В противном случае [math]J + z \in \mathcal{I}_1, z \in X_1[/math], то есть [math]X_1 \cap U \ne \emptyset[/math], что противоречит отсутствию пути из [math]X_1[/math] в [math]X_2[/math]. Так как [math](J \cap U) + z \in \mathcal{I}_1[/math], а [math]J + z \notin \mathcal{I}_1[/math],
[math]\exists y \in J \setminus U : J - y + z \in \mathcal{I}_1[/math]. Однако, тогда [math](y, z) \in A(J)[/math], что противоречит факту [math]\delta^- (U) = \emptyset[/math]. | | [math]\triangleleft[/math] |
| Утверждение: |
[math]r_2 (S \setminus U) \leqslant |J \cap (S \setminus U)|[/math] |
| [math]\triangleright[/math] | |
От противного. Пусть [math]\exists z \in (S \setminus U) \setminus J : J \cap (S \setminus U) + z \in \mathcal{I}_2[/math]. Аналогично доказательству предыдущего утверждения [math]\exists y \in J \setminus (S \setminus U) : J - y + z \in \mathcal{I}_2[/math]. Однако [math]J \setminus (S \setminus U) = J \cap U[/math], то есть [math](z, y)[/math] — дуга в [math]D_{M_1, M_2}(J)[/math], поэтому [math]z \in U[/math] (т.к. [math]y \in U[/math]). Противоречие. | | [math]\triangleleft[/math] |
Так как [math]|J| = |J \cap U| + |J \setminus U| \geqslant r_1 (U) + r_2 (S \setminus U), |J| = r_1 (U) + r_2 (S \setminus U)[/math]. Следовательно, [math]J[/math] — максимальное по мощности независимое множество в пересечении [math]M_1[/math] и [math]M_2[/math]. |
| [math]\triangleleft[/math] |
| Лемма: |
[math]J' = J \bigtriangleup V(P) \in \mathcal{I}_1 \cap \mathcal{I}_2[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]P = z_0, y_1, z_1, ..., y_t, z_t; G = \{ z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \})[/math]. Тогда [math]G \subseteq S, |G| = |J|[/math] и дуги из [math]\{ y_1, ..., y_t \}[/math] в
[math]\{ z_1, ..., z_t \}[/math] составляют единственное полное паросочетание в [math]J \bigtriangleup G[/math]. То есть, согласно лемме о единственном паросочетании в подграфе замен, [math]G \in \mathcal{I}_1[/math].
К тому же, [math]\forall i \geqslant 1\ z_i \notin X_1[/math], иначе [math]P[/math] — не кратчайший путь из [math]X_1[/math] в [math]X_2[/math]. Это означает, что [math]z_i + J \notin \mathcal{I}_1[/math], то есть
[math]r_1 (J \cup G) = r_1 (J) = r_1 (G) = |G| = |J|[/math]. Так как [math]J + z_0 \in \mathcal{I}_1, G + z_0 \in \mathcal{I}_1[/math] (т.е. [math]J' = \{ z_0, z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \}) \in \mathcal{I}_1[/math].
Симметрично [math]G = \{ z_0, ..., z_{t - 1} \} \cup (J \setminus \{ y_1, ..., y_t \}), J' \in \mathcal{I}_2[/math] и, следовательно, [math]J' \in (\mathcal{I}_1 \cap \mathcal{I}_2)[/math]. |
| [math]\triangleleft[/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 | J + z \in \mathcal{I}_1 \}[/math]
[math]X_2 \leftarrow \{ z \in S \setminus J | 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]M_1=\langle X, \mathcal{I}_1\rangle[/math], [math]M_2=\langle X, \mathcal{I}_2\rangle[/math] — матроиды. Тогда
[math]\max\limits_{I \in \mathcal{I}_1 \cap \mathcal{I}_2 } |I| = \min\limits_{A \subseteq X} \left(r_1(A) + r_2(X \setminus A)\right)[/math].
Где [math]r_1[/math] и [math]r_2[/math] — ранговые функции в первом и втором матроиде соответственно. |
| Доказательство: |
| [math]\triangleright[/math] |
 Граф замен, кратчайший путь
Докажем неравенство [math]\max\limits_{I \in \mathcal{I}_1 \cap \mathcal{I}_2 } |I| \leqslant \min\limits_{A \subseteq X} \left(r_1(A) + r_2(X \setminus A)\right)[/math]
Выберем произвольные [math]I \in \mathcal{I}_1 \cap \mathcal{I}_2[/math], [math]A \subseteq X[/math], тогда
[math]|I| = |I \cap A| + |I \cap (X \setminus A)|[/math]
[math]I \cap A[/math] и [math]I \cap (X \setminus A)[/math] — независимые в обоих матроидах (как подмножества независимового [math]I[/math]), значит
[math]|I| = r_1(I \cap A) + r_2(I \cap (X \setminus A))[/math]
Но [math]r_1(I \cap A) \leqslant r_1(A)[/math] и [math]r_2(I \cap (X \setminus A)) \leqslant r_2(X \setminus A)[/math], значит
[math]|I| \leqslant r_1(A) + r_2(X \setminus A)[/math]
В силу произвольности [math]I[/math] и [math]A[/math] получаем
[math]\max\limits_{I \in \mathcal{I}_1 \cap \mathcal{I}_2 } |I| \leqslant \min\limits_{A \subseteq X} \left(r_1(A) + r_2(X \setminus A)\right)[/math]
Конструктивно построим [math]\forall M_1, M_2[/math] такие [math]I \in \mathcal{I}_1 \cap \mathcal{I}_2[/math] и [math]A \subseteq X[/math], что [math]|I| = r_1(A) + r_2(X \setminus A)[/math].
Обозначим [math]S = \left\{x|I \cup \{x\} \in \mathcal{I}_1\right\}[/math], [math]T = \left\{x|I \cup \{x\} \in \mathcal{I}_2\right\}[/math]. Если [math]S \cap T \ne \varnothing[/math], добавим их пересечение в [math]I[/math].
Построим граф замен [math]G_I[/math]. Добавим вершину [math]z[/math], не влияющую на независимость в первом матроиде — из неё будут вести рёбра во все вершины множества [math]S[/math]. Пусть [math]p[/math] — кратчайший путь из [math]S[/math] в [math]T[/math], [math]p_1[/math] — путь [math]p[/math] с добавленным в начало ребром из [math]z[/math]. По лемме о единственном паросочетании и лемме о единственном паросочетании, индуцированном кратчайшем путём [math]I \bigtriangleup p_1 \in \mathcal{I}_2[/math]. Теперь добавим вершину [math]u[/math], не влияющую на независимость во втором матроиде — в неё будут вести рёбра из всех вершин множества [math]T[/math]. Тогда [math]p_2[/math] (путь [math]p[/math] с добавленным ребром в [math]u[/math]) — кратчайший путь из [math]S[/math] в [math]u[/math]. Аналогично, [math]I \bigtriangleup p_2 \in \mathcal{I}_1[/math]. Отсюда следует, что [math]I \bigtriangleup p \in \mathcal{I}_1 \cap \mathcal{I}_2[/math], причём [math]|I \bigtriangleup p| = |I| + 1[/math].
Будем таким образом увеличивать [math]I[/math], пока существует путь [math]p[/math]. Рассмотрим момент, когда такого пути не нашлось.
Введём обозначение: [math]A = \{u|u \rightsquigarrow T\}[/math].
Докажем, что [math]r_1(A) = |I \cap A|[/math] от противного.
Пусть [math]r_1(A) \gt |I \cap A|[/math], тогда существует [math]w \in A \setminus (I \cap A)[/math], такое, что [math](I \cap A) \cup \{w\} \in \mathcal{I}_1[/math]. Если [math]I \cup \{w\} \in \mathcal{I}_1[/math], то [math]w \in S[/math] и из [math]S[/math] есть путь в [math]A[/math]. Значит, [math]I \cup \{w\} \notin \mathcal{I}_1[/math]. Отсюда следует, что существует [math]y \in I \setminus A[/math], такое что [math]I \setminus \{y\} \cup \{w\} \in \mathcal{I}_1[/math]. Но тогда ребро [math]yw[/math] имеется в графе, то есть из [math]y[/math] существует путь в [math]T[/math], что противоречит условию [math]y \in I \setminus A[/math].
Следовательно, [math]r_1(A) = |I \cap A|[/math]. Аналогично, [math]r_2(\overline A) = |I \cap \overline A|[/math]. Отсюда [math]r_1(A) + r_2(\overline A) = |I|[/math], то есть при найденных [math]I[/math] и [math]A[/math] достигается равенство.
Построен пример равенства, значит, теорема доказана. |
| [math]\triangleleft[/math] |
См. также
Источники информации
