Изменения
Нет описания правки
о циклах
|statement=
Пусть <tex>M(E)</tex> — {{---}} матроид и <tex>Ccl</tex> — {{---}} семейство его циклов. Тогда: <br/>
1) <tex>\varnothing \notin Ccl</tex>; <br/>
2) Если <tex>C_1, C_2 \in Ccl</tex> и <tex>C_1 \ne C_2</tex>, то <tex>C_1 \nsubseteq C_2</tex> и <tex>C_2 \nsubseteq C_1</tex>; <br/>
3) Если <tex>C_1, C_2 \in Ccl, C_1 \ne C_2</tex> и <tex>p \in C_1 \cap C_2</tex>, то существует <tex>C \in Ccl</tex> такой, что <tex>C \subseteq (C_1 \cup C_2) \setminus p.</tex>
|proof=
1) Из [[Определение матроида|определения матроида]] (первой аксиомы) <tex>\varnothing \in I</tex>, где <tex>I</tex> — {{---}} семейство независимых множеств матроида <tex>M</tex>. Откуда <tex>\varnothing \notin Ccl</tex>. <br/>
2) От противного. Из определения цикла: если <tex>C_1 \subset C_2</tex>, то <tex>C_1 \in I</tex>. Значит <tex>C_1 \notin Ccl</tex>. Противоречие. Аналогично <tex>C_2 \nsubseteq C_1</tex>. <br/>
3) От противного. Пусть <tex>D = (C_1 \cup C_2) \setminus p</tex> независимо.<br/>
Обозначим <tex>A = C_1 \cap C_2</tex>. Покажем, что <tex>|A| < |D|</tex>. Из предыдущего пункта очевидным образом следует, что <tex>|C_1 \setminus C_2| > 0</tex> и <tex>|C_2 \setminus C_1| > 0</tex>.
<tex>|D| = |C_1 \setminus C_2| + |C_2 \setminus C_1| + |A| - 1 \ge |A| + 1 + 1 - 1 = |A| + 1 > |A|</tex><br/>Отсюда путем многократного применения третьей аксиомы матроидов получим <tex>\exists B: A \subset B</tex> и <tex>|B| = |D|</tex>, причем <tex>B</tex> {{---}} независимо. <br/>Поскольку <tex>C_1</tex> {{---}} цикл, <tex>C_1 \nsubseteq B</tex>. Значит, найдется хотя бы один элемент в <tex>C_1 \setminus A</tex>, не лежащий в <tex>B</tex>. Значит в <tex>B</tex> лежит не более чем <tex>|C_1 \setminus A| - 1</tex> элементов из этого множества. Аналогично в <tex>B</tex> лежит не более чем <tex>|C_2 \setminus A| - 1</tex> элементов из множества <tex>C_2 \setminus A</tex>. <br/>Получаем: <tex>|B| \le |A| + |C_1 \setminus A| - 1 + |C_2 \setminus A| - 1 = |C_1 \cup C_2| - 2 = |D| - 1</tex>. А поскольку <tex>|B| = |D|</tex> получаем противоречие.
}}
