Аксиоматизация матроида рангами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Минорные правки форматирования)
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
{{Лемма
 +
|statement=Пусть <tex>r: A \in 2^X \to \{0\} \cup \mathbb{N}</tex> удовлетворяет условиям теоремы ниже, <tex> B \subset A \in 2^X</tex>, <tex>r(B) = |B|</tex>, и <tex> A \setminus B = \{p_1,  \ldots p_t\}</tex>. Если <tex>r(B \cup p_i) = |B|</tex>  для любого <tex> i = 1, \ldots , t</tex>, то <tex>r(A) = |B|</tex>
 +
|proof=
 +
:По индукции: предположим, что <tex>r(B \cup p_1 \cup  \ldots \cup p_j) = |B|</tex> для некоторого <tex>j = 1, \ldots ,t-1</tex>. Тогда, применяя (2) и (3), получаем:
 +
:<tex>|B| = r(B) = r(B \cup p_1 \cup  \ldots \cup p_j) \leqslant r(B \cup p_1 \cup \ldots \cup p_{j+1}) \leqslant r(B \cup p_1\cup \ldots \cup p_j) + r(B \cup p_{j+1}) -r(B) = |B| + |B| - |B| = |B| </tex>.
 +
:Следовательно, <tex>r(B \cup p_1 \cup \ldots \cup p_{j+1}) = |B|</tex>.  Переход доказан, а значит, <tex>r(B \cup p_1 \cup  \ldots \cup p_t) = |B|</tex>.
 +
}}
 +
 +
 +
 
