Изменения
Новая страница: «{{Определение |definition= Объединение матроидов <tex>M</tex> = <tex>\langle S,J \rangle</tex> = <tex>\bigcup\limits_{i=1}^{n}</tex...»
{{Определение
|definition=
Объединение матроидов <tex>M</tex> = <tex>\langle S,J \rangle</tex> = <tex>\bigcup\limits_{i=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S_i,J_i \rangle</tex>
}}
{{Определение
|definition=
Для каждого <tex>M_i</tex> построим двудольный ориентированный граф <tex>D_{M_i}(I_i)</tex>, где <tex>I_i \in J_i</tex>, такой что в левой доле находятся вершины из <tex>I_i</tex>, а в правой — вершины из <tex>S \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S \setminus I_i</tex>, при условии, что <tex>(I_i \setminus y) \cup x \in J_i</tex>.
}}
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов.
{{Определение
|definition=
<tex>F_i = \{ x \in S_i \setminus I_i : I_i + x \in J_i \}</tex>. <tex>F</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>F_i</tex>
}}
== Алгоритм ==
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым.
Здесь мы обозначим текущее множество как <tex>I</tex>.
Тогда нужно найти такой элемент <tex>s \in S \setminus I</tex>, что <tex>I + s</tex> — снова независимо.
Все наши кандидаты находятся в <tex>S \setminus I</tex>. Если мы найдем путь из <tex>F</tex> в <tex>S \setminus I</tex>, то элемент <tex>s</tex>, которым путь закончился, можно будет добавить в <tex>I</tex>.
То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути.
===Псевдокод===
union('''int''' <tex>S[n]</tex>, '''int''' <tex>J[n]</tex>):
'''int''' <tex>I[n]</tex>
'''bool''' reached = '''false'''
'''while''' '''not''' reached:
reached = '''true'''
'''int''' <tex>F[n]</tex>
'''Graph''' <tex>D[n]</tex>
'''for''' i = 1 '''to''' n
<tex>D[i]</tex> = build_bipartite_graph<tex>(I[i] ,S[i] \setminus I[i])</tex> <font color="darkgreen">// Строим двудольный граф D[i] </font>
<tex>F[i]</tex> =<tex> \{ x \in S \setminus I[i] : I[i] + x \in J[i] \}</tex>
'''for''' <tex>s \in S</teX>:
'''int[]''' <tex>P</tex> = find_shortest_path(<tex>F</tex>, <tex>s</tex>)
'''if''' find_shortest_path(<tex>F</tex>, <tex>s</tex>) <tex>\neq \varnothing </tex>:
reached = '''false'''
'''int''' <tex>pos</tex> = get_f(<tex>P[1]</tex>) <font color="darkgreen">// Находим <tex>F_i</tex>, которому принадлежит стартовая вершина в пути</font>
'''int''' <tex>V[n]</tex>
'''for''' j = 1 '''to''' <tex>P.len - 1</tex>:
'''int''' <tex>vertex\_num</tex> = get_D_by_edge<tex>(P[j],P[j+1])</tex> <font color="darkgreen">// Находим номер множества, соответствующего ребру <tex>(p[j],p[j+1])</tex></font>
<tex>V[vertex\_num].add(j)</tex>
<tex>V[vertex\_num].add(j + 1)</tex>
'''for''' j = 1 '''to''' n:
<tex> I[j]</tex> = <tex> I[j] \oplus V[j]</tex>
<tex>I[pos]</tex> = <tex>I[pos] \cup P[1] </tex>
'''break'''
{{Теорема
|statement=
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + s \in J \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
|proof=
<tex>\Leftarrow</tex>
Пусть существует путь из <tex>F</tex> в <tex>s</tex> и <tex>P</tex> — самый короткий такой путь. Запишем его вершины как <tex>\{s_0, s_1, \dots s_p\}</tex>. <tex>s_0 \in F</tex>, так что не умаляя общности можно сказать, что <tex>s_0 \in F_1</tex>. Для каждого <tex>j = 1...n</tex> определим множество вершин <tex>S_j =</tex> {<tex>s_i, s_{i+1}:(s_i, s_{i+1}) \in D_{M_j}(I_j)</tex>}, где <tex>i</tex> пробегает от <tex>0</tex> до <tex>p - 1</tex>.
Положим, что <tex>I'_1 = (I_1 \oplus S_1) \cup \{s_0\}</tex>, для всех <tex>j > 1</tex> положим <tex>I'_j = (I_j \oplus S_j)</tex>. Ясно, что <tex>\cup _j I'_j = I + s</tex>. Для того, чтобы показать независимость <tex>I + s</tex> в объединении матроидов нужно показать, что <tex>I'_j \in J_j</tex> для всех <tex>j</tex>. Заметим, что так как мы выбирали путь <tex>P</tex> таким, что он будет наименьшим, для каждого <tex>j > 1</tex> существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать <tex>I'_j = I_j \oplus S_j</tex>. Так как паросочетание единственно, <tex>I'_j \in J_j</tex>. Аналогично <tex>s_0 \in F_1</tex>, значит <tex>I'_1 \in J_1</tex>. Следовательно <tex>I + s</tex> независимо в объединении матроидов.
<tex>\Rightarrow</tex>
Пусть нет пути из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>. Тогда пусть существует множество <tex>T</tex>, состоящее из вершин <tex>D</tex>, из которого мы можем достичь <tex>s</tex> : <tex>T = \{x, \exists x \leadsto s\}</tex> по допущению <tex>F\cap T = \varnothing</tex>. Утверждается, что для всех <tex>i : |I_i \cap T| = r_i(T)</tex>(что означает, что <tex>I_i \cap T</tex> — максимальное подмножество <tex>T</tex>, независимое в <tex>M_i</tex>).
Предположим, что это не так. <tex>|I_i \cap T| = r_i(I_i\cap T) \le r_i(T)</tex>, это возможно только если <tex>|I_i \cap T| < r_i(T)</tex>. Значит существует такой <tex>x \in T \cap (S \setminus I_i)</tex>, для которого <tex>(I_i \cap T) + x \in J_i</tex>. Но <tex>x \notin F</tex> (по предположению вначале доказательства), значит <tex>I_i + x \notin J_i</tex>. Из этого следует, что <tex>I_i + x</tex> содержит единственный цикл. Значит существует <tex>y \in I_i - T</tex>, такой что <tex>I_i + x - y \in J_i</tex>. Получается, что <tex>(y, x)</tex> — ребро в <tex>D_{M_i}(I_i)</tex> и оно содержит этот <tex>y \in T</tex>, что противоречит тому как был выбран <tex>y \in I_i \setminus T</tex>. Следовательно для всех <tex>i</tex> нам известно : <tex>|I_i \cap T| = r_i(T)</tex>.
У нас есть <tex>s \in T</tex> и <tex>(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s</tex>. Из определния функции ранга объединения матроидов имеем :
<tex>r_M(I + s) \le (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))</tex>
<tex>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| < |I + s|</tex>
и значит <tex>(I + s) \notin J</tex> — противоречие.
}}
== Источник ==
[http://math.mit.edu/~goemans/18438/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13]
|definition=
Объединение матроидов <tex>M</tex> = <tex>\langle S,J \rangle</tex> = <tex>\bigcup\limits_{i=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S_i,J_i \rangle</tex>
}}
{{Определение
|definition=
Для каждого <tex>M_i</tex> построим двудольный ориентированный граф <tex>D_{M_i}(I_i)</tex>, где <tex>I_i \in J_i</tex>, такой что в левой доле находятся вершины из <tex>I_i</tex>, а в правой — вершины из <tex>S \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S \setminus I_i</tex>, при условии, что <tex>(I_i \setminus y) \cup x \in J_i</tex>.
}}
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов.
{{Определение
|definition=
<tex>F_i = \{ x \in S_i \setminus I_i : I_i + x \in J_i \}</tex>. <tex>F</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>F_i</tex>
}}
== Алгоритм ==
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым.
Здесь мы обозначим текущее множество как <tex>I</tex>.
Тогда нужно найти такой элемент <tex>s \in S \setminus I</tex>, что <tex>I + s</tex> — снова независимо.
Все наши кандидаты находятся в <tex>S \setminus I</tex>. Если мы найдем путь из <tex>F</tex> в <tex>S \setminus I</tex>, то элемент <tex>s</tex>, которым путь закончился, можно будет добавить в <tex>I</tex>.
То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути.
===Псевдокод===
union('''int''' <tex>S[n]</tex>, '''int''' <tex>J[n]</tex>):
'''int''' <tex>I[n]</tex>
'''bool''' reached = '''false'''
'''while''' '''not''' reached:
reached = '''true'''
'''int''' <tex>F[n]</tex>
'''Graph''' <tex>D[n]</tex>
'''for''' i = 1 '''to''' n
<tex>D[i]</tex> = build_bipartite_graph<tex>(I[i] ,S[i] \setminus I[i])</tex> <font color="darkgreen">// Строим двудольный граф D[i] </font>
<tex>F[i]</tex> =<tex> \{ x \in S \setminus I[i] : I[i] + x \in J[i] \}</tex>
'''for''' <tex>s \in S</teX>:
'''int[]''' <tex>P</tex> = find_shortest_path(<tex>F</tex>, <tex>s</tex>)
'''if''' find_shortest_path(<tex>F</tex>, <tex>s</tex>) <tex>\neq \varnothing </tex>:
reached = '''false'''
'''int''' <tex>pos</tex> = get_f(<tex>P[1]</tex>) <font color="darkgreen">// Находим <tex>F_i</tex>, которому принадлежит стартовая вершина в пути</font>
'''int''' <tex>V[n]</tex>
'''for''' j = 1 '''to''' <tex>P.len - 1</tex>:
'''int''' <tex>vertex\_num</tex> = get_D_by_edge<tex>(P[j],P[j+1])</tex> <font color="darkgreen">// Находим номер множества, соответствующего ребру <tex>(p[j],p[j+1])</tex></font>
<tex>V[vertex\_num].add(j)</tex>
<tex>V[vertex\_num].add(j + 1)</tex>
'''for''' j = 1 '''to''' n:
<tex> I[j]</tex> = <tex> I[j] \oplus V[j]</tex>
<tex>I[pos]</tex> = <tex>I[pos] \cup P[1] </tex>
'''break'''
{{Теорема
|statement=
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + s \in J \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
|proof=
<tex>\Leftarrow</tex>
Пусть существует путь из <tex>F</tex> в <tex>s</tex> и <tex>P</tex> — самый короткий такой путь. Запишем его вершины как <tex>\{s_0, s_1, \dots s_p\}</tex>. <tex>s_0 \in F</tex>, так что не умаляя общности можно сказать, что <tex>s_0 \in F_1</tex>. Для каждого <tex>j = 1...n</tex> определим множество вершин <tex>S_j =</tex> {<tex>s_i, s_{i+1}:(s_i, s_{i+1}) \in D_{M_j}(I_j)</tex>}, где <tex>i</tex> пробегает от <tex>0</tex> до <tex>p - 1</tex>.
Положим, что <tex>I'_1 = (I_1 \oplus S_1) \cup \{s_0\}</tex>, для всех <tex>j > 1</tex> положим <tex>I'_j = (I_j \oplus S_j)</tex>. Ясно, что <tex>\cup _j I'_j = I + s</tex>. Для того, чтобы показать независимость <tex>I + s</tex> в объединении матроидов нужно показать, что <tex>I'_j \in J_j</tex> для всех <tex>j</tex>. Заметим, что так как мы выбирали путь <tex>P</tex> таким, что он будет наименьшим, для каждого <tex>j > 1</tex> существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать <tex>I'_j = I_j \oplus S_j</tex>. Так как паросочетание единственно, <tex>I'_j \in J_j</tex>. Аналогично <tex>s_0 \in F_1</tex>, значит <tex>I'_1 \in J_1</tex>. Следовательно <tex>I + s</tex> независимо в объединении матроидов.
<tex>\Rightarrow</tex>
Пусть нет пути из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>. Тогда пусть существует множество <tex>T</tex>, состоящее из вершин <tex>D</tex>, из которого мы можем достичь <tex>s</tex> : <tex>T = \{x, \exists x \leadsto s\}</tex> по допущению <tex>F\cap T = \varnothing</tex>. Утверждается, что для всех <tex>i : |I_i \cap T| = r_i(T)</tex>(что означает, что <tex>I_i \cap T</tex> — максимальное подмножество <tex>T</tex>, независимое в <tex>M_i</tex>).
Предположим, что это не так. <tex>|I_i \cap T| = r_i(I_i\cap T) \le r_i(T)</tex>, это возможно только если <tex>|I_i \cap T| < r_i(T)</tex>. Значит существует такой <tex>x \in T \cap (S \setminus I_i)</tex>, для которого <tex>(I_i \cap T) + x \in J_i</tex>. Но <tex>x \notin F</tex> (по предположению вначале доказательства), значит <tex>I_i + x \notin J_i</tex>. Из этого следует, что <tex>I_i + x</tex> содержит единственный цикл. Значит существует <tex>y \in I_i - T</tex>, такой что <tex>I_i + x - y \in J_i</tex>. Получается, что <tex>(y, x)</tex> — ребро в <tex>D_{M_i}(I_i)</tex> и оно содержит этот <tex>y \in T</tex>, что противоречит тому как был выбран <tex>y \in I_i \setminus T</tex>. Следовательно для всех <tex>i</tex> нам известно : <tex>|I_i \cap T| = r_i(T)</tex>.
У нас есть <tex>s \in T</tex> и <tex>(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s</tex>. Из определния функции ранга объединения матроидов имеем :
<tex>r_M(I + s) \le (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))</tex>
<tex>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| < |I + s|</tex>
и значит <tex>(I + s) \notin J</tex> — противоречие.
}}
== Источник ==
[http://math.mit.edu/~goemans/18438/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13]
