34
правки
Изменения
Добавлена статья "Аксиоматизация матроида рангами"
{{Теорема
|about= об аксиоматизации матроида рангами
|statement= Пусть некоторая функция <tex>r: 2^X \to \{0\} \cup \mathbb{N}</tex>, где <tex>2^X</tex> - конечное непустое множество, удовлетворяет условиям: <br>
r.1) <tex> 0 \le r(A) \le |A| </tex> <br>
r.2) <tex> A \in B \to r(A) \le r(B) </tex> <br>
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>r</tex> является ранговой функцией однозначно определенного матроида на <tex>X</tex>. <br>
|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>
'''1)''' В силу r.1 выполняется <tex>r(\emptyset)=0</tex>, следовательно <tex> \emptyset \in \mathcal{I}</tex><br>
'''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>
{{Лемма
|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>, <br>
т.е. <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>
т.е. <tex> r(B \cup p_i) = |B| </tex>. В силу доказанного утверждения получаем <tex>r(A) = |B|</tex>. <br>
Теорема доказана.
}}
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
|about= об аксиоматизации матроида рангами
|statement= Пусть некоторая функция <tex>r: 2^X \to \{0\} \cup \mathbb{N}</tex>, где <tex>2^X</tex> - конечное непустое множество, удовлетворяет условиям: <br>
r.1) <tex> 0 \le r(A) \le |A| </tex> <br>
r.2) <tex> A \in B \to r(A) \le r(B) </tex> <br>
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>r</tex> является ранговой функцией однозначно определенного матроида на <tex>X</tex>. <br>
|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>
'''1)''' В силу r.1 выполняется <tex>r(\emptyset)=0</tex>, следовательно <tex> \emptyset \in \mathcal{I}</tex><br>
'''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>
{{Лемма
|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>, <br>
т.е. <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>
т.е. <tex> r(B \cup p_i) = |B| </tex>. В силу доказанного утверждения получаем <tex>r(A) = |B|</tex>. <br>
Теорема доказана.
}}
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
