Изменения

Пусть <tex>\mathfrak C</tex> {{---}} семейство подмножеств конечного непустого множетва множества <tex>\mathbb E</tex> такое, что:

# Если <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>.

Пусть семейство <tex>\mathfrak C</tex> удовлетворяет условию теоремы. Множество <tex>\mathbb I \nsubseteq \mathbb subseteq 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>\mathbb A \in \mathfrak I</tex> и <tex>\mathbb B \subset \mathbb A</tex> то <tex>\mathbb B \in \mathfrak I</tex>, и, следовательно, вторая аксиома выполнена.

Проверим справедливость третьей аксиомы для семейства <tex>\mathfrak I</tex>. Предположим, что существуют множества <tex>\mathbb I, \mathbb J \in \mathfrak I</tex> такие, что <tex>|\mathbb I|<|\mathbb J|</tex>, для которых третья аксиома не выполнена. Среди всех таких пар <tex>\mathbb I, \mathbb J</tex> выберем ту, у которой мощность <tex>|\mathbb I \cup \mathbb J|</tex> минимальна. Положим <tex>\mathbb J \setminus \mathbb I = \{p_1,...\ldots,p_t\}</tex>. Если <tex>t = 1</tex>, то, очевидно, <tex>\mathbb I \subset \mathbb J</tex> и аксиома выполняется. Поэтому достаточно рассмотреть <tex>t \ge geqslant 2</tex>.

В силу нашего предположения <tex>\mathbb I \cup p_i \notin \mathfrak I</tex> для любого <tex>i \in \{1,...\ldots,t\}</tex>. Следовательно, существует <tex>\mathbb C_i \in \mathfrak C</tex> такое, что <tex>\mathbb C_i \subseteq \mathbb I \cup p_i</tex> и в силу <tex>\mathfrak C</tex>-независимости множества <tex>\mathbb I</tex> имеем <tex>p_i \in \mathbb C_i</tex> для любого <tex>i \in \{1,...\ldots,t\}</tex>. Ясно, что множества <tex>\mathbb C_1,...\ldots,\mathbb C_t</tex> попарно различны.

Рассмотрим множество <tex>\mathbb C_1.</tex>. Для него верно <tex>p_1 \in \mathbb C_1 \subseteq \mathbb I \cup p_1.</tex>. В силу <tex>\mathfrak C</tex>-независимости <tex>\mathbb J</tex> существует <tex>q_1 \in \mathbb I \setminus \mathbb J</tex> такой, что <tex>q_1 \in \mathbb C_1.</tex>. Рассмотрим теперь множество <tex>(\mathbb I \setminus q_1) \cup p_1.</tex>.

Если <tex>(\mathbb I \setminus q_1) \cup p_1 \notin \mathfrak I</tex>, то существует <tex>\mathbb C' \in \mathfrak C</tex>, для которого существует такой такое <tex>\mathbb C'' \in \mathfrak C,</tex>, что <tex>\mathbb C'' \subseteq (\mathbb C_1 \cup \mathbb C_2C') \setminus p_1 \subseteq \mathbb I.</tex>. Пришли к противоречию с условием <tex>\mathbb I \in \mathfrak I.</tex>.

Пусть <tex>(\mathbb I \setminus q_1) \cup p_1 \in \mathfrak I</tex>. Заметим, что <tex>|((\mathbb I \setminus q_1) \cup p_1) \cup \mathbb J| < |\mathbb I \cup \mathbb J|</tex>. Поэтому в силу выбора пары <tex>\mathbb I, \mathbb J</tex> для пары <tex>(\mathbb I \setminus q_1) \cup p_1, J</tex> существует элемент <tex>p_j</tex>, где <tex>j \ge geqslant 2</tex>, такой, что <tex>(\mathbb I \setminus q_1) \cup p_1 \cup p_j \in \mathfrak I</tex>. Возьмем множество <tex>\mathbb C_j \in \mathfrak C</tex>. Для него выполняется <tex>p_j \in \mathbb C_j \subseteq \mathbb I \cup p_j.</tex>. Если <tex>q_1 \notin \mathbb C_j</tex>, то <tex>\mathbb C_j \subseteq (\mathbb I \setminus q_1) \cup p_j \subseteq (\mathbb I \setminus q1q_1) \cup p_1 \cup p_j</tex>, что невозможно. Следовательно, <tex>q_1 \in \mathbb C_j \cap C_1</tex> и <tex>\mathbb C_j \ne \mathbb C_1</tex>. Тогда по <tex>3 пункуту </tex> пункту теоремы, существует <tex>\mathbb C \in \mathfrak C</tex>, для которого <tex>\mathbb C \subseteq (\mathbb C_j \cup \mathbb C_1) \setminus q_1 \subseteq (\mathbb C_j \setminus q_1) \cup (\mathbb C_1 \setminus q_1) \subseteq ((\mathbb I \setminus q_1) \cup p_j) \cup ((\mathbb I \setminus q_1) \cup p_1)</tex>, которое равно <tex>(\mathbb I \setminus q_10q_1) \cup p_1 \cup p_j \in \mathfrak I</tex>, что невозможно.

Итак, семейство <tex>\mathfrak I</tex> удовлетворяет аксиомам матроида. Следовательно, существует матроид <tex>M(\mathbb E)</tex> на множестве <tex>\mathbb E</tex>, для которого семейство <tex>\mathfrak I</tex> является семейством независимых множеств. Из определения <tex>\mathfrak C</tex>-независимости легко следует, что семейство <tex>\mathfrak C</tex> совпадает с множеством цисклов циклов матроида <tex>M</tex> Докажем, что матроид <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>\mathbb Emathfrak C</tex> {{---}} семейство циклов <tex>M_2</tex>, следовательно для всех <tex>p \in C</tex> выполнено <tex>(C \setminus p) \in B_2</tex>, что невозможно.}} {{Утверждение|about= Следствие <tex>1</tex> из теоремы|statement= Пусть <tex>M = \langle X, I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Если <tex>A \in I</tex> и <tex>y \notin A, y \in X</tex>, тогда <tex>A \cup y \in I</tex> или существует единственный цикл <tex>C \subseteq A \cup y.</tex> Более того, для любого <tex> \widehat{y} \in C, (A \cup y) \setminus \widehat{y} \in I.</tex>|proof=Если <tex>A \cup y \notin I, </tex> тогда в нем должен существовать цикл <tex>C_1.</tex> Предположим, что существует другой цикл <tex>C_2 \subseteq A \cup y, </tex> и <tex>C_1 \ne C_2.</tex> Поскольку <tex>A \in I,</tex> тогда и <tex>C_1</tex>, и <tex>C_2</tex> одновременно содержат <tex>y</tex>. По <tex>3</tex> пункту теоремы, <tex>(C_1 \cup C_2) \setminus y</tex> содержит цикл <tex>C.</tex> Возникает противоречие, так как <tex>(C_1 \cup C_2) \setminus y \subseteq A.</tex> Поэтому, <tex>A \cup y</tex> содержит единственный цикл <tex>C.</tex>Если для какого-либо <tex>\widehat{y} \in C, (A \cup y) \setminus \widehat{y} \notin I, </tex> то <tex>(A \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>

== Литература ==[[Категория:Алгоритмы и структуры данных]][[Категория:Матроиды]]''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика[[Категория: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />Основные факты теории матроидов]]