Изменения

Перейти к: навигация, поиск

Аксиоматизация матроида циклами

87 байт добавлено, 18:41, 27 июня 2011
Нет описания правки
# Если <tex>\mathbb C_1, \mathbb C_2 \in \mathfrak C</tex> и <tex>\mathbb C_1 \ne \mathbb C_2</tex>, то <tex>\mathbb C_1 \nsubseteq \mathbb C_2</tex> и <tex>\mathbb C_2 \nsubseteq \mathbb C_1</tex>.
# Если <tex>\mathbb C_1, \mathbb C_2 \in \mathfrak C, \mathbb C_1 \ne \mathbb C_2</tex> и <tex>p \in \mathbb C_1 \cap \mathbb C_2</tex>, то существует <tex>\mathbb C \in \mathfrak C</tex> такой, что <tex>\mathbb C \subseteq (\mathbb C_1 \cup \mathbb C_2) \setminus p</tex>.
Тогда семейство <tex>\mathfrak C</tex> совпадает с [[Теорема о циклах|семейством циклов]] однозначно определенного [[матроида |Определениематроида]] на <tex>\mathbb E</tex>.
|proof=
Пусть семейство <tex>\mathfrak C</tex> удовлетворяет условию теоремы. Множество <tex>\mathbb I \nsubseteq \mathbb E</tex> назовем <tex>\mathfrak C</tex>-независимым, если оно не содержит ни одного из множеств <tex>\mathbb C \in \mathfrak C</tex>. Через <tex>\mathfrak I</tex> обозначим семейство всех <tex>\mathfrak C</teX>-независимых множеств, подмножеств <tex>\mathbb E</tex>. Проверим, что семейство <tex>\mathfrak I</tex> удовлетворяет [[аксиомам из определения матроида|Определение_матроида]].
Поскольку <tex>\varnothing \notin \mathfrak C</tex>, имеем <tex>\varnothing \in \mathfrak I</tex>, и первая аксиома, очевидно, выполняется.
Анонимный участник

Навигация