Что такое матроид

Определение:
Матроид —это пара множеств $\langle X,I\rangle$, где $X$ - некоторое множество, называемое носителем матроида, а $I$ - некоторое подмножество множества $X$ ($I\subset 2^X$). Для данной пары выполнены 3 аксиомы матроидов:

• Пустое множество принадлежит $I$ ($\emptyset \in I$)
• Подмножество множества, принадлежащего $I$ тоже принадлежит $I$ ($A \in I; B\subset A \Rightarrow B \in I$)
• Если множества $A$ и $B$ принадлежат $I$ и мощность $A$ меньше мощности $B$, то существует хотя бы один элемент $b$ множества $B$ такой, что $A\cup b$ принадлежит $I$ ($A,B \in I, $|$A$|$<$|$B$|$ \Rightarrow \exists b \in B: A\cup b \in I$)

Определение:
Независимое множество —это множество $A \in I$ для данного $X$

Определение:
Зависимое множество —это множество $A \notin I$ для данного $X$

Определение:
Базис матроида —это любое независимое множество данного матроида, добавление в которое элемента всегда делает его зависимым ($A$ - базис $\langle X,I\rangle \Leftrightarrow \forall x \notin A: A\cup x \notin I$)

Свойства базиса матроида

Утверждение:
Все базисы матроида имеют одинаковую мощность

Доказательство:
Пусть $\exists A,B$ - базисы $\langle X,I \rangle$ такие, что |$ A $|$ < $|$ B $| $ \Rightarrow$ по третьей аксиоме матроидов $\exists b \in B:A\cup b \in I \Rightarrow A$ - не базис

Утверждение:
Никакой базис не является подмножеством другого базиса

Доказательство данного факта тривиально

Утверждение:
Любое множество $A\in I$ не являющееся базисом - подмножество хотя бы одного базиса

Доказательство данного факта тривиально

Утверждение:
Для описания матроида достаточно описания всех его базисов

Доказательство данного факта тривиально

Определение:
Цикл —это любое зависимое множество, каждое подмножество которого(исключая его самого) независимо

Свойства циклов

Утверждение:
Любое зависимое множество имеет хотя бы одно подмножество-цикл

Доказательство:
Пусть существует зависимое множество, ни одно подмножество которого(включая его самого) не является циклом, тогда рассмотрим наименьшее по размеру его подмножество, являющееся зависимым, заметим, что удаление любого элемента из него будет делать наше множество зависимым $\Rightarrow$ мы получили цикл

Утверждение:
Никакой цикл не является подмножеством другого цикла

Доказательство данного факта тривиально

Утверждение:
Для описания матроида достаточно описания всех его циклов

Доказательство данного факта тривиально

Утверждение:
Из объединения двух циклов можно удалить любой элемент и полученное множество будет всё равно содержать цикл

Доказательство остаётся читателю в качестве упражнения

Определение:
Ранг(также ранговая функция $r(S)$, где $S$ - подмножество $X$) —это максимальное независимое подмножество для данного подмножества

Свойства рангов

Утверждение:
Ранг множества не больше его размера

Доказательство данного факта тривиально

Утверждение:
Ранг независимого множества равен его размеру

Доказательство данного факта тривиально

Утверждение:
Ранг носителя матроида - размер базисов

Доказательство данного факта тривиально

Утверждение:
Ранг пустого множества = 0

Доказательство данного факта тривиально

Утверждение:
Ранг множества не меньше ранга любого его подмножества

Доказательство:
Любое подмножество подмножества тоже является подмножеством текущего множества $\Rightarrow$ наибольшее независимое подмножество подмножества данного множества является подмножеством исходного множества $\Rightarrow$ если предположить, что ранг данного множества меньше его подмножества, то возникнет противоречие, тк наибольшее независимое подмножество того подмножества будет подмножеством исходного множества $\Rightarrow$ его размер учтётся при нахождении ранга, а значит он будет не меньше, чем ранг подмножества

Утверждение:
Добавление элемента в множество увеличивает его ранг не более, чем на 1 ($\forall S\in 2^X; x\notin S:r(S)\le r(S\cup x)\le r(S)+1$)

Доказательство данного факта тривиально

---

Автор конспекта: Карп

По всем вопросам пишите в telegram @KS20031501