Ранговая функция, полумодулярность — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о рангах)
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition= Пусть дан [[Определение матроида|матроид]]  <tex> M = \langle X, I \rangle</tex>. '''Ранговая функция (rank function)''' <tex>r: 2^X \to Z_+</tex> определяется как: <tex>r(A) = \max \{ |B| : B \subset A, B \in I\}</tex>
+
|definition= Пусть дан [[Определение матроида|матроид]]  <tex> M = \langle X, I \rangle</tex>. '''Ранговая функция''' (англ. ''rank function'') <tex>r: A \in 2^X \to \mathbb{N}</tex> определяется как: <tex>r(A) = \max \{ |B| : B \subset A, B \in I\}</tex>
 
}}
 
}}
  
 
==Полумодулярность ранговой функции==
 
==Полумодулярность ранговой функции==
Докажем свойство полумодулярности (submodularity) ранговой функции: <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le r(A) + r(B)</tex>. Для начала небольшая лемма.
+
Докажем свойство полумодулярности (англ: ''submodularity'') ранговой функции: <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \leqslant r(A) + r(B)</tex>. Для начала небольшая лемма.
  
 
{{Лемма
 
{{Лемма
Строка 18: Строка 18:
 
{{Теорема
 
{{Теорема
 
|id=theorem
 
|id=theorem
|statement=Пусть дан матроид <tex> M = \langle X, I \rangle</tex>, тогда <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le r(A) + r(B)</tex>
+
|statement=Пусть дан матроид <tex> M = \langle X, I \rangle</tex>, тогда <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \leqslant r(A) + r(B)</tex>
 
|proof=  
 
|proof=  
 
Рассмотрим множество <tex>D_\cap \subset A \cap B : D_\cap \in I, |D_\cap| = r(A \cap B)</tex>, такое всегда существует по определению <tex>r</tex>. Дополним множество <tex>D_\cap</tex> элементами из <tex>B \setminus D_\cap</tex> до множества <tex>D_B : |D_B| = r (B), D_B \in I</tex> (по [[#lemma|лемме]] такое возможно).  
 
Рассмотрим множество <tex>D_\cap \subset A \cap B : D_\cap \in I, |D_\cap| = r(A \cap B)</tex>, такое всегда существует по определению <tex>r</tex>. Дополним множество <tex>D_\cap</tex> элементами из <tex>B \setminus D_\cap</tex> до множества <tex>D_B : |D_B| = r (B), D_B \in I</tex> (по [[#lemma|лемме]] такое возможно).  
  
Далее дополним <tex>D_B</tex> элементами из <tex>A \cup B \setminus D_B</tex> до множества <tex>D_\cup : |D_\cup| = r(A \cup B), D_\cup \in I</tex>. Заметим, что на последнем шаге будут добавляться только элемента из <tex>A</tex>, т.к. пусть на том этапе мы взяли <tex>x \in B</tex>, тогда <tex>\{x\} \cup D_B \subset D_\cup, D_\cup \in I </tex>, следовательно <tex>\{x\} \cup D_B \in I</tex> (по [[Определение матроида]]), а также<tex>|\{x\} \cup D_B| = |D_B| + 1 = r(B) + 1</tex>, что невозможно по определению <tex>r</tex>.  
+
Далее дополним <tex>D_B</tex> элементами из <tex>A \cup B \setminus D_B</tex> до множества <tex>D_\cup : |D_\cup| = r(A \cup B), D_\cup \in I</tex>. Заметим, что на последнем шаге будут добавляться только элемента из <tex>A</tex>, т.к. пусть на том этапе мы взяли <tex>x \in B</tex>, тогда <tex>\{x\} \cup D_B \subset D_\cup, D_\cup \in I </tex>, следовательно <tex>\{x\} \cup D_B \in I</tex> (по [[Определение матроида|определению матроида]]), а также<tex>|\{x\} \cup D_B| = |D_B| + 1 = r(B) + 1</tex>, что невозможно по определению <tex>r</tex>.  
  
 
Заметим также, что   
 
Заметим также, что   
Строка 28: Строка 28:
 
<tex>(D_\cup \setminus D_B) \cup D_\cap \subset A</tex>, <tex>(D_\cup \setminus D_B) \cup D_\cap \in I</tex>
 
<tex>(D_\cup \setminus D_B) \cup D_\cap \subset A</tex>, <tex>(D_\cup \setminus D_B) \cup D_\cap \in I</tex>
  
(по [[Определение матроида]]), значит (по определению ранговой функции)
+
(по [[Определение матроида|определению матроида]]), значит по определению ранговой функции:
  
<tex>r(A) \ge |(D_\cup \setminus D_B) \cup D_\cap| = |D_\cup| - |D_B| + |D_\cap|</tex>
+
<tex>r(A) \geqslant |(D_\cup \setminus D_B) \cup D_\cap| = |D_\cup| - |D_B| + |D_\cap|</tex>
  
 
Заменяя мощности на ранги:
 
Заменяя мощности на ранги:
  
<tex>r(A) +  r(B) \ge r(A \cup B) + r(A \cap B) </tex>  
+
<tex>r(A) +  r(B) \geqslant r(A \cup B) + r(A \cap B) </tex>  
 
 
Что и требовалось доказать.
 
 
}}
 
}}
  
Строка 43: Строка 41:
 
{{Теорема
 
{{Теорема
 
|id=theorem
 
|id=theorem
|statement=Пусть дан матроид <tex> M = \langle X, I \rangle</tex>, и <tex>r: 2^X \to \{0\} \cup \mathbb{N}</tex> {{---}} его ранговая функция. Тогда для любых <tex>A, B \subseteq 2^X</tex> выполняется следующее:
+
|statement=Пусть дан матроид <tex> M = \langle X, I \rangle</tex>, и <tex>r: A \in 2^X \to \mathbb{N}</tex> {{---}} его ранговая функция. Тогда для любых <tex>A, B \subseteq 2^X</tex> выполняется следующее:
 
#<tex> 0  \leqslant r(A)  \leqslant |A| </tex>  
 
#<tex> 0  \leqslant r(A)  \leqslant |A| </tex>  
 
#<tex> A \subseteq B \Rightarrow r(A)  \leqslant r(B) </tex>
 
#<tex> A \subseteq B \Rightarrow r(A)  \leqslant r(B) </tex>

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

Определение:
Пусть дан матроид [math] M = \langle X, I \rangle[/math]. Ранговая функция (англ. rank function) [math]r: A \in 2^X \to \mathbb{N}[/math] определяется как: [math]r(A) = \max \{ |B| : B \subset A, B \in I\}[/math]


Полумодулярность ранговой функции

Докажем свойство полумодулярности (англ: submodularity) ранговой функции: [math]\forall A, B \subset X,[/math] [math]r(A \cup B) + r(A \cap B) \leqslant r(A) + r(B)[/math]. Для начала небольшая лемма.

Лемма:
Дан матроид [math] M = \langle X, I \rangle[/math] и множество [math]A \subset X[/math]. Пусть также [math]B \subset A[/math], [math]B \in I[/math], тогда существует [math]D : B\subset D \subset A, D \in I, |D| = r(A)[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]E[/math] — подмножество [math]A[/math] такое, что [math]r(A) = |E|, E \in I[/math] (по определению ранговой функции такое [math]E[/math] всегда существует).

Предположим, что лемма неверна и максимальное независимое подмножество, которое мы можем получить из [math]B[/math] добавляя элементы из [math]A[/math] — это [math]C[/math], причем [math]|C| \lt r(A)[/math]. Тогда имеем: [math]C \in I, E \in I, |C| \lt |E|[/math], следовательно существует элемент [math]x \in E \setminus C: C \cup \{x\} \in I[/math]. Заметим также что [math]|C \cup {x}| = |C| + 1 \gt |C|[/math] и [math]x \in A[/math], т.к. [math]E \setminus C \subset A[/math], [math]B \subset C \cup \{x\}[/math]. Итак пришли к противоречию, мы получили множество большее по мощности, чем [math]C[/math] такое, что [math]B \subset C \subset A, C \in I[/math], значит исходное предположение было не верно, и мы можем найти множество [math]D[/math] удовлетворяющее необходимым условиям.
[math]\triangleleft[/math]

Итак теперь мы готовы доказать свойство полумодулярности ранговой функции.

Теорема:
Пусть дан матроид [math] M = \langle X, I \rangle[/math], тогда [math]\forall A, B \subset X,[/math] [math]r(A \cup B) + r(A \cap B) \leqslant r(A) + r(B)[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим множество [math]D_\cap \subset A \cap B : D_\cap \in I, |D_\cap| = r(A \cap B)[/math], такое всегда существует по определению [math]r[/math]. Дополним множество [math]D_\cap[/math] элементами из [math]B \setminus D_\cap[/math] до множества [math]D_B : |D_B| = r (B), D_B \in I[/math] (по лемме такое возможно).

Далее дополним [math]D_B[/math] элементами из [math]A \cup B \setminus D_B[/math] до множества [math]D_\cup : |D_\cup| = r(A \cup B), D_\cup \in I[/math]. Заметим, что на последнем шаге будут добавляться только элемента из [math]A[/math], т.к. пусть на том этапе мы взяли [math]x \in B[/math], тогда [math]\{x\} \cup D_B \subset D_\cup, D_\cup \in I [/math], следовательно [math]\{x\} \cup D_B \in I[/math] (по определению матроида), а также[math]|\{x\} \cup D_B| = |D_B| + 1 = r(B) + 1[/math], что невозможно по определению [math]r[/math].

Заметим также, что

[math](D_\cup \setminus D_B) \cup D_\cap \subset A[/math], [math](D_\cup \setminus D_B) \cup D_\cap \in I[/math]

(по определению матроида), значит по определению ранговой функции:

[math]r(A) \geqslant |(D_\cup \setminus D_B) \cup D_\cap| = |D_\cup| - |D_B| + |D_\cap|[/math]

Заменяя мощности на ранги:

[math]r(A) + r(B) \geqslant r(A \cup B) + r(A \cap B) [/math]
[math]\triangleleft[/math]


Теорема о рангах

Теорема:
Пусть дан матроид [math] M = \langle X, I \rangle[/math], и [math]r: A \in 2^X \to \mathbb{N}[/math] — его ранговая функция. Тогда для любых [math]A, B \subseteq 2^X[/math] выполняется следующее:
  1. [math] 0 \leqslant r(A) \leqslant |A| [/math]
  2. [math] A \subseteq B \Rightarrow r(A) \leqslant r(B) [/math]
  3. Неравенство полумодулярности: [math]\forall A, B \subset X,[/math] [math]r(A \cup B) + r(A \cap B) \leqslant r(A) + r(B)[/math]
Доказательство:
[math]\triangleright[/math]
  1. Очевидно из определения: максимальное независимое подмножество по мощности не может быть больше самого множества и меньше нуля.
  2. Пусть [math]C \subseteq A[/math] — максимальное независимое подмножество. Т.к. [math]A \subseteq B[/math], то [math]C \subseteq B[/math] — независимое подмножество. Поэтому [math]r(B) \geqslant |C|[/math] по определению, а значит [math]r(B) \geqslant r(A)[/math]
  3. Доказано выше.
[math]\triangleleft[/math]

См. также

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

  • Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
  • Will Johnson — Mathroids. June 3, 2009.