Изменения
Новая страница: «==Постановка задачи== Даны матроиды <tex>M_1 = (S, I_1)</tex> и <tex>M_2 = (S, I_2)</tex>. Необходимо найти максим…»
==Постановка задачи==
Даны матроиды <tex>M_1 = (S, I_1)</tex> и <tex>M_2 = (S, I_2)</tex>. Необходимо найти максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>
==Алгоритм решения==
До тех пор, пока множество <tex>J</tex> не максимально (не удовлетворяет критерию из [[Теорема Эдмондса-Лоулера|теоремы Эдмондса-Лоулера]]), будем итерировать следующий алгоритм:
<br>Определим [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J) = (S, A(J))</tex>, где
<tex>A(J) = \{(y, z) | y \in S, z \in S\setminus J, J - y + z \in I_1 \} </tex>
<tex>\cup \{ (z', y') | z' \in S \setminus J, y' \in J, J - y' + z' \in I_2 \}</tex>
Пусть <tex>X_1 = \{ z \in S \setminus J | J + z \in I_1 \}</tex>, <tex>X_2 = \{ z \in S \setminus J | J + z \in I_2 \}</tex>, <tex>P</tex> - кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex> в графе <tex>D_{M_1, M_2}(J)</tex>. <tex>P</tex> может и не существовать
{{Лемма
|statement =
Если в графе <tex>D_{M_1, M_2}(J)</tex> нет пути из <tex>X_1</tex> в <tex>X_2</tex>, то <tex>J</tex> - искомое максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>
|proof =
Отметим, что если <tex>X_1</tex> или <tex>X_2</tex> пустые, то <tex>J</tex> - база в одном из исходных матроидов <tex>M_1</tex> или <tex>M_2</tex> и, следовательно, искомое максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>. Таким образом, предположим, что <tex>X_1</tex> и <tex>X_2</tex> непусты. Пусть <tex>U</tex> - множество вершин, из которых достижимы вершины из <tex>X_2</tex>. Отсутствие пути из <tex>X_1</tex> в <tex>X_2</tex> означает, что <tex>X_1 \cap U = \emptyset</tex>, <tex>X_2 \subseteq U</tex> и <tex>\delta^- (U) = \emptyset</tex>(т.е. в <tex>U</tex> не входит ни одной дуги). Тогда:
{{Утверждение
|statement =
<tex>r_1 (U) \le |J \cap U|</tex>
|proof =
От противного. Пусть <tex>r_1 (U) > |J \cap U|</tex>, тогда <tex>\exists z \in U \setminus (J \cap U)</tex> : <tex>(J \cap U) + z \in I_1</tex> при том, что <tex>J + z \notin I_1</tex>. В противном случае (<tex>J + z \in I_1</tex>),
<tex>z \in X_1</tex>, то есть <tex>X_1 \cap U \ne \emptyset</tex>, что противоречит отсутствию пути из <tex>X_1</tex> в <tex>X_2</tex>. Так как <tex>(J \cap U) + z \in I_1</tex>, а <tex>J + z \notin I_1</tex>,
<tex>\exists y \in J \setminus U</tex> : <tex>J - y + z \in I_1</tex>. Однако, тогда <tex>(y, z) \in A(J)</tex>, что противоречит тому факту, что <tex>\delta^- (U) = \emptyset</tex>.
}}
{{Утверждение
|statement =
<tex>r_2 (U) \le |J \setminus U|</tex>
|proof =
Аналогично предыдущему утверждению
}}
Так как <tex>|J| = |J \cap U| + |I \setminus U| \ge r_1 (U) + r_2 (S \setminus U)</tex>, что означает, что <tex>|J| = r_1 (U) + r_2 (S \setminus U)</tex>. Таким образом, <tex>J</tex> - максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>.
}}
{{Лемма
|statement =
<tex>J' = J \bigtriangleup V(P) \in I_1 \cap I_2</tex>
|proof =
[[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем | ]]
Пусть <tex>P = z_0, y_1, z_1, ..., y_t, z_t</tex>, <tex>G = \{ z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \})</tex>. Тогда <tex>G \subseteq S</tex>, <tex>|G| = |J|</tex> и дуги из <tex>\{ y_1, ..., y_t \}</tex> в
<tex>\{ z_1, ..., z_t \}</tex> составляют единственное полное паросочетание в <tex>J \bigtriangleup G</tex>. То есть, согласно [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем | лемме о единственном паросочетании в подграфе замен, индуцированным кратчайшим путем]], <tex>G \in I_1</tex>.
К тому же, <tex>\forall i \ge 1 z_i \notin X_1</tex>, иначе <tex>P</tex> - не кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. Это означает, что <tex>z_i + J \notin I_1</tex>, то есть
<tex>r_1 (J \cup G) = r_1 (J) = r_1 (G) = |G| = |J|</tex>. Так как <tex>J + z_0 \in I_1</tex>, <tex>G + z_0 \in I_1</tex> (т.е. <tex>J' = \{ z_0, z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \}) \in I_1</tex>.
Симметрично, <tex>G \in I_2</tex> и, следовательно, <tex>G \in (I_1 \cap I_2)</tex>.
}}
Таким образом, получаем следующий алгоритм:
*'''Псевдокод'''
<tex>J</tex> <- <tex>\emptyset</tex>
isMaximal <- false
while (not isMaximal) {
<построить [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J)</tex>>
<tex>X_1</tex> <- <tex>\{ z \in S \setminus J | J + z \in I_1 \}</tex>
<tex>X_2</tex> <- <tex>\{ z \in S \setminus J | J + z \in I_2 \}</tex>
<tex>P</tex> <- кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>
if <tex>(P \ne \emptyset)</tex> {
<tex>J</tex> <- <tex>J \bigtriangleup V(P)</tex>
} else {
isMaximal <- true
}
}
Даны матроиды <tex>M_1 = (S, I_1)</tex> и <tex>M_2 = (S, I_2)</tex>. Необходимо найти максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>
==Алгоритм решения==
До тех пор, пока множество <tex>J</tex> не максимально (не удовлетворяет критерию из [[Теорема Эдмондса-Лоулера|теоремы Эдмондса-Лоулера]]), будем итерировать следующий алгоритм:
<br>Определим [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J) = (S, A(J))</tex>, где
<tex>A(J) = \{(y, z) | y \in S, z \in S\setminus J, J - y + z \in I_1 \} </tex>
<tex>\cup \{ (z', y') | z' \in S \setminus J, y' \in J, J - y' + z' \in I_2 \}</tex>
Пусть <tex>X_1 = \{ z \in S \setminus J | J + z \in I_1 \}</tex>, <tex>X_2 = \{ z \in S \setminus J | J + z \in I_2 \}</tex>, <tex>P</tex> - кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex> в графе <tex>D_{M_1, M_2}(J)</tex>. <tex>P</tex> может и не существовать
{{Лемма
|statement =
Если в графе <tex>D_{M_1, M_2}(J)</tex> нет пути из <tex>X_1</tex> в <tex>X_2</tex>, то <tex>J</tex> - искомое максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>
|proof =
Отметим, что если <tex>X_1</tex> или <tex>X_2</tex> пустые, то <tex>J</tex> - база в одном из исходных матроидов <tex>M_1</tex> или <tex>M_2</tex> и, следовательно, искомое максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>. Таким образом, предположим, что <tex>X_1</tex> и <tex>X_2</tex> непусты. Пусть <tex>U</tex> - множество вершин, из которых достижимы вершины из <tex>X_2</tex>. Отсутствие пути из <tex>X_1</tex> в <tex>X_2</tex> означает, что <tex>X_1 \cap U = \emptyset</tex>, <tex>X_2 \subseteq U</tex> и <tex>\delta^- (U) = \emptyset</tex>(т.е. в <tex>U</tex> не входит ни одной дуги). Тогда:
{{Утверждение
|statement =
<tex>r_1 (U) \le |J \cap U|</tex>
|proof =
От противного. Пусть <tex>r_1 (U) > |J \cap U|</tex>, тогда <tex>\exists z \in U \setminus (J \cap U)</tex> : <tex>(J \cap U) + z \in I_1</tex> при том, что <tex>J + z \notin I_1</tex>. В противном случае (<tex>J + z \in I_1</tex>),
<tex>z \in X_1</tex>, то есть <tex>X_1 \cap U \ne \emptyset</tex>, что противоречит отсутствию пути из <tex>X_1</tex> в <tex>X_2</tex>. Так как <tex>(J \cap U) + z \in I_1</tex>, а <tex>J + z \notin I_1</tex>,
<tex>\exists y \in J \setminus U</tex> : <tex>J - y + z \in I_1</tex>. Однако, тогда <tex>(y, z) \in A(J)</tex>, что противоречит тому факту, что <tex>\delta^- (U) = \emptyset</tex>.
}}
{{Утверждение
|statement =
<tex>r_2 (U) \le |J \setminus U|</tex>
|proof =
Аналогично предыдущему утверждению
}}
Так как <tex>|J| = |J \cap U| + |I \setminus U| \ge r_1 (U) + r_2 (S \setminus U)</tex>, что означает, что <tex>|J| = r_1 (U) + r_2 (S \setminus U)</tex>. Таким образом, <tex>J</tex> - максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>.
}}
{{Лемма
|statement =
<tex>J' = J \bigtriangleup V(P) \in I_1 \cap I_2</tex>
|proof =
[[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем | ]]
Пусть <tex>P = z_0, y_1, z_1, ..., y_t, z_t</tex>, <tex>G = \{ z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \})</tex>. Тогда <tex>G \subseteq S</tex>, <tex>|G| = |J|</tex> и дуги из <tex>\{ y_1, ..., y_t \}</tex> в
<tex>\{ z_1, ..., z_t \}</tex> составляют единственное полное паросочетание в <tex>J \bigtriangleup G</tex>. То есть, согласно [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем | лемме о единственном паросочетании в подграфе замен, индуцированным кратчайшим путем]], <tex>G \in I_1</tex>.
К тому же, <tex>\forall i \ge 1 z_i \notin X_1</tex>, иначе <tex>P</tex> - не кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. Это означает, что <tex>z_i + J \notin I_1</tex>, то есть
<tex>r_1 (J \cup G) = r_1 (J) = r_1 (G) = |G| = |J|</tex>. Так как <tex>J + z_0 \in I_1</tex>, <tex>G + z_0 \in I_1</tex> (т.е. <tex>J' = \{ z_0, z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \}) \in I_1</tex>.
Симметрично, <tex>G \in I_2</tex> и, следовательно, <tex>G \in (I_1 \cap I_2)</tex>.
}}
Таким образом, получаем следующий алгоритм:
*'''Псевдокод'''
<tex>J</tex> <- <tex>\emptyset</tex>
isMaximal <- false
while (not isMaximal) {
<построить [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J)</tex>>
<tex>X_1</tex> <- <tex>\{ z \in S \setminus J | J + z \in I_1 \}</tex>
<tex>X_2</tex> <- <tex>\{ z \in S \setminus J | J + z \in I_2 \}</tex>
<tex>P</tex> <- кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>
if <tex>(P \ne \emptyset)</tex> {
<tex>J</tex> <- <tex>J \bigtriangleup V(P)</tex>
} else {
isMaximal <- true
}
}
