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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Нормальная картинка графа замен)
Строка 11: Строка 11:
 
<tex>(z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in I_2</tex>.
 
<tex>(z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in I_2</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_{M_1, M_2}(I)</tex> из <tex>X_1</tex> в <tex>X_2</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, либо позволяет найти набор большей мощности.
+
Пусть <tex>X_1 = \{z \in S \setminus I \mid I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I \mid I \cup z \in I_2 \}, P</tex> — кратчайший путь в <tex>D_{M_1, M_2}(I)</tex> из <tex>X_1</tex> в <tex>X_2</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, либо позволяет найти набор большей мощности.
  
 
== Источник ==
 
== Источник ==

Версия 00:30, 13 июня 2015

Граф замен [math]D_{M_1, M_2}(I)[/math]

Граф замен — специальный ориентированный двудольный граф, фигурирующий в теореме Эдмондса-Лоулера.

Пусть [math]I[/math] — текущее независимое множество, построенное алгоритмом для матроидов [math]M_1 = \langle S, I_1 \rangle[/math], [math]M_2 = \langle S, I_2 \rangle[/math]. Введем граф замен [math]D_{M_1, M_2}(I)[/math], левой долей которого являются элементы множества [math]I[/math], правой — все остальные элементы [math]S[/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].

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

Источник

Chandra ChekuriCombinatorial Optimization, с. 2-3.