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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Объединение матроидов <tex>M</tex> = <tex>\langle S,J \rangle</tex> = <tex>\cup _{k=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S_i,J_i \rangle</tex>
+
Объединение матроидов <tex>M</tex> = <tex>\langle S,J \rangle</tex> = <tex>\cup _{k=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S,J_i \rangle</tex>
 
}}
 
}}
  
Строка 20: Строка 20:
 
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + x \in J_i  \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
 
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + x \in J_i  \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
 
|proof=
 
|proof=
 +
<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>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>
 
}}
 
}}
  

Версия 09:02, 27 июня 2011

Определение:
Объединение матроидов [math]M[/math] = [math]\langle S,J \rangle[/math] = [math]\cup _{k=1}^{n}[/math] [math]M_i[/math], где [math]M_i[/math] = [math]\langle S,J_i \rangle[/math]


Определение:
Для каждого [math]M_i[/math] построим двудольный ориентированный граф [math]D_{M_i}(I_i)[/math], такой что в левой доле находятся вершины из [math]I_i[/math], а в правой - вершины из [math]S_i \setminus I_i[/math]. Построим ориентированные ребра из [math]y \in I_i[/math] в [math]x \in S_i \setminus I_i[/math], при условии, что [math]I_i - y + x \in J_i[/math].


Объединим все [math]D_{M_i}(I_i)[/math] в один граф [math]D[/math], который будет суперпозицией ребер из этих графов.


Определение:
[math]F_i[/math] = { [math]x \in S_i \setminus I_i[/math] : [math]I_i + x \in J_i [/math]}. [math]F[/math] = [math]\cup _{k=1}^{n}[/math] [math]F_i[/math]


Теорема:
Для любого [math]s \in S \setminus I[/math] имеем [math]I + x \in J_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, ... s_p[/math]}. [math]s_0 \in F[/math], так что не умаляя общности можно сказать, что [math]s_0 \in F_1[/math]. Для каждого [math]j = 1...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]\triangleleft[/math]

Алгоритм

Нам известно, что объединение матроидов - матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым. Здесь мы обозначили текущее множество как [math]I[/math]. Тогда нужно найти такой элемент [math]s \in S \setminus I[/math], что [math]I + s[/math] - снова независимо. Все наши кандидаты находятся в [math]S \setminus I[/math]. Если мы найдем путь из [math]F[/math] в [math]S \setminus I[/math], то элемент [math]s[/math], которым путь закончился, можно будет добавить в [math]I[/math]. То есть шаг жадного алгоритма заключается в создании нового [math]D[/math] и поиске такого пути.


Источник

Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13