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

Определение:
Матроид —это пара множеств $\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, \overline {\overline A}<\overline {\overline 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$ такие, что $\overline{\overline A} < \overline{\overline B} \Rightarrow$ по третьей аксиоме матроидов $\exists b \in B:A\cup b \in I \Rightarrow A$ - не базис

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

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

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

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

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

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

---

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

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