Алгоритм построения базы в пересечении матроидов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 5 участников)
Строка 1: Строка 1:
==Постановка задачи==
+
{{Задача
Даны матроиды <tex>M_1 = (S, I_1)</tex> и <tex>M_2 = (S, I_2)</tex>. Необходимо найти максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>
+
|definition=
 +
Даны матроиды <tex>M_1 = \langle S, \mathcal{I}_1 \rangle</tex> и <tex>M_2 = \langle S, \mathcal{I}_2 \rangle</tex>. Необходимо найти максимальное по мощности независимое множество в [[Пересечение_матроидов,_определение,_примеры|пересечении]] <tex>M_1</tex> и <tex>M_2</tex>.
 +
}}
  
 
==Алгоритм решения==
 
==Алгоритм решения==
Пусть множество <tex>J \in (I_1 \cap I_2)</tex>
+
Пусть множество <tex>J \in (\mathcal{I}_1 \cap \mathcal{I}_2)</tex>.
<br>Определим [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J) = (S, A(J))</tex>, где  
+
<br>Определим [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J) = \langle S, A(J) \rangle</tex>, где  
<tex>A(J) = \{(y, z) | y \in S, z \in S\setminus J, J - y + z \in I_1 \} </tex>  
+
<tex>A(J) = \{(y, z) \mid y \in J, z \in S\setminus J, J - y + z \in \mathcal{I}_1 \} </tex>  
<tex>\cup \{ (z', y') | z' \in S \setminus J, y' \in J, J - y' + z' \in I_2 \}</tex>
+
<tex>\cup \{ (z', y') \mid z' \in S \setminus J, y' \in J, J - y' + z' \in \mathcal{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> может и не существовать
+
 
 +
Пусть <tex>X_1 = \{ z \in S \setminus J \mid J + z \in \mathcal{I}_1 \}</tex>, <tex>X_2 = \{ z \in S \setminus J \mid J + z \in \mathcal{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 =
 
|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>
+
Если в графе <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 =
 
|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> не входит ни одной дуги). Тогда:
+
Отметим, что если <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 =
 
|statement =
<tex>r_1 (U) \le |J \cap U|</tex>
+
<tex>r_1 (U) \leqslant |J \cap U|</tex>
 
|proof =
 
|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>r_1 (U) > |J \cap U|</tex>, тогда <tex>\exists z \in U \setminus (J \cap U) : (J \cap U) + z \in \mathcal{I}_1</tex> при том, что <tex>J + z \notin \mathcal{I}_1</tex>. В противном случае <tex>J + z \in \mathcal{I}_1, 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 \mathcal{I}_1</tex>, а <tex>J + z \notin \mathcal{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 : J - y + z \in \mathcal{I}_1</tex>. Однако, тогда <tex>(y, z) \in A(J)</tex>, что противоречит факту <tex>\delta^- (U) = \emptyset</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 =
 
|statement =
<tex>r_2 (S \setminus U) \le |J \cap (S \setminus U)|</tex>
+
<tex>r_2 (S \setminus U) \leqslant |J \cap (S \setminus U)|</tex>
 
|proof =
 
|proof =
От противного. Пусть <tex>\exists z \in (S \setminus U) \setminus J</tex> : <tex>J \cap (S \setminus U) + z \in I_2</tex>. Аналогично доказательству предыдущего утверждения, <tex>\exists y \in J \setminus (S \setminus U)</tex> : <tex>J - y + z \in I_2</tex>. Однако <tex>J \setminus (S \setminus U) = J \cap U</tex>, то есть <tex>(z, y)</tex> - дуга в <tex>D_{M_1, M_2}(J)</tex>, поэтому <tex>z \in U</tex> (т.к. <tex>y \in U</tex>). Противоречие.
+
От противного. Пусть <tex>\exists z \in (S \setminus U) \setminus J : J \cap (S \setminus U) + z \in \mathcal{I}_2</tex>. Аналогично доказательству предыдущего утверждения <tex>\exists y \in J \setminus (S \setminus U) : J - y + z \in \mathcal{I}_2</tex>. Однако <tex>J \setminus (S \setminus U) = J \cap U</tex>, то есть <tex>(z, y)</tex> {{---}} дуга в <tex>D_{M_1, M_2}(J)</tex>, поэтому <tex>z \in U</tex> (т.к. <tex>y \in U</tex>). Противоречие.
 
}}
 
}}
Так как <tex>|J| = |J \cap U| + |J \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>.
+
Так как <tex>|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)</tex>. Следовательно, <tex>J</tex> {{---}} максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>.
 
}}
 
}}
 
