Аксиоматизация матроида циклами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (русский язык)
м (косметика)
Строка 15: Строка 15:
 
Очевидно, что если <tex>\mathbb A \in \mathfrak I</tex> и <tex>\mathbb B \subset \mathbb A</tex> то <tex>\mathbb B \in \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,...,p_t\}</tex>. Если <tex>t = 1</tex>, то, очевидно, <tex>\mathbb I \subset \mathbb J</tex> и аксиома выполняется. Поэтому имеем <tex>t \ge 2</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,...,p_t\}</tex>. Если <tex>t = 1</tex>, то, очевидно, <tex>\mathbb I \subset \mathbb J</tex> и аксиома выполняется. Поэтому достаточно рассмотреть <tex>t \ge 2</tex>.
  
В силу нашего предположения <tex>\mathbb I \cup p_i \notin \mathfrak I</tex> для любого <tex>i=1,...,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 C_i</tex> для любого <tex>i=1,...,t</tex>. Ясно, что множества <tex>C_1,...,C_t</tex> попарно различны.
+
В силу нашего предположения <tex>\mathbb I \cup p_i \notin \mathfrak I</tex> для любого <tex>i \in \{1,...,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 C_i</tex> для любого <tex>i=1,...,t</tex>. Ясно, что множества <tex>C_1,...,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 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>.

Версия 00:35, 26 июня 2011

Теорема (Аксиоматизация матроида циклами):
Пусть [math]\mathfrak C[/math] — семейство подмножеств конечного непустого множетва [math]\mathbb E[/math] такое, что:
  1. [math]\varnothing \notin \mathfrak C[/math]
  2. Если [math]\mathbb C_1, \mathbb C_2 \in \mathfrak C[/math] и [math]\mathbb C_1 \ne \mathbb C_2[/math], то [math]\mathbb C_1 \nsubseteq \mathbb C_2[/math] и [math]\mathbb C_2 \nsubseteq \mathbb C_1[/math].
  3. Если [math]\mathbb C_1, \mathbb C_2 \in \mathfrak C, \mathbb C_1 \ne \mathbb C_2[/math] и [math]p \in \mathbb C_1 \cap \mathbb C_2[/math], то существует [math]\mathbb C \in \mathfrak C[/math] такой, что [math]\mathbb C \subseteq (\mathbb C_1 \cup \mathbb C_2) \setminus p[/math].
Тогда семейство [math]\mathfrak C[/math] совпадает с семейством циклов однозначно определенного матроида на [math]\mathbb E[/math].
Доказательство:
[math]\triangleright[/math]

Пусть семейство [math]\mathfrak C[/math] удовлетворяет условию теоремы. Множество [math]\mathbb I \nsubseteq \mathbb E[/math] назовем [math]\mathfrak C[/math]-независимым, если оно не содержит ни одного из множеств [math]\mathbb C \in \mathfrak C[/math]. Через [math]\mathfrak I[/math] обозначим семейство всех [math]\mathfrak C[/math]-независимых множеств, содержащихся в [math]\mathbb E[/math]. Проверим, что семейство [math]\mathfrak I[/math] удовлетворяет аксиомам из определения матроида.

Поскольку [math]\varnothing \notin \mathfrak C[/math], имеем [math]\varnothing \in \mathfrak I[/math], и первая аксиома, очевидно, выполняется.

Очевидно, что если [math]\mathbb A \in \mathfrak I[/math] и [math]\mathbb B \subset \mathbb A[/math] то [math]\mathbb B \in \mathfrak I[/math], и, следовательно, вторая аксиома выполнена.

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

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

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

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

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

Итак, семейство [math]\mathfrak I[/math] удовлетворяет аксиомам матроида. Следовательно, существует матроид [math]M(\mathbb E)[/math] на множестве [math]\mathbb E[/math], для которого семейство [math]\mathfrak I[/math] является семейством независимых множеств. Из определения [math]\mathfrak C[/math]-независимости легко следует, что семейство [math]\mathfrak C[/math] совпадает с множеством цисклов матроида [math]M(\mathbb E)[/math]
[math]\triangleleft[/math]