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

Материал из Algocode wiki
Версия от 15:45, 3 февраля 2020; NekoKarp (обсуждение | вклад) (Добавлен раздел "Свойства циклов")
Перейти к: навигация, поиск

Определение:
Матроид —это пара множеств $\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$ мы получили цикл

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

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

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

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

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

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



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

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