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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
 
|id = minsum  
 
|id = minsum  
|statement = Пусть <tex>M_1 = <X, I_1></tex> и <tex>M_2 = <X, I_2></tex> - [[Определение матроида|матроиды]] с [[Ранговая функция, полумодулярность|ранговыми функциями]] <tex>r_1</tex> и <tex>r_2</tex>, соответственно. Тогда максимальная мощность множества из <tex>I_1 \cap I_2</tex> равна <tex>\min_{U \subset X} (r_1(U) + r_2(X \setminus U))</tex>.
+
|statement = Пусть <tex>M_1 = <S, I_1></tex> и <tex>M_2 = <S, I_2></tex> - [[Определение матроида|матроиды]] с [[Ранговая функция, полумодулярность|ранговыми функциями]] <tex>r_1</tex> и <tex>r_2</tex>, соответственно. Тогда максимальная мощность множества из <tex>I_1 \cap I_2</tex> равна <tex>\min_{U \subset S} (r_1(U) + r_2(S \setminus U))</tex>.
 
|proof =  
 
|proof =  
Пусть <tex>I \in I_1 \cap I_2</tex>. Следовательно, <tex>\forall U \subset X</tex> верно <tex>I \cap U \in I_1, I \setminus U \in I_2</tex>. Тогда, из определения ранга, <tex>|I| = |I \cap U| + |I \setminus U| \leq r_1(U) + r_2(X \setminus U)</tex>.
+
Пусть <tex>I \in I_1 \cap I_2</tex>. Следовательно, <tex>\forall U \subset S</tex> верно <tex>I \cap U \in I_1, I \setminus U \in I_2</tex>. Тогда, из определения ранга, <tex>|I| = |I \cap U| + |I \setminus U| \leq r_1(U) + r_2(S \setminus U)</tex>.
  
 
В другую сторону докажем теорему алгоритмически. На каждом этапе алгоритм получает <tex>I \in I_1 \cap I_2</tex> и либо заключает, что множества большей мощности из <tex>I_1 \cap I_2</tex> получить невозможно, либо возвращает <tex>J \in I_1 \cap I_2: |J| = |I| + 1</tex>.
 
В другую сторону докажем теорему алгоритмически. На каждом этапе алгоритм получает <tex>I \in I_1 \cap I_2</tex> и либо заключает, что множества большей мощности из <tex>I_1 \cap I_2</tex> получить невозможно, либо возвращает <tex>J \in I_1 \cap I_2: |J| = |I| + 1</tex>.
  
Введем двудольный ориентированный '''граф замен''' для <tex>M_1</tex> и <tex>M_2</tex> - граф <tex>D</tex>. Левой долей <tex>D</tex> являются элементы текущего множества <tex>I \in I_1 \cap I_2</tex>, правой - все остальные элементы <tex>X \setminus I</tex>. Проведем ребра <tex>(y, z): y \in I, z \in X \setminus I, I \setminus y \cup z \in I_1</tex>, а также <tex>(z', y'): y' \in I, z' \in X \setminus I, I \setminus y' \cup z' \in I_2</tex>.
+
Введем двудольный ориентированный '''граф замен''' для <tex>M_1</tex> и <tex>M_2</tex> - граф <tex>D</tex>. Левой долей <tex>D</tex> являются элементы текущего множества <tex>I \in I_1 \cap I_2</tex>, правой - все остальные элементы <tex>S \setminus I</tex>. Проведем ребра <tex>(y, z): y \in I, z \in S \setminus I, I \setminus y \cup z \in I_1</tex>, а также <tex>(z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in I_2</tex>.
  
 
[[Файл:ExchangeGraph.JPG]]
 
[[Файл:ExchangeGraph.JPG]]
  
Пусть <tex>X_1 = \{z \in X \setminus I | I \cup z \in I_1 \}, X_2 = \{z \in X \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>, либо позволяет найти набор большей мощности.
 
}}
 
}}

Версия 23:55, 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]