{{Теорема
 
{{Теорема
 
|about= об аксиоматизации матроида рангами
 
|about= об аксиоматизации матроида рангами
|statement= Пусть некоторая функция <tex>r: 2^X \to \{0\} \cup \mathbb{N}</tex>, где <tex>2^X</tex> - конечное непустое множество, удовлетворяет условиям: <br>
+
|statement= Пусть некоторая функция <tex>r: A \in 2^X \to \mathbb{N}</tex>, где <tex>X</tex> {{---}} конечное непустое множество, удовлетворяет условиям:  
(r.1) <tex> 0 \le r(A) \le |A| </tex> <br>
+
# <tex> 0 \leqslant r(A) \leqslant |A| </tex>.
(r.2) <tex> A \in B \to r(A) \le r(B) </tex> <br>
+
# <tex> A \subseteq B \Rightarrow r(A) \leqslant r(B) </tex>.
(r.3) <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le r(A) + r(B)</tex> <br>
+
# <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \leqslant r(A) + r(B)</tex>  
Тогда <tex>r</tex> является ранговой функцией однозначно определенного матроида на <tex>X</tex>. <br>
+
Тогда <tex>r</tex> является [[Ранговая функция, полумодулярность|ранговой функцией]] однозначно определенного матроида на <tex>X</tex>.  
|proof= Подмножество <tex>I \subseteq 2^X</tex> назовем <tex>r</tex>-независимым, если выполняется <tex>r(I) = |I|</tex>. Обозначим через <tex>\mathcal{I}</tex> множество всех <tex>r</tex>-независимых подмножеств из <tex>2^X</tex>. Докажем, что <tex>\mathcal{I}</tex> удовлетворяет аксиомам независимого множества 1, 2 и 3:<br>
+
|proof= Подмножество <tex>I \in 2^X</tex> назовем <tex>r</tex>-независимым, если выполняется <tex>r(I) = |I|</tex>. Обозначим через <tex>\mathcal{I} \subseteq 2^X</tex> множество всех <tex>r</tex>-независимых подмножеств из <tex>2^X</tex>. Докажем, что <tex>\mathcal{I}</tex> удовлетворяет [[Определение матроида|аксиомам независимого множества]] 1, 2 и 3:
  
'''1)''' В силу (r.1) выполняется <tex>r(\emptyset)=0</tex>, следовательно <tex> \emptyset \in \mathcal{I}</tex><br>
+
# В силу (1) выполняется <tex>r(\emptyset)=0</tex>, следовательно <tex> \emptyset \in \mathcal{I}</tex>.
 +
# Пусть <tex> I \in \mathcal{I}</tex> и <tex>J \subseteq I</tex>. Предположим от противного, что <tex>r(J) < |J|</tex>. Тогда, используя (1) и (3), получаем: <tex>|I| = r(I) = r(J \cup (I \setminus J)) \leqslant r(J) + r(I \setminus J) - r(\emptyset) < |J| + |I \setminus J| = |I|</tex>, что невозможно. Следовательно, <tex>r(J) = |J|</tex>, т.е. <tex> J \in \mathcal{I} </tex>
 +
# Пусть <tex>I, J \subseteq \mathcal{I}</tex> и <tex>|I| < |J|</tex>. Положим <tex>J \setminus I = \{p_1, \ldots,p_t\}</tex>. Пусть, от противного, <tex>I \cup p_i \nsubseteq \mathcal{I}</tex> для любого <tex>i = 1, \ldots,t</tex>. Тогда для <tex>i = 1, \ldots,t</tex> имеет место: <tex> |I| = r(I) \leqslant r(I \cup p_i) < |I \cup p_i| = |I| + 1</tex>, т.е. <tex> r(I \cup p_i) = |I|</tex>. Отсюда, в силу доказанной раннее леммы, получаем <tex> r(I \cup J) = |I|</tex>. С другой стороны, <tex>|I| < |J| = r(J) \leqslant r(I \cup J)</tex>. Противоречие.
  
'''2)''' Пусть <tex> I \in \mathcal{I}</tex> и <tex>J \subseteq I</tex>. Предположим от противного, что <tex>r(J) < |J|</tex>. Тогда, используя (r.1) и (r.3), получаем: <br>
 
<tex>|I| = r(I) = r(J \cup (I \setminus J)) \le r(J) + r(I \setminus J) - r(\emptyset) < |J| + |I \setminus J| = |I|</tex>, <br>
 
что невозможно. Следовательно, <tex>r(J) = |J|</tex>, т.е. <tex> J \in \mathcal{I} </tex> <br>
 
  
 
+
Все три аксиомы выполняются на <tex>\mathcal{I}</tex>, соответственно, семейство <tex>\mathcal{I}</tex> является семейством независимых множеств некоторого матроида <tex> M = \langle X, \mathcal{I} \rangle</tex>. Осталось проверить, что исходная функция <tex>r</tex> совпадает с ранговой функцией матроида <tex>M</tex>. Так как, по определению, ранговая функция равна мощности максимального независимого подмножества множества (мощности базы множества), для этого достаточно доказать, что для любой [[Теорема о базах|базы]] <tex>B</tex> произвольного множества <tex>A \in 2^X, B \subseteq A</tex> выполняется <tex> r(A) = |B| </tex>. Пусть <tex>B</tex> {{---}} [[Теорема о базах|база]] множества <tex>A \in 2^X</tex>. По определению <tex>r </tex> имеем <tex> r(B) = |B|</tex> и <tex>B</tex> {{---}} максимальное <tex>r</tex>-независимое подмножество из <tex>A</tex>. Если <tex>A=B</tex>, то, очевидно, <tex>r(A)=r(B).</tex> Поэтому пусть <tex>B \subset A</tex>. Пусть <tex> A \setminus B = \{p_1\ldots ,p_t\}</tex>. В силу максимальности <tex>B</tex> для любого <tex>i = 1, \ldots,t</tex> множество <tex>B \cup p_i</tex> не является <tex>r</tex>-независимым, т.е. <tex>r(B \cup p_i) < |B \cup p_i|</tex>. Тогда имеем: <tex> |B| = r(B) \leqslant r(B \cup p_i) < |B \cup p_i| = |B| + 1 </tex>,
{{Лемма
+
т.е. <tex> r(B \cup p_i) = |B| </tex>. В силу доказанного утверждения получаем <tex>r(A) = |B|</tex>.  
|statement=Пусть <tex> B \subset A \subseteq 2^X</tex>, <tex>r(B) = |B|</tex>, и <tex> A \setminus B = \{p_1, ... p_t\}</tex>. Если <tex>r(B \cup p_i) = |B|</tex>   для любого <tex> i = 1,..., t</tex>, то <tex>r(A) = |B|</tex>
 
|proof=По индукции: предположим, что <tex>r(B \cup p_1 \cup ... \cup p_j) = |B|</tex> для некоторого <tex>j = 1,...,t-1</tex>. Тогда, применяя (r.2) и (r.3), получаем: <br>
 
<tex>|B| = r(B) \le r(B \cup p_1 \cup ... \cup p_j+1) \le r(B \cup p_1 \cup ... \cup p_j) + r(B \cup p_j+1) -r(B) = |B| + |B| - |B| = |B| </tex>. <br>
 
Следовательно, <tex>r(B \cup p_1 \cup ... \cup p_j+1) = |B|</tex>. Переход доказан, а значит, <tex>r(B \cup p_1 \cup ... \cup p_t) = |B|</tex>. <br>
 
 
}}
 
}}
  
'''3)''' Пусть <tex>I, J \in \mathcal{I}</tex> и <tex>|I| < |J|</tex>. Положим <tex>J \setminus I = \{p_1,...,p_t\}</tex>. Пусть, от противного, <tex>I \cup p_i \notin \mathcal{I}</tex> для любого <tex>i = 1,...,t</tex>. Тогда для <tex>i = 1,...,t</tex> имеет место: <br>
+
== См. также==
<tex> |I| = r(I) \le r(I \cup p_i) < |I \cup p_i| = |I| + 1</tex>, т.е. <tex> r(I \cup p_i) = |I|</tex>. Отсюда, в силу доказанной раннее леммы, получаем <tex> r(I \cup J) = |I|</tex>. С другой стороны, <tex>|I| < |J| = r(J) \le r(I \cup J)</tex>. Противоречие. <br>
+
* [[Аксиоматизация матроида базами]]
 
+
* [[Аксиоматизация матроида циклами]]
  
Все три аксиомы выполняются на <tex>\mathcal{I}</tex>, соответственно, семейство <tex>\mathcal{I}</tex> является семейством независимых множеств некоторого матроида <tex> M = \langle X, \mathcal{I} \rangle</tex>. Осталось проверить, что исходная функция <tex>r</tex> совпадает с ранговой функцией матроида <tex>M</tex>. Для этого надо доказать, что для любой базы <tex>B</tex> произвольного множества <tex>A \subseteq 2^X</tex> выполняется <tex> r(A) = |B|. Пусть <tex>B</tex> - база множества <tex>A \subseteq 2^X</tex>. По определению <tex>\mathcal{I} </tex> имеем <tex> r(B) = |B|</tex> и <tex>B</tex> - максимальное <tex>r</tex>-независимое подмножество из <tex>A</tex>. Если <tex>A=B</tex>, то, очевидно, <tex>r(A)=r(B)</tex>. Поэтому пусть <tex>B \in A</tex>. Пусть <tex> A \setminus B = \{p_1, ... ,p_t\}</tex>. В силу максимальности <tex>B</tex> для любого <tex>i = 1,...,t</tex> множество <tex>B \cup p_i</tex> не является <tex>r</tex>-независимым, т.е. <tex>r(B \cup p_i) < |B \cup p_i|</tex>. Тогда имеем: <br>
+
== Источники информации==
<tex> |B| = r(B) \le r(B \cup p_i) < |B \cup p_i| = |B| + 1 </tex>, <br>
+
*''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
т.е. <tex> r(B \cup p_i) = |B| </tex>. В силу доказанного утверждения получаем <tex>r(A) = |B|</tex>. <br>
 
Теорема доказана.
 
}}
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]
 +
