Что такое матроид: различия между версиями
NekoKarp (обсуждение | вклад) м (Добавлены категории) |
NekoKarp (обсуждение | вклад) (Изменено обозначение мощности множеств) |
||
Строка 4: | Строка 4: | ||
* Пустое множество принадлежит $I$ ($\emptyset \in I$) | * Пустое множество принадлежит $I$ ($\emptyset \in I$) | ||
* Подмножество множества, принадлежащего $I$ тоже принадлежит $I$ ($A \in I; B\subset A \Rightarrow B \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$ принадлежат $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$) |
}} | }} | ||
{{Определение | {{Определение | ||
Строка 21: | Строка 21: | ||
{{Утверждение | {{Утверждение | ||
|Утверждение=Все базисы матроида имеют одинаковую мощность | |Утверждение=Все базисы матроида имеют одинаковую мощность | ||
− | |Доказательство=Пусть $\exists A,B$ - базисы $\langle X,I \rangle$ такие, что $ | + | |Доказательство=Пусть $\exists A,B$ - базисы $\langle X,I \rangle$ такие, что |$ A |
+ | $|$ < $|$ B $| $ \Rightarrow$ по третьей аксиоме матроидов $\exists b \in B:A\cup b \in I \Rightarrow A$ - не базис | ||
}} | }} | ||
{{Утверждение | {{Утверждение |
Версия 16:47, 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, $|$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$ не являющееся базисом - подмножество хотя бы одного базиса
Доказательство остаётся читателю в качестве упражнения
Утверждение:
Для описания матроида достаточно описания всех его базисов
Доказательство остаётся читателю в качестве упражнения
Автор конспекта: Карп
По всем вопросам пишите в telegram @KS20031501