1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Циклом''' (англ. '''circuit''') в матроиде называется множество, не являющееся независимым, каждое подмножество которого является независимым.
}}
# От противного. Пусть <tex>D = (C_1 \cup C_2) \setminus p</tex> независимо.
#: Обозначим <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 geqslant |A| + 1 + 1 - 1 = |A| + 1 > |A|.</tex>
#: Отсюда путем многократного применения третьей аксиомы матроидов получим <tex>\exists B: A \subset B</tex> и <tex>|B| = |D|</tex>, причем <tex>B</tex> {{---}} независимо.
#: Поскольку <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>. #: Получаем: <tex>|B| \le leqslant |A| + |C_1 \setminus A| - 1 + |C_2 \setminus A| - 1 = |C_1 \cup C_2| - 2 = |D| - 1</tex> . А поскольку <tex>|B| = |D|</tex> получаем противоречие.
}}
==См. также==
* [[Определение матроида]]
* [[Примеры матроидов]]
== Источники информации ==
* [[wikipedia:en:Matroid#Bases_and_circuits | Wikipedia {{---}} Matroid]]
* [[wikipedia:ru:Матроид#Аксиоматическое определение | Википедия {{---}} Матроид]]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Основные факты теории матроидов]]