[[Категория:Основные факты теории матроидов]]

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

Лемма:
Пусть [math]r: A \in 2^X \to \{0\} \cup \mathbb{N}[/math] удовлетворяет условиям теоремы ниже, [math] B \subset A \in 2^X[/math], [math]r(B) = |B|[/math], и [math] A \setminus B = \{p_1, \ldots p_t\}[/math]. Если [math]r(B \cup p_i) = |B|[/math] для любого [math] i = 1, \ldots , t[/math], то [math]r(A) = |B|[/math]
Доказательство:
[math]\triangleright[/math]
По индукции: предположим, что [math]r(B \cup p_1 \cup \ldots \cup p_j) = |B|[/math] для некоторого [math]j = 1, \ldots ,t-1[/math]. Тогда, применяя (2) и (3), получаем:
[math]|B| = r(B) = r(B \cup p_1 \cup \ldots \cup p_j) \leqslant r(B \cup p_1 \cup \ldots \cup p_{j+1}) \leqslant r(B \cup p_1\cup \ldots \cup p_j) + r(B \cup p_{j+1}) -r(B) = |B| + |B| - |B| = |B| [/math].
Следовательно, [math]r(B \cup p_1 \cup \ldots \cup p_{j+1}) = |B|[/math]. Переход доказан, а значит, [math]r(B \cup p_1 \cup \ldots \cup p_t) = |B|[/math].
[math]\triangleleft[/math]


