32
правки
Изменения
Нет описания правки
Докажем, что матроид <tex>M</tex> определен однозначно. Пусть есть два матроида <tex>M_1 \neq M_2</tex> с носителем <tex>E</tex>, семейством циклов <tex>\mathfrak C</tex> и [[Аксиоматизация матроида базами|множествами баз]] <tex>B_1, B_2</tex> соответственно. Не ограничивая общности можно считать, что существует <tex>A \in B_1, A \notin B_2</tex>. Тогда для всех <tex>e \in E, e \notin A: (A \cup e) = C \in \mathfrak C</tex>, но <tex>\mathfrak C</tex> {{---}} семейство циклов <tex>M_2</tex>, следовательно для всех <tex>p \in C</tex> выполнено <tex>(C \setminus p) \in B_2</tex>, что невозможно.
}}
{{Утверждение
|about=
Следствие 1 из теоремы
|statement=
Пусть <tex>M = (S, I)</tex> {{---}} [[Определение матроида|матроид]]. Если <tex>X \in I</tex> и <tex>y \notin X</tex>, тогда <tex>X \cup y \in I</tex> или существует единственный цикл <tex>C \subseteq X \cup y.</tex> Более того, для любого <tex> \widehat{y} \in C, (X \cup y) \setminus \widehat{y} \in I.</tex>
|proof=
Если <tex>X \cup y \notin I, </tex> тогда в нем должен существовать цикл <tex>C_1.</tex> Предположим, что существует другой цикл <tex>C_2 \subseteq X \cup y, </tex> и <tex>C_1 \ne C_2.</tex> Поскольку <tex>X \in I,</tex> тогда и <tex>C_1</tex>, и <tex>C_2</tex> одновременно содержат <tex>y</tex>. По 3 пункту теоремы, <tex>(C_1 \cup C_2) \setminus y</tex> содержит цикл <tex>C.</tex> Возникает противоречие, так как <tex>(C_1 \cup C_2) \setminus y \subseteq X.</tex> Поэтому, <tex>X \cup y</tex> содержит единственный цикл <tex>C.</tex>
Если для какого-либо <tex>\widehat{y} \in C, (X \cup y) \setminus \widehat{y} \notin I, </tex> то <tex>(X \cup y) \setminus \widehat{y}</tex> не является независимым и содержит цикл <tex>\widehat{C}.</tex> Более того, <tex>\widehat{C} \ne C,</tex> так как <tex>\widehat{y} \notin \widehat{C}, </tex> что противоречит единственности <tex>C.</tex>
}}
{{Утверждение
|about=
Следствие 2 из теоремы
|statement=
Пусть <tex>B </tex> и <tex> \widehat{B}</tex> {{---}} базы. Тогда для любого <tex>\widehat{x} \in \widehat{B} \setminus B</tex> существует такой <tex>x \in B \setminus \widehat{B}, </tex> что <tex>(B \cup \widehat{x}) \setminus x</tex> {{---}} база.
|proof=
}}
