Граф замен — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 13: Строка 13:
 
Пусть <tex>X_1 = \{z \in S \setminus I | I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I | I \cup z \in I_2 \}, P</tex> - кратчайший путь в <tex>D</tex> из <tex>X_1</tex> в <tex>X_2</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, либо позволяет найти набор большей мощности.
 
Пусть <tex>X_1 = \{z \in S \setminus I | I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I | I \cup z \in I_2 \}, P</tex> - кратчайший путь в <tex>D</tex> из <tex>X_1</tex> в <tex>X_2</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, либо позволяет найти набор большей мощности.
 
}}
 
}}
 +
 +
== Источник ==
 +
''Chandra Chekuri'' — [http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture17.pdf '''Combinatorial Optimization'''], с. 2-3.

Версия 23:58, 25 июня 2011

Теорема:
Пусть [math]M_1 = \lt S, I_1\gt [/math] и [math]M_2 = \lt S, I_2\gt [/math] - матроиды с ранговыми функциями [math]r_1[/math] и [math]r_2[/math], соответственно. Тогда максимальная мощность множества из [math]I_1 \cap I_2[/math] равна [math]\min_{U \subset S} (r_1(U) + r_2(S \setminus U))[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]I \in I_1 \cap I_2[/math]. Следовательно, [math]\forall U \subset S[/math] верно [math]I \cap U \in I_1, I \setminus U \in I_2[/math]. Тогда, из определения ранга, [math]|I| = |I \cap U| + |I \setminus U| \leq r_1(U) + r_2(S \setminus U)[/math].

В другую сторону докажем теорему алгоритмически. На каждом этапе алгоритм получает [math]I \in I_1 \cap I_2[/math] и либо заключает, что множества большей мощности из [math]I_1 \cap I_2[/math] получить невозможно, либо возвращает [math]J \in I_1 \cap I_2: |J| = |I| + 1[/math].

Введем двудольный ориентированный граф замен для [math]M_1[/math] и [math]M_2[/math] - граф [math]D[/math]. Левой долей [math]D[/math] являются элементы текущего множества [math]I \in I_1 \cap I_2[/math], правой - все остальные элементы [math]S \setminus I[/math]. Проведем ребра [math](y, z): y \in I, z \in S \setminus I, I \setminus y \cup z \in I_1[/math], а также [math](z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in I_2[/math].

ExchangeGraph.JPG

Пусть [math]X_1 = \{z \in S \setminus I | I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I | I \cup z \in I_2 \}, P[/math] - кратчайший путь в [math]D[/math] из [math]X_1[/math] в [math]X_2[/math]. Тогда алгоритм с помощью этого пути либо определяет максимальность набора [math]I[/math], либо позволяет найти набор большей мощности.
[math]\triangleleft[/math]

Источник

Chandra ChekuriCombinatorial Optimization, с. 2-3.