Что такое матроид: различия между версиями
NekoKarp (обсуждение | вклад) (Создана страница с базовыми определениями матроида) |
NekoKarp (обсуждение | вклад) м (Добавлены категории) |
||
Строка 35: | Строка 35: | ||
|Доказательство=Упражнение | |Доказательство=Упражнение | ||
}} | }} | ||
+ | [[Категория:Конспект]] | ||
+ | [[Категория:Математика]] | ||
{{Автор|Карп|KS20031501}} | {{Автор|Карп|KS20031501}} |
Версия 10:41, 2 февраля 2020
Определение:
Матроид —это пара множеств $\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