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

Теорема (Аксиоматизация матроида циклами):

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

Доказательство:

[math]\triangleright[/math]

Пусть семейство [math]\mathfrak C[/math] удовлетворяет условию теоремы. Множество [math]I \subseteq E[/math] назовем [math]\mathfrak C[/math]-независимым, если оно не содержит ни одного из множеств [math]C \in \mathfrak C[/math]. Через [math]\mathfrak I[/math] обозначим семейство всех [math]\mathfrak C[/math]-независимых множеств, подмножеств [math]E[/math]. Проверим, что семейство [math]\mathfrak I[/math] удовлетворяет аксиомам из определения матроида. Поскольку [math]\varnothing \notin \mathfrak C[/math], имеем [math]\varnothing \in \mathfrak I[/math], и первая аксиома, очевидно, выполняется. Очевидно, что если [math]A \in \mathfrak I[/math] и [math]B \subset A[/math] то [math]B \in \mathfrak I[/math], и, следовательно, вторая аксиома выполнена. Проверим справедливость третьей аксиомы для семейства [math]\mathfrak I[/math]. Предположим, что существуют множества [math]I, J \in \mathfrak I[/math] такие, что [math]|I|\lt |J|[/math], для которых третья аксиома не выполнена. Среди всех таких пар [math]I, J[/math] выберем ту, у которой мощность [math]|I \cup J|[/math] минимальна. Положим [math]J \setminus I = \{p_1,...,p_t\}[/math]. Если [math]t = 1[/math], то, очевидно, [math]I \subset J[/math] и аксиома выполняется. Поэтому достаточно рассмотреть [math]t \geqslant 2[/math]. В силу нашего предположения [math]I \cup p_i \notin \mathfrak I[/math] для любого [math]i \in \{1,...,t\}[/math]. Следовательно, существует [math]C_i \in \mathfrak C[/math] такое, что [math]C_i \subseteq I \cup p_i[/math] и в силу [math]\mathfrak C[/math]-независимости множества [math]I[/math] имеем [math]p_i \in C_i[/math] для любого [math]i \in \{1,...,t\}[/math]. Ясно, что множества [math]C_1,...,C_t[/math] попарно различны. Рассмотрим множество [math]C_1.[/math] Для него верно [math]p_1 \in C_1 \subseteq I \cup p_1.[/math] В силу [math]\mathfrak C[/math]-независимости [math]J[/math] существует [math]q_1 \in I \setminus J[/math] такой, что [math]q_1 \in C_1.[/math] Рассмотрим теперь множество [math](I \setminus q_1) \cup p_1.[/math] Если [math](I \setminus q_1) \cup p_1 \notin \mathfrak I[/math], то существует [math]C' \in \mathfrak C[/math], для которого существует такое [math]C'' \in \mathfrak C,[/math] что [math]C'' \subseteq (C_1 \cup C') \setminus p_1 \subseteq I.[/math] Пришли к противоречию с условием [math]I \in \mathfrak I.[/math] Пусть [math](I \setminus q_1) \cup p_1 \in \mathfrak I[/math]. Заметим, что [math]|((I \setminus q_1) \cup p_1) \cup J| \lt |I \cup J|[/math]. Поэтому в силу выбора пары [math]I, J[/math] для пары [math](I \setminus q_1) \cup p_1, J[/math] существует элемент [math]p_j[/math], где [math]j \geqslant 2[/math], такой, что [math](I \setminus q_1) \cup p_1 \cup p_j \in \mathfrak I[/math]. Возьмем множество [math]C_j \in \mathfrak C[/math]. Для него выполняется [math]p_j \in C_j \subseteq I \cup p_j.[/math] Если [math]q_1 \notin C_j[/math], то [math]C_j \subseteq (I \setminus q_1) \cup p_j \subseteq (I \setminus q1) \cup p_1 \cup p_j[/math], что невозможно. Следовательно, [math]q_1 \in C_j \cap C_1[/math] и [math]C_j \ne C_1[/math]. Тогда по 3 пункуту теоремы, существует [math]C \in \mathfrak C[/math], для которого [math]C \subseteq (C_j \cup C_1) \setminus q_1 \subseteq (C_j \setminus q_1) \cup (C_1 \setminus q_1) \subseteq ((I \setminus q_1) \cup p_j) \cup ((I \setminus q_1) \cup p_1)[/math], которое равно [math](I \setminus q_10) \cup p_1 \cup p_j \in \mathfrak I[/math], что невозможно. Итак, семейство [math]\mathfrak I[/math] удовлетворяет аксиомам матроида. Следовательно, существует матроид [math]M[/math] на множестве [math]E[/math], для которого семейство [math]\mathfrak I[/math] является семейством независимых множеств. Из определения [math]\mathfrak C[/math]-независимости легко следует, что семейство [math]\mathfrak C[/math] совпадает с множеством циклов матроида [math]M[/math] Докажем, что матроид [math]M[/math] определен однозначно. Пусть есть два матроида [math]M_1 \neq M_2[/math] с носителем [math]E[/math], семейством циклов [math]\mathfrak C[/math] и множествами баз [math]B_1, B_2[/math] соответственно. Не ограничивая общности можно считать, что существует [math]A \in B_1, A \notin B_2[/math]. Тогда для всех [math]e \in E, e \notin A: (A \cup e) = C \in \mathfrak C[/math], но [math]\mathfrak C[/math] — семейство циклов [math]M_2[/math], следовательно для всех [math]p \in C[/math] выполнено [math](C \setminus p) \in B_2[/math], что невозможно.

[math]\triangleleft[/math]

См. также

• Определение матроида
• Примеры матроидов
• Теорема о циклах

Источники информации

• Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2