Теорема (об аксиоматизации матроида рангами):
Пусть некоторая функция [math]r: A \in 2^X \to \mathbb{N}[/math], где [math]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]r[/math] является ранговой функцией однозначно определенного матроида на [math]X[/math].
Доказательство:
[math]\triangleright[/math]

Подмножество [math]I \in 2^X[/math] назовем [math]r[/math]-независимым, если выполняется [math]r(I) = |I|[/math]. Обозначим через [math]\mathcal{I} \subseteq 2^X[/math] множество всех [math]r[/math]-независимых подмножеств из [math]2^X[/math]. Докажем, что [math]\mathcal{I}[/math] удовлетворяет аксиомам независимого множества 1, 2 и 3:

  1. В силу (1) выполняется [math]r(\emptyset)=0[/math], следовательно [math] \emptyset \in \mathcal{I}[/math].
  2. Пусть [math] I \in \mathcal{I}[/math] и [math]J \subseteq I[/math]. Предположим от противного, что [math]r(J) \lt |J|[/math]. Тогда, используя (1) и (3), получаем: [math]|I| = r(I) = r(J \cup (I \setminus J)) \leqslant r(J) + r(I \setminus J) - r(\emptyset) \lt |J| + |I \setminus J| = |I|[/math], что невозможно. Следовательно, [math]r(J) = |J|[/math], т.е. [math] J \in \mathcal{I} [/math]
  3. Пусть [math]I, J \subseteq \mathcal{I}[/math] и [math]|I| \lt |J|[/math]. Положим [math]J \setminus I = \{p_1, \ldots,p_t\}[/math]. Пусть, от противного, [math]I \cup p_i \nsubseteq \mathcal{I}[/math] для любого [math]i = 1, \ldots,t[/math]. Тогда для [math]i = 1, \ldots,t[/math] имеет место: [math] |I| = r(I) \leqslant r(I \cup p_i) \lt |I \cup p_i| = |I| + 1[/math], т.е. [math] r(I \cup p_i) = |I|[/math]. Отсюда, в силу доказанной раннее леммы, получаем [math] r(I \cup J) = |I|[/math]. С другой стороны, [math]|I| \lt |J| = r(J) \leqslant r(I \cup J)[/math]. Противоречие.


Все три аксиомы выполняются на [math]\mathcal{I}[/math], соответственно, семейство [math]\mathcal{I}[/math] является семейством независимых множеств некоторого матроида [math] M = \langle X, \mathcal{I} \rangle[/math]. Осталось проверить, что исходная функция [math]r[/math] совпадает с ранговой функцией матроида [math]M[/math]. Так как, по определению, ранговая функция равна мощности максимального независимого подмножества множества (мощности базы множества), для этого достаточно доказать, что для любой базы [math]B[/math] произвольного множества [math]A \in 2^X, B \subseteq A[/math] выполняется [math] r(A) = |B| [/math]. Пусть [math]B[/math]база множества [math]A \in 2^X[/math]. По определению [math]r [/math] имеем [math] r(B) = |B|[/math] и [math]B[/math] — максимальное [math]r[/math]-независимое подмножество из [math]A[/math]. Если [math]A=B[/math], то, очевидно, [math]r(A)=r(B).[/math] Поэтому пусть [math]B \subset A[/math]. Пусть [math] A \setminus B = \{p_1, \ldots ,p_t\}[/math]. В силу максимальности [math]B[/math] для любого [math]i = 1, \ldots,t[/math] множество [math]B \cup p_i[/math] не является [math]r[/math]-независимым, т.е. [math]r(B \cup p_i) \lt |B \cup p_i|[/math]. Тогда имеем: [math] |B| = r(B) \leqslant r(B \cup p_i) \lt |B \cup p_i| = |B| + 1 [/math],

т.е. [math] r(B \cup p_i) = |B| [/math]. В силу доказанного утверждения получаем [math]r(A) = |B|[/math].
[math]\triangleleft[/math]

См. также

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

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