{{Лемма
 
{{Лемма
 
|statement =
 
|statement =
<tex>J' = J \bigtriangleup V(P) \in I_1 \cap I_2</tex>
+
<tex>J' = J \bigtriangleup V(P) \in \mathcal{I}_1 \cap \mathcal{I}_2</tex>
 
|proof =
 
|proof =
[[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем | ]]
+
[[Файл:Graph_DY.png|400px|thumb|right|Граф замен]]
Пусть <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>P = z_0, y_1, z_1, ..., y_t, z_t; G = \{ z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \})</tex>. Тогда <tex>G \subseteq S, |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>\{ z_1, ..., z_t \}</tex> составляют единственное полное паросочетание в <tex>J \bigtriangleup G</tex>. То есть, согласно [[Лемма о единственном паросочетании в графе замен | лемме о единственном паросочетании в подграфе замен]], <tex>G \in \mathcal{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>\forall i \geqslant 1\ z_i \notin X_1</tex>, иначе <tex>P</tex> {{---}} не кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. Это означает, что <tex>z_i + J \notin \mathcal{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>r_1 (J \cup G) = r_1 (J) = r_1 (G) = |G| = |J|</tex>. Так как <tex>J + z_0 \in \mathcal{I}_1, G + z_0 \in \mathcal{I}_1</tex> (т.е. <tex>J' = \{ z_0, z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \}) \in \mathcal{I}_1</tex>.
Симметрично, <tex>G \in I_2</tex> и, следовательно, <tex>G \in (I_1 \cap I_2)</tex>.
+
Симметрично <tex>G = \{ z_0, ..., z_{t - 1} \} \cup (J \setminus \{ y_1, ..., y_t \}), J' \in \mathcal{I}_2</tex> и, следовательно, <tex>J' \in (\mathcal{I}_1 \cap \mathcal{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 \leftarrow \{ z \in S \setminus J \mid J + z \in \mathcal{I}_1 \}</tex>
 +
      <tex>X_2 \leftarrow \{ z \in S \setminus J \mid J + z \in \mathcal{I}_2 \}</tex>
 +
      <tex>P</tex> <tex>\leftarrow</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>X_1</tex>.
 +
 
 +
== Теорема Эдмондса-Лоулера ==
 +
 
 +
{{Теорема
 +
|about=
 +
Эдмондса-Лоулера
 +
|statement= Пусть <tex>M_1=\langle X, \mathcal{I}_1\rangle</tex>, <tex>M_2=\langle X, \mathcal{I}_2\rangle</tex> {{---}} матроиды. Тогда <br>
 +
<tex>\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)</tex>.
 +
Где <tex>r_1</tex> и <tex>r_2</tex> {{---}} ранговые функции в первом и втором матроиде соответственно.
 +
|proof=
 +
[[Файл:El_graph2.png|thumb|140px|right|Граф замен, кратчайший путь]]
 +
[[Файл:El_graph.png|thumb|140px|right|Завершение алгоритма]]
 +
<div>
 +
Докажем неравенство <tex>\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)</tex>
 +
 
 +
Выберем произвольные <tex>I \in \mathcal{I}_1 \cap \mathcal{I}_2</tex>, <tex>A \subseteq X</tex>, тогда
 +
 
 +
<tex>|I| = |I \cap A| + |I \cap (X \setminus A)|</tex>
 +
 
 +
<tex>I \cap A</tex> и <tex>I \cap (X \setminus A)</tex> {{---}} независимые в обоих матроидах (как подмножества независимового <tex>I</tex>), значит
 +
 
 +
<tex>|I| = r_1(I \cap A) + r_2(I \cap (X \setminus A))</tex>
 +
 
 +
Но <tex>r_1(I \cap A) \leqslant r_1(A)</tex> и <tex>r_2(I \cap (X \setminus A)) \leqslant r_2(X \setminus A)</tex>, значит
 +
 
 +
<tex>|I| \leqslant r_1(A) + r_2(X \setminus A)</tex>
 +
 
 +
В силу произвольности <tex>I</tex> и <tex>A</tex> получаем
 +
 
 +
<tex>\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)</tex>
 +
 
 +
 
 +
Конструктивно построим <tex>\forall M_1, M_2</tex> такие <tex>I \in \mathcal{I}_1 \cap \mathcal{I}_2</tex> и <tex>A \subseteq X</tex>, что <tex>|I| = r_1(A) + r_2(X \setminus A)</tex>.
 +
 
 +
Обозначим <tex>S = \left\{x \mid I \cup \{x\} \in \mathcal{I}_1\right\}</tex>, <tex>T = \left\{x \mid I \cup \{x\} \in \mathcal{I}_2\right\}</tex>. Если <tex>S \cap T \ne \varnothing</tex>, добавим их пересечение в <tex>I</tex>.
 +
 
 +
Построим [[Граф замен для двух матроидов|граф замен]] <tex>G_I</tex>. Добавим вершину <tex>z</tex>, не влияющую на независимость в первом матроиде {{---}} из неё будут вести рёбра во все вершины множества <tex>S</tex>. Пусть <tex>p</tex> {{---}} кратчайший путь из <tex>S</tex> в <tex>T</tex>, <tex>p_1</tex> {{---}} путь <tex>p</tex> с добавленным в начало ребром из <tex>z</tex>. По [[Лемма о единственном паросочетании в графе замен|лемме о единственном паросочетании]] и [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем|лемме о единственном паросочетании, индуцированном кратчайшем путём]] <tex>I \bigtriangleup p_1 \in \mathcal{I}_2</tex>. Теперь добавим вершину <tex>u</tex>, не влияющую на независимость во втором матроиде {{---}} в неё будут вести рёбра из всех вершин множества <tex>T</tex>. Тогда <tex>p_2</tex> (путь <tex>p</tex> с добавленным ребром в <tex>u</tex>) — кратчайший путь из <tex>S</tex> в <tex>u</tex>. Аналогично, <tex>I \bigtriangleup p_2 \in \mathcal{I}_1</tex>. Отсюда следует, что <tex>I \bigtriangleup p \in \mathcal{I}_1 \cap \mathcal{I}_2</tex>, причём <tex>|I \bigtriangleup p| = |I| + 1</tex>.</div>
 +
 
 +
Будем таким образом увеличивать <tex>I</tex>, пока существует путь <tex>p</tex>. Рассмотрим момент, когда такого пути не нашлось.
 +
Введём обозначение: <tex>A = \{u \mid u \rightsquigarrow T\}</tex>.
 +
 
 +
Докажем, что <tex>r_1(A) = |I \cap A|</tex> от противного.
 +
Пусть <tex>r_1(A) > |I \cap A|</tex>, тогда существует <tex>w \in A \setminus (I \cap A)</tex>, такое, что <tex>(I \cap A) \cup \{w\} \in \mathcal{I}_1</tex>. Если <tex>I \cup \{w\} \in \mathcal{I}_1</tex>, то <tex>w \in S</tex> и из <tex>S</tex> есть путь в <tex>A</tex>. Значит, <tex>I \cup \{w\} \notin \mathcal{I}_1</tex>. Отсюда следует, что существует <tex>y \in I \setminus A</tex>, такое что <tex>I \setminus \{y\} \cup \{w\} \in \mathcal{I}_1</tex>. Но тогда ребро <tex>yw</tex> имеется в графе, то есть из <tex>y</tex> существует путь в <tex>T</tex>, что противоречит условию <tex>y \in I \setminus A</tex>.
 +
 
 +
Следовательно, <tex>r_1(A) = |I \cap A|</tex>. Аналогично, <tex>r_2(\overline A) = |I \cap \overline A|</tex>. Отсюда <tex>r_1(A) + r_2(\overline A) = |I|</tex>, то есть при найденных <tex>I</tex> и <tex>A</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>
+
* ''Chandra Chekuri'' — [http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture17.pdf '''Combinatorial Optimization''']
    <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
 
    }
 
  }
 

Текущая версия на 19:30, 4 сентября 2022

Задача:
Даны матроиды [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) \mid y \in J, z \in S\setminus J, J - y + z \in \mathcal{I}_1 \} [/math] [math]\cup \{ (z', y') \mid z' \in S \setminus J, y' \in J, J - y' + z' \in \mathcal{I}_2 \}[/math].

Пусть [math]X_1 = \{ z \in S \setminus J \mid J + z \in \mathcal{I}_1 \}[/math], [math]X_2 = \{ z \in S \setminus J \mid 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 \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]X_1[/math].

Теорема Эдмондса-Лоулера

Теорема (Эдмондса-Лоулера):
Пусть [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 \mid I \cup \{x\} \in \mathcal{I}_1\right\}[/math], [math]T = \left\{x \mid 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 \mid 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]

См. также

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