Изменения

{{Теорема|about= об аксиоматизации матроида рангамиЛемма|statement= Пусть некоторая функция <tex>r: 2^X B \to subset A \{0\} \cup \mathbb{N}</tex>, где <tex>subseteq 2^X</tex> - конечное непустое множество, удовлетворяет условиям: <br>(r.1) <tex> 0 \le r(AB) \le = |AB| </tex> <br>(r.2) , и <tex> A \in setminus B = \to r(A) {p_1, \ldots p_t\le }</tex>. Если <tex>r(B\cup p_i) = |B|</tex> <br>(r.3) для любого <tex>\forall Ai = 1, B \subset Xldots ,t</tex> , то <tex>r(A \cup B) + r(A \cap = |B) \le r(A) + r(B)|</tex> <br>Тогда |proof=:По индукции: предположим, что <tex>r(B \cup p_1 \cup \ldots \cup p_j) = |B|</tex> является ранговой функцией однозначно определенного матроида на для некоторого <tex>Xj = 1, \ldots ,t-1</tex>. Тогда, применяя (2) и (3), получаем: <br>|proof= Подмножество :<tex>I |B| = r(B) \leqslant r(B \cup p_1 \cup \ldots \cup p_j+1) \subseteq 2^X</tex> назовем <tex>leqslant r(B \cup p_1 \cup \ldots \cup p_j) + r</tex>(B \cup p_j+1) -независимым, если выполняется <tex>r(IB) = |IB| + |B| - |B| = |B|</tex>. Обозначим через <texbr>\mathcal{I}</tex> множество всех :Следовательно, <tex>r</tex>-независимых подмножеств из <tex>2^X(B \cup p_1 \cup \ldots \cup p_j+1) = |B|</tex>. Докажем Переход доказан, а значит, что <tex>r(B \cup p_1 \mathcal{I}cup \ldots \cup p_t) = |B|</tex> удовлетворяет аксиомам независимого множества 1, 2 и 3:. <br>}}

* 2) {{Теорема|about= об аксиоматизации матроида рангами|statement= Пусть некоторая функция <tex> I r: 2^X \to \{0\} \in cup \mathcalmathbb{IN}</tex> и , где <tex>J \subseteq I2^X</tex>. Предположим от противного{{---}} конечное непустое множество, что удовлетворяет условиям: <br># <tex>0 \leqslant r(JA) < \leqslant |JA|</tex>. Тогда, используя # <tex> A \in B \to r(A) \leqslant r.1(B) и (r</tex>.3)# <tex>\forall A, B \subset X, получаем: <br/tex>*:<tex>|I| = r(IA \cup B) = + r(J \cup (I A \setminus J)cap B) \le leqslant r(JA) + r(I \setminus JB) - </tex> <br>Тогда <tex>r(\emptyset) < /tex> является [[Ранговая функция, полумодулярность|J| + ранговой функцией]] однозначно определенного матроида на <tex>X</tex>. <br>|proof= Подмножество <tex>I \setminus J| = |I|subseteq 2^X</tex>, назовем <tex>r<br/tex> *:что невозможно. Следовательно-независимым, если выполняется <tex>r(JI) = |JI|</tex>, т.еОбозначим через <tex>\mathcal{I}</tex> множество всех <tex>r</tex>-независимых подмножеств из <tex>2^X</tex>. Докажем, что <tex> J \in \mathcal{I} </tex> удовлетворяет [[Определение матроида|аксиомам независимого множества]] 1, 2 и 3:<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>. Пусть <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, ... \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>. Тогда имеем: <br><tex> |B| = r(B) \le leqslant r(B \cup p_i) < |B \cup p_i| = |B| + 1 </tex>, <br>

== Литература Источники информации==*''Асанов М. О., Баранский В. А., Расин В. В.'' {{- --}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' <br> == См. также==* [[Аксиоматизация матроида базами]]* [[Аксиоматизация матроида циклами]]