Изменения

'''Циклом''' (англ. '''circuit''') в матроиде называется множество, не являющееся независимым, каждое подмножество которого является независимым.

Пусть <tex>M</tex> {{---}} матроид и <tex>Ccl\mathfrak{C}</tex> {{---}} семейство его циклов. Тогда: <br/>1) # <tex>\varnothing \notin Ccl\mathfrak{C}</tex>; <br/>2) # Если <tex>C_1, C_2 \in Ccl\mathfrak{C}</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\mathfrak{C}, C_1 \ne C_2</tex> и <tex>p \in C_1 \cap C_2</tex>, то существует <tex>C \in Ccl\mathfrak{C}</tex> такой, что <tex>C \subseteq (C_1 \cup C_2) \setminus p.</tex>

1) # Из [[Определение матроида|определения матроида]] (первой аксиомы) <tex>\varnothing \in I</tex>, где <tex>I</tex> {{---}} семейство независимых множеств матроида <tex>M</tex>. Откуда <tex>\varnothing \notin Ccl\mathfrak{C}</tex>. <br/>2) # От противного. Из определения цикла: если <tex>C_1 \subset C_2</tex>, то <tex>C_1 \in I</tex>. Значит <tex>C_1 \notin Ccl\mathfrak{C}</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> получаем противоречие.