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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 6 участников)
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
 
|definition=
 
|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>M_1 = (S, \mathcal{I}_1), \ldots ,(S, \mathcal{I}_k)</tex>. Необходимо найти максимальное по мощности [[Определение матроида#def_matroid|независимое множество]] в объединении <tex>M_1\ldots M_k</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Объединение матроидов''' <tex>M</tex> = <tex>\langle S,J \rangle</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S,J_i \rangle</tex>
+
'''Объединение матроидов''' (англ. ''matroid union'') <tex>M = (S,\mathcal{I}) = \bigcup\limits_{k=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i = (S,\mathcal{I}_i)</tex>
 
}}
 
}}
  
 
== Алгоритм ==
 
== Алгоритм ==
  
Определим [[Граф замен|граф замен]]: для каждого <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>I_i \in \mathcal{I}_i</tex>, для <tex>i = 1\ldots k</tex> с <tex>I_i \cap I_j = \emptyset</tex>, если <tex>i \neq j</tex>. Определим [[Граф замен|граф замен]]: для каждого <tex>M_i</tex> построим [[Основные определения теории графов#defBiparateGraph|двудольный ориентированный граф]] <tex>D_{M_i}(I_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 \mathcal{I}_i</tex>.
  
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов. Пусть для каждого <tex>i:</tex> <tex>F_i</tex> - множество вершин из <tex>S_i \setminus I_i</tex>, которые могут быть добавлены в <tex>I_i</tex> таким образом, что <tex>I_i + x</tex> независимое множество в <tex>M_i</tex>. Или формально:
+
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов. Пусть для каждого <tex>i:</tex> <tex>F_i</tex> {{---}} множество элементов <tex>s \notin I_i</tex> с <tex>I_i \cup {s} \in \mathcal{I}_i</tex>. Определим <tex>I = I_1 \cup \ldots \cup I_k</tex>, <tex>F = F_1 \cup \ldots \cup F_k</tex> и <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup  \mathcal{I}_k</tex>.
  
<tex>F_i = \{ x \in S \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>D_{M_i}(I_i)</tex> ([[Алгоритм построения базы в объединении матроидов#th_1|следующая теорема]] отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как <tex>I</tex>.
 
+
Тогда нужно найти такой элемент <tex>s \in S \setminus I</tex>, что <tex>I \cup s</tex> — снова независимо.
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. Иначе говоря, на каждом шаге мы выбираем элемент не из текущего множества, который оставит текущее множество независимым ([[Алгоритм построения базы в объединении матроидов#th_1|следующая теорема]] отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как <tex>I</tex>.
+
Все наши кандидаты находятся в <tex>S \setminus I</tex> . Если мы найдем путь из <tex>F</tex> в <tex>S \setminus I</tex>, то элемент <tex>s</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> и поиске такого пути.
 
То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути.
  
=== Псевдокод ===
+
'''Псевдокод'''
 
   <tex>J</tex> = <tex>\emptyset</tex>
 
   <tex>J</tex> = <tex>\emptyset</tex>
   isMaximal = ''false''
+
   '''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>n - 1</tex>
  '''while''' '''not''' isMaximal
+
       построить [[Граф замен|граф замен]] <tex>D_{M_i}(I_i)</tex>
       построить [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J)</tex>
+
       '''if''' <tex>I_i + s \in \mathcal{I}_i</tex>
       <tex>X_1 \leftarrow \{ z \in S \setminus J \mid J + z \in \mathcal{I}_1 \}</tex>
+
          <tex>J \leftarrow I_i + s</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>
+
Это подразумевает, что максимальное независимое множество в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup  \mathcal{I}_k</tex> мы можем найти за полиномиальное время (жадно наращивать независимое множество в <tex>M = M_1 \cup \ldots \cup M_k</tex>). Cunningham<ref>Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, стр.732</ref> разработал алгоритм, которым за <tex>O((n^{(3/2)} + k)mQ + n^{(1/2)}km)</tex> можно найти максимальное независимое множество в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup  \mathcal{I}_k</tex>, где <tex>n</tex> максимальный размер множества в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup  \mathcal{I}_k</tex>, <tex>m</tex> размер подмножества и <tex>Q</tex> время, необходимое, чтобы определить принадлежит ли множество <tex> \mathcal{I}_j</tex> для каждого <tex>j</tex>. Более детальное объяснение алгоритма (но не время работы) можно найти у C. Greene и T.L. Magnanti<ref>C. Greene, T.L. Magnanti, Some abstract pivot algorithms, SIAM Journal on Applied Mathematics, p.530-539</ref>.
      '''else'''
 
          isMaximal = ''true''
 
  
  
Строка 39: Строка 36:
 
|id=th_1
 
|id=th_1
 
|statement=
 
|statement=
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + s \in \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
+
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I \cup s \in \mathcal{I} \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам графа <tex>D</tex>.
 
|proof=
 
|proof=
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
  
Пусть существует путь из <tex>F</tex> в <tex>s</tex> и <tex>P</tex> — самый короткий такой путь. Запишем его вершины как {<tex>s_0, s_1, ... s_p</tex>}. <tex>s_0 \in F</tex>, так что не умаляя общности можно сказать, что <tex>s_0 \in F_1</tex>. Для каждого <tex>j = 1...k</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>F</tex> в <tex>s</tex> и <tex>P</tex> — самый короткий такой путь. Запишем его вершины как {<tex>s_0, s_1, \ldots s_p</tex>}. <tex>s_0 \in F</tex>, так что не умаляя общности можно сказать, что <tex>s_0 \in F_1</tex>. Для каждого <tex>j = 1\ldots k</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>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> независимо в объединении матроидов.
  
Строка 50: Строка 47:
 
Пусть нет пути из <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>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>|I_i \cap T| = r_i(I_i\cap T) \leqslant 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>s \in T</tex> и <tex>(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s</tex> . Из определния функции [[Определение матроида#def_rank_of_matroid|ранга]] объединения матроидов имеем :  
  
<tex>r_M(I + s) \le (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))</tex>
+
<tex>r_M(I + s) \leqslant (|(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>r_M(I + s) \leqslant |(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> — противоречие.
 
и значит <tex>(I + s) \notin J</tex> — противоречие.
 
}}
 
}}
Строка 62: Строка 59:
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Алгоритм построения базы в пересечении матроидов]]
 
* [[Алгоритм построения базы в пересечении матроидов]]
 +
 +
== Примечания ==
 +
<references/>
  
 
== Источники информации ==
 
== Источники информации ==
 
[https://math.mit.edu/~goemans/18438F09/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13]
 
[https://math.mit.edu/~goemans/18438F09/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13]
 +
 +
Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, {{---}} Springer, 2004, {{---}} стр.732
 +
 +
[http://booksc.org/book/18618751/0b4420 C. Greene, T.L. Magnanti, Some abstract pivot algorithms, SIAM Journal on Applied Mathematics 29 (1975) 530-539]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]
 
[[Категория:Объединение матроидов]]
 
[[Категория:Объединение матроидов]]

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

Задача:
Даны матроиды [math]M_1 = (S, \mathcal{I}_1), \ldots ,(S, \mathcal{I}_k)[/math]. Необходимо найти максимальное по мощности независимое множество в объединении [math]M_1\ldots M_k[/math].


Определение:
Объединение матроидов (англ. matroid union) [math]M = (S,\mathcal{I}) = \bigcup\limits_{k=1}^{n}[/math] [math]M_i[/math], где [math]M_i = (S,\mathcal{I}_i)[/math]


Алгоритм

Эта задача сводится к пересечению матроидов, однако есть другой способ её решить. Пусть [math]I_i \in \mathcal{I}_i[/math], для [math]i = 1\ldots k[/math] с [math]I_i \cap I_j = \emptyset[/math], если [math]i \neq j[/math]. Определим граф замен: для каждого [math]M_i[/math] построим двудольный ориентированный граф [math]D_{M_i}(I_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 \mathcal{I}_i[/math].

Объединим все [math]D_{M_i}(I_i)[/math] в один граф [math]D[/math], который будет суперпозицией ребер из этих графов. Пусть для каждого [math]i:[/math] [math]F_i[/math] — множество элементов [math]s \notin I_i[/math] с [math]I_i \cup {s} \in \mathcal{I}_i[/math]. Определим [math]I = I_1 \cup \ldots \cup I_k[/math], [math]F = F_1 \cup \ldots \cup F_k[/math] и [math] \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k[/math].

Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. На каждом шаге мы выбираем элемент не из текущего множества в новом графе замен [math]D_{M_i}(I_i)[/math] (следующая теорема отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как [math]I[/math]. Тогда нужно найти такой элемент [math]s \in S \setminus I[/math], что [math]I \cup 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]
 for [math]i \leftarrow 0[/math] to [math]n - 1[/math]
     построить граф замен [math]D_{M_i}(I_i)[/math]
     if [math]I_i + s \in \mathcal{I}_i[/math]
         [math]J \leftarrow I_i + s[/math]

Время работы

Это подразумевает, что максимальное независимое множество в [math] \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k[/math] мы можем найти за полиномиальное время (жадно наращивать независимое множество в [math]M = M_1 \cup \ldots \cup M_k[/math]). Cunningham[1] разработал алгоритм, которым за [math]O((n^{(3/2)} + k)mQ + n^{(1/2)}km)[/math] можно найти максимальное независимое множество в [math] \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k[/math], где [math]n[/math] максимальный размер множества в [math] \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k[/math], [math]m[/math] размер подмножества и [math]Q[/math] время, необходимое, чтобы определить принадлежит ли множество [math] \mathcal{I}_j[/math] для каждого [math]j[/math]. Более детальное объяснение алгоритма (но не время работы) можно найти у C. Greene и T.L. Magnanti[2].


Теорема:
Для любого [math]s \in S \setminus I[/math] имеем [math]I \cup s \in \mathcal{I} \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, \ldots s_p[/math]}. [math]s_0 \in F[/math], так что не умаляя общности можно сказать, что [math]s_0 \in F_1[/math]. Для каждого [math]j = 1\ldots 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) \leqslant 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) \leqslant (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))[/math]

[math]r_M(I + s) \leqslant |(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]

См. также

Примечания

  1. Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, стр.732
  2. C. Greene, T.L. Magnanti, Some abstract pivot algorithms, SIAM Journal on Applied Mathematics, p.530-539

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

Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13

Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, — Springer, 2004, — стр.732

C. Greene, T.L. Magnanti, Some abstract pivot algorithms, SIAM Journal on Applied Mathematics 29 (1975) 